Recursion

RECURSION

Recursion in computer science is a way of thinking about and solving problems. It is, in fact, one of the central ideas of computer science. Solving a problem using recursion means the solution depends on solutions to smaller instances of the same problem.

"The power of recursion evidently lies in the possibility of defining an infinite set of objects by a finite statement. In the same manner, an infinite number of computations can be described by a finite recursive program, even if this program contains no explicit repetitions."

Most high-level computer programming languages support recursion by allowing a function to call itself within the program text. Imperative languages define looping constructs like “while” and “for” loops that are used to perform repetitive actions. Some functional programming languages do not define any looping constructs but rely solely on recursion to repeatedly call code. Computability theory has proven that these recursive only languages are mathematically equivalent to the imperative languages, meaning they can solve the same kinds of problems even without the typical control structures like “while” and “for”.

• Recursion in computer science

A common method of simplification is to divide a problem into subproblems of the same type. As a computer programming technique, this is called divide and conquer and is key to the design of many important algorithms, as well as being a fundamental part of dynamic programming.
Recursion in computer programming is exemplified when a function is defined in terms of itself. One example application of recursion is in parsers for programming languages. The great advantage of recursion is that an infinite set of possible sentences, designs or other data can be defined, parsed or produced by a finite computer program.
Recurrence relations are equations to define one or more sequences recursively. Some specific kinds of recurrence relation can be "solved" to obtain a non-recursive definition.
A classic example of recursion is the definition of the factorial function, given here in C code:

unsigned int factorial(unsigned int n)
{
if (n <= 1) return 1; return n * factorial(n-1); }

The function calls itself recursively on a smaller version of the input (n - 1) and multiplies the result of the recursive call by n, until reaching the base case, analogously to the mathematical definition of factorial.
Use of recursion in an algorithm has both advantages and disadvantages. The main advantage is usually simplicity. The main disadvantage is often that the algorithm may require large amounts of memory if the depth of the recursion is very large. It has been claimed that recursive algorithms are easier to understand because the code is shorter and is closer to a mathematical definition, as seen in these factorial examples.
It is often possible to replace a recursive call with a simple loop, as the following example of factorial shows:

unsigned int factorial(unsigned int n) {
if (n <= 1) return 1; unsigned int result = n; while (--n) result *= n; return result; }

It should be noted that on most CPUs the above examples give correct results only for small values of n, due to arithmetic overflow.
An example of a recursive algorithm is a procedure that processes (does something with) all the nodes of a tree data structure:

void ProcessTree(node x) {
unsigned int i = 0;
while (i <>

To process the whole tree, the procedure is called with a root node representing the tree as an initial parameter. The procedure calls itself recursively on all child nodes of the given node (i.e. sub-trees of the given tree), until reaching the base case that is a node with no child nodes (i.e. a tree having no branches known as a "leaf").
A tree data structure itself can be defined recursively (and so predestinated for recursive processing) like this:

typedef struct {
unsigned int count;
node* children;
} node

• Recursive programming

Creating a recursive procedure essentially requires defining a "base case", and then defining rules to break down more complex cases into the base case. Key to a recursive procedure is that with each recursive call, the problem domain must be reduced in such a way that eventually the base case is arrived at.

Some authors classify recursion as either "generative" or "structural". The distinction is made based on where the procedure gets the data that it works on. If the data comes from a data structure like a list, then the procedure is "structurally recursive"; otherwise, it is "generatively recursive".

Many well-known recursive algorithms generate an entirely new piece of data from the given data and recur on it. HTDP (How To Design Programs) refers to this kind as generative recursion. Examples of generative recursion include: gcd, quicksort, binary search, mergesort, Newton's method, fractals, and adaptive integration.

• Examples of Recursively defined procedures (generative recursion)

Factorial
A classic example of a recursive procedure is the function used to calculate the factorial of an integer.
Function definition: 0 \\ \end{cases} "

Pseudocode (recursive):
function factorial is:input: integer n such that n >= 1output: [n × (n-1) × (n-2) × … × 1]
1. if n is 0, return 1
2. otherwise, return [ n × factorial(n-1) ]
end factorial
A recurrence relation is an equation that relates later terms in the sequence to earlier terms.Recurrence relation for factorial:bn = n * bn-1b0 = 1
Computing the recurrence relation for n = 4:
b4 = 4 * b3 = 4 * 3 * b2
= 4 * 3 * 2 * b1
= 4 * 3 * 2 * 1 * b0
= 4 * 3 * 2 * 1 * 1
= 4 * 3 * 2 * 1
= 4 * 3 * 2
= 4 * 6
= 24

Example Implementations:
Scheme (recursive)
C (recursive)
;; Input: Integer n such that n >= 0
(define (fact n)
(if (= n 0)
1
(* n (fact (- n 1)))))
//INPUT: n is an integer such that n >= 0
int fact(int n)
{
if (n == 0)
return 1;
else
return n * fact(n - 1);
}

This factorial function can also be described without using recursion by making use of the typical looping constructs found in imperative programming languages:
Pseudocode (iterative):
function factorial is:input: integer n such that n >= 0output: [n × (n-1) × (n-2) × … × 1]
1. create new variable called running_total with a value of 1
2. begin loop
1. if n is 0, exit loop
2. set running_total to (running_total × n)
3. decrement n
4. repeat loop
3. return running_total
end factorial

Scheme, however, is a functional programming language and does not define any looping constructs. It relies solely upon recursion to perform all looping. Because Scheme is tail-recursive, a recursive procedure can be defined that implements the factorial procedure as an iterative process — meaning that it uses constant space but linear time.

Example implementations:
Scheme (iterative)
C (iterative)
;; Input: Integer n such that n >= 0
(define (fact n)
(fact-iter 1 n))
(define (fact-iter running_total n)
(if (= n 0)
running_total
(fact-iter (* running_total n) (- n 1))))
int fact(int n)
{
int running_total;
for (running_total = 1; n != 0; --n)
running_total *= n;
return running_total;
}

Fibonacci
Another well known recursive sequence is the Fibonacci numbers. The first few elements of this sequence are: 0, 1, 1, 2, 3, 5, 8, 13, 21...
Function definition: = 2 \\ \end{cases} "

Pseudocode
function fib is:
input: integer n such that n >= 0
1. if n is 0, return 0
2. if n is 1, return 1
3. otherwise, return [ fib(n-1) + fib(n-2) ]
end fib

Recurrence relation for Fibonacci:bn = bn-1 + bn-2b1 = 1, b0 = 0
Computing the recurrence relation for n = 4:
b4 = b3 + b2
= b2 + b1 + b1 + b0
= b1 + b0 + 1 + 1 + 0
= 1 + 0 + 1 + 1 + 0
= 3

Example Implementations:
Scheme
C
Python
;; n is an integer such that n >= 0
(define (fib n)
(cond ((= n 0) 0)
((= n 1) 1)
(else
(+ (fib (- n 1))
(fib (- n 2))))))
int fib(int n)
{
if (n == 0)
return 0;
else if (n == 1)
return 1;
else
return fib(n-1) + fib(n-2);
}
def fib(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fib(n-1) + fib(n-2)

These implementations are especially bad because each time the function is executed, it will make two function calls to itself each of which in turn makes two more function calls and so on until they "bottom out" at 1 or 0. This is an example of "tree recursion", and grows exponentially in time and linearly in space requirements.