Recursion

Introduction:

Recursion is a fundamental concept in programming and data structures, where a function calls itself to solve a problem. This technique works under a condition called the base case, which ensures the recursion eventually stops. Recursion is both time-efficient and memory-efficient when used appropriately, especially for problems that can be divided into smaller, identical sub-problems.

In simple terms, recursion allows breaking down complex problems into manageable parts. It is commonly used in algorithms like divide and conquer, tree traversals, and dynamic programming.

Key Points:

Base Case: The condition at which recursion stops.
Recursive Step: The step where the function calls itself with a smaller sub-problem.
Stack Overflow: If the base case is not defined or met, recursion continues indefinitely, causing a stack overflow.

Note

Recursion can sometimes be replaced by iteration, but recursive solutions are often more elegant and closer to the problem's natural representation.

Visualizing Recursion:

Example: Factorial Calculation

#include <iostream>
using namespace std;
int factorial(int n) {
    if (n == 0 || n == 1) return 1; // Base case
    return n * factorial(n - 1); // Recursive step
}
int main() {
    int num = 5;
    cout << "Factorial of " << num << " is " << factorial(num) << endl;
    return 0;
}

def factorial(n):
    if n == 0 or n == 1:  # Base case
        return 1
    return n * factorial(n - 1)  # Recursive step
num = 5
print(f"Factorial of {num} is {factorial(num)}")

function factorial(n) {
    if (n === 0 || n === 1) return 1; // Base case
    return n * factorial(n - 1); // Recursive step
}
let num = 5;
console.log(`Factorial of ${num} is ${factorial(num)}`);

Warning

Ensure that the base case is correctly defined to avoid infinite recursion!

Core Concepts:

Tail Recursion

In tail recursion, the recursive call is the last operation in the function. This allows some compilers or interpreters to optimize the recursive calls and save memory.

#include <iostream>
using namespace std;
int tailFactorial(int n, int acc = 1) {
    if (n == 0) return acc;
    return tailFactorial(n - 1, acc * n);
}
int main() {
    cout << tailFactorial(5); // Output: 120
    return 0;
}

def tail_factorial(n, acc=1):
    if n == 0:
        return acc
    return tail_factorial(n - 1, acc * n)
print(tail_factorial(5))  # Output: 120

function tailFactorial(n, acc = 1) {
    if (n === 0) return acc;
    return tailFactorial(n - 1, acc * n);
}
console.log(tailFactorial(5)); // Output: 120

Applications of Recursion

Step 1: Divide and Conquer

Recursion is heavily used in divide-and-conquer algorithms like merge sort, quicksort, and binary search.

Step 2: Tree and Graph Traversals

Recursive techniques are ideal for traversing trees (e.g., pre-order, in-order, post-order) and graphs (e.g., DFS).

Step 3: Dynamic Programming

Problems like Fibonacci sequence, knapsack, and matrix chain multiplication use recursion combined with memoization.

Recursive vs Iterative Approaches

Feature	Recursive Approach	Iterative Approach
Elegance	Simple and closer to natural logic	Sometimes verbose
Efficiency	May cause stack overflow	No stack overflow
Optimization	Tail recursion can be optimized	Already optimized

TOH using recursion

Objective: The objective of Tower of Hanoi (TOH) is to transfer all the disks from origin pole to destination pole using intermediate pole for temporary storage.

Conditions:

Move only one disk at a time.
Each disk must always be placed around one of the poles.
Never place a larger disk on top of a smaller disk.

Algorithm: To move a tower of n disks from source to destination (where n is a positive integer):

If n == 1: Move a single disk from source to destination.
If n > 1:
- Move n-1 disks from source to temporary.
- Move the nth disk from source to destination.
- Move n-1 disks from temporary to destination.

Pseudocode:

TOH(n, src, dist, temp) {
    if n == 1:
        Display "Move disc {n} from source to destination"
    else:
        TOH(n-1, src, temp, dist)
        Display "Move disc {n} from source to destination"
        TOH(n-1, temp, dist, src)
}

Implementation:

#include <stdio.h>
void toh(int n, char src, char dist, char temp) {
    if (n == 1) {
        printf("Move disc %d from %c to %c\n", n, src, dist);
    } else {
        toh(n - 1, src, temp, dist);
        printf("Move disc %d from %c to %c\n", n, src, dist); 
        toh(n - 1, temp, dist, src);
    }
}
int main() {
    int n;
    printf("Enter the number of discs: ");
    scanf("%d", &n);
    toh(n, 'A', 'C', 'B');
    return 0;
}

#include <iostream>
using namespace std;
void toh(int n, string src, string dist, string temp) {
    if (n == 1) {
        cout << "Move disc " << n << " from " << src << " to " << dist << endl;
    } else {
        toh(n - 1, src, temp, dist);
        cout << "Move disc " << n << " from " << src << " to " << dist << endl;
        toh(n - 1, temp, dist, src);
    }
}
int main() {
    int n;
    cout << "Enter the number of discs: ";
    cin >> n;
    toh(n, "Source", "Destination", "Temporary");
    return 0;
}

def toh(num, src, dist, temp):
    if num == 1:
        print(f"Move disc {num} from {src} to {dist}")
    else:
        toh(num - 1, src, temp, dist)
        print(f"Move disc {num} from {src} to {dist}")
        toh(num - 1, temp, dist, src)

disc = int(input("Enter the number of discs: "))
toh(disc, "Source", "Destination", "Temporary")

function toh(n, src, dist, temp) {
    if (n === 1) {
        console.log(`Move disc ${n} from ${src} to ${dist}`);
    } else {
        toh(n - 1, src, temp, dist);
        console.log(`Move disc ${n} from ${src} to ${dist}`);
        toh(n - 1, temp, dist, src);
    }
}

const num = 3;
toh(num, "Source", "Destination", "Temporary");

Here's the TOH recursion tree for 4 disks:

Conclusion:

Recursion is a powerful tool in a developer's arsenal. However, it is essential to use it judiciously, keeping efficiency and readability in mind. Explore recursion by solving classic problems like Fibonacci, Tower of Hanoi, and tree traversals!

Recursion

On this page