Recursion - Full-Stack

1. Recursion Concepts

Definition of Recursion

Recursion is a programming technique where a function calls itself directly or indirectly to solve a problem by breaking it down into smaller, similar subproblems.

Base Case

The condition that stops the recursion. Without a base case, recursive functions would call themselves indefinitely, causing a stack overflow.

Base Case Example

function factorial(n) {
    // Base case: when n is 0 or 1
    if (n <= 1) {
        return 1;
    }
    // Recursive case
    return n * factorial(n - 1);
}

Recursive Case

The part of the function that calls itself with modified parameters, moving toward the base case.

Stack Behaviour

Each recursive call creates a new stack frame containing function parameters and local variables. Understanding stack behavior is crucial for debugging recursive functions.

Call Stack Visualization

factorial(5)

factorial(4)

factorial(3)

factorial(2)

factorial(1) ← Base Case

2. Recursion vs Iteration

Differences

Aspect	Recursion	Iteration
Approach	Function calls itself	Loops (for, while, do-while)
Termination	Base case condition	Loop condition
Memory Usage	Higher (uses call stack)	Lower (uses variables)
Readability	Elegant for certain problems	Straightforward for simple loops

Advantages of Recursion

Elegant solution for problems with recursive structure
Reduces code length for tree/graph traversals
Natural fit for divide-and-conquer algorithms
Easier to implement for backtracking problems

When to Use Recursion

Tree and graph traversals
Divide and conquer algorithms (Merge Sort, Quick Sort)
Backtracking problems (N-Queens, Sudoku)
Problems with mathematical recursive definitions

Limitations

Stack overflow for deep recursion
Higher memory usage
Slower due to function call overhead
Difficult to debug for beginners

3. Classic Recursion Problems

Factorial

n! = n × (n-1) × (n-2) × ... × 1

Recursive Factorial Implementation

function factorial(n) {
    // Base case
    if (n <= 1) return 1;
    
    // Recursive case
    return n * factorial(n - 1);
}

// Example: factorial(5) = 5 * 4 * 3 * 2 * 1 = 120

Fibonacci Sequence

F(n) = F(n-1) + F(n-2), where F(0) = 0, F(1) = 1

Recursive Fibonacci Implementation

function fibonacci(n) {
    // Base cases
    if (n <= 0) return 0;
    if (n === 1) return 1;
    
    // Recursive case
    return fibonacci(n - 1) + fibonacci(n - 2);
}

// Example: fibonacci(7) = 13

Tower of Hanoi

Mathematical puzzle with three rods and n disks of different sizes.

Recursive Tower of Hanoi Solution

function towerOfHanoi(n, source, auxiliary, destination) {
    if (n === 1) {
        console.log(`Move disk 1 from ${source} to ${destination}`);
        return;
    }
    
    towerOfHanoi(n - 1, source, destination, auxiliary);
    console.log(`Move disk ${n} from ${source} to ${destination}`);
    towerOfHanoi(n - 1, auxiliary, source, destination);
}

// Example: Move 3 disks from rod A to rod C
towerOfHanoi(3, 'A', 'B', 'C');

Tree/Array Traversals

Binary Tree In-order Traversal

class TreeNode {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

function inorderTraversal(root) {
    const result = [];
    
    function traverse(node) {
        if (node === null) return; // Base case
        
        traverse(node.left);     // Recursive left
        result.push(node.value); // Process node
        traverse(node.right);    // Recursive right
    }
    
    traverse(root);
    return result;
}