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.

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.

2. Recursion vs Iteration

Differences

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

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

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

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

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;
}