Recursion

Definition

The process in which a function calls itself directly or indirectly is called recursion and the corresponding function is called as recursive function.

void func() {
    // Some code
    func(); // Function call
    // Some code
}

Basic Rules of Recursion

Function should call itself.
Function should have a base condition.
Function should change its state and move towards the base condition.

Below is a simple C++ program to demonstrate working of recursion.

void fun(int N) {
 
    // Base condition/case
    if (N == 0) {
        return;
    }
    cout << N << " ";
 
    // Recursive call
    fun(N - 1);
}

Factorial using Recursion

Understanding

Factorial(N) = N * (N - 1) * (N - 2) * ... * 2 * 1
Recursively, Factorial(N) = N * Factorial(N - 1)
Base condition: Factorial(0) = 1

Code

int factorial(int N) {
    // Base condition
    if (N == 0) {
        return 1;
    }
    // Recursive call
    return N * factorial(N - 1);
}

Deep Dive

During Recursion a stack is created to store the fuction calls and the function calls are pushed or popped from the stack one by one as the function calls are made or returned respectively.
The stack is a LIFO (Last In First Out) data structure.


Factorial using Recursion - Stack

In the above image, the function calls are pushed into the stack and the function calls are popped from the stack one by one as the function calls are returned.

Stack Overflow in Recursion

The stack used to store the function calls can store only a finite number of funtion callls (say n). If the number of function calls exceeds n, then the stack overflows and the program crashes.
Cases when stack overflow occurs:
1. No base condition - The function calls are pushed into the stack infinitely and the stack overflows.
2. Recursive call do not align towards the base condition - The function never reaches the base condition and the stack overflows.

Recursion vs Iteration

Parameter	Iteration	Recursion
Working Principle	We initialize the loop control variable and increment / decrement based on the the need. Before execution control variable is checked with the termination condition.	Function calls itself to solve the problem. Here we define a base case which is the termination point.
Control Variable and Control Logic	Value of the control variable continuously movees towards the termination condition.	Function call moves towards the base case.
Storage	Control Variable holds the value and it will be incremented / decremented based on the need	Every function state is maintained in the stack memory and when the base case is met, the execution follows LOFO principle.
Infinite Loop	When control variable do not move towards the terminating condition, the loop is executed infinte times. A lot of CPU cycles are consumed.	If no base case defined or the function call not aligned to the base case then the function calls may overflow the stack memory and will crash the system

Converting an Iterative Solution to Recursive Solution

Iteration

Logic: n is printed and decremented till it reaches 1.

Recursion

Logic: n is printed and the function is called with n - 1 as the parameter.

Activity: Can you write iterative and recursive function for reversing a string?

Types of Recursion


Types of Recursion

Direct Recursion

Tail Recursion

When the recursive call is the last statement in the function, it is called tail recursion.

void tailRecursion() {
    // some code
    tailRecursion();
}

Head Recursion

When the recursive call is the first statement in the function, it is called head recursion.

void headRecursion() {
    headRecursion();
    // some code
}

Nested Recursion

When a recursive function calls itself as a parameter in the function call, it is called nested recursion.

void nestedRecursion() {
    // some code
    nestedRecursion(nestedRecursion(nestedRecursion()));
}

Tree recursion

When a recursive function calls itself more than one time, it is called tree recursion.

void treeRecursion() {
    // some code
    treeRecursion();
    // some code
    treeRecursion();
}

Indirect Recursion

When a recursive function calls another function and that function calls the first function, it is called indirect recursion.

void indirectRecursion1() {
    // some code
    indirectRecursion2();
}
 
void indirectRecursion2() {
    // some code
    indirectRecursion1();
}

Fun Fact: If you are a fan of the movie Inception, you can relate the types of recursion with the movie.

The stack is created in the memory and the memory is divided into two parts: Stack and Heap.
The stack is used to store the function calls and the heap is used to store the variables and the data where the stack is of fixed size and the heap is of dynamic size.
Using recursive algorithm, certain problems can be solved quite easily. Examples of such problems are Towers of Hanoi (TOH), Inorder/Preorder/Postorder Tree Traversals, DFS of Graph, etc.

TODO Basic Questions