Recursion

In C/C++, a function calling itself is called a recursive function.

Recursion is a technique that allows us to break down a problem into one or more sub-problems that are similar in form to the original problem.

A program becomes compact and readable with recursive functions. Recursion is extremely powerful as it enables the programmer to express complex processes easily. Recursive programs are used in a variety of applications ranging from calculating the factorial of a number to playing complex games against human intelligence.

A recurrence is a well-defined mathematical function where the function being defined is applied within its own definition.

The factorial we defined as n! = n \ (n - 1)! is an example of recurrence with 1! = 1 as the end condition.

Use of stack in recursion

The stack is a special area of memory where temporary variables are stored. It acts on the LIFO principle.

The following points are to be noted when recursion is used:

1. The number of times a function calls itself is known as the recursive depth of that function.

2. Each time the function calls itself, it stores one or more variables on the stack. Since stacks hold a limited amount of memory, the functions with a high recursive depth may crash because of non-availability of memory. Such a situation is known as stack overflow.

3. Recursive functions should have a terminating (or end) condition.

4. All recursive functions go through two distinct phases. The first phase, winding, occurs when the function calls itself and pushes values onto the stack. The second phase, unwinding, occurs when the function pops values from the stack, usually after the end condition.

 Variants of Recursion

The recursive functions based on characterization are categorized as

1. Direct, 2. Indirect, 3. Linear, 4.Tree, and 5.Tail recursions.

1. Direct recursion

Recursion is when a function calls itself. Recursion is said to be direct when a function calls itself directly.

int Power(int x, int y)

{

if(y == 1)

return x;

else

return (x * Power(x, y - 1));

}

2. Indirect recursion

A function is said to be indirectly recursive if it calls another function, which in turn calls it.

int Fact(int n)

{

if(n <= 1)

return 1;

else

return (n * Dummy(n - 1));

}

void Dummy(int n)

{

Fact(n);

}

3. Linear Recursion

A recursive function is said to be linearly recursive when no pending operation involves another recursive call.

4. Tree Recursion

In a recursive function, if there is another recursive call in the set of operations to be completed after the recursion is over, this is called a tree recursion.

 5. Tail recursion

A recursive function is said to be tail recursive if there are no pending operations to be performed on return from a recursive call. Tail recursion is also used to return the value of the last recursive call as the value of the function. Tail recursion is advantageous as the amount of information that must be stored during computation is independent of the number of recursive calls.