What is recursion and when is it useful? Recursion क्या है और कब useful है?

Recursion is a programming technique where a function calls itself to solve a problem by breaking it down into smaller subproblems. The function must have a base case to stop recursion.

// Factorial - classic recursion example
function factorial(n) {
    // Base case - stops recursion
    if (n <= 1) return 1;
    
    // Recursive case - function calls itself
    return n * factorial(n - 1);
}

console.log(factorial(5)); // 5 * 4 * 3 * 2 * 1 = 120

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

console.log(fib(6)); // 8

// Tree traversal - very useful for recursion
const tree = {
    value: 1,
    left: {
        value: 2,
        left: { value: 4 },
        right: { value: 5 }
    },
    right: {
        value: 3,
        left: { value: 6 },
        right: { value: 7 }
    }
};

function traverse(node) {
    if (!node) return;
    console.log(node.value);
    traverse(node.left);
    traverse(node.right);
}

traverse(tree); // 1, 2, 4, 5, 3, 6, 7

// Problem with recursion: Performance
// fib(40) will be VERY slow because of repeated calculations

// Solution 1: Memoization (caching)
function fibMemo(n, memo = {}) {
    if (memo[n]) return memo[n];
    if (n <= 1) return n;
    
    memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
    return memo[n];
}

console.log(fibMemo(40)); // Much faster!

// Solution 2: Dynamic Programming (bottom-up)
function fibDP(n) {
    if (n <= 1) return n;
    
    const dp = [0, 1];
    for (let i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

// Deep copy using recursion
function deepCopy(obj) {
    if (obj === null || typeof obj !== 'object') return obj;
    if (Array.isArray(obj)) {
        return obj.map(item => deepCopy(item));
    }
    
    const copy = {};
    for (let key in obj) {
        copy[key] = deepCopy(obj[key]);
    }
    return copy;
}

Interview tip: Always mention the base case when explaining recursion. Discuss the performance implications (stack overflow on deep recursion) and mention optimization techniques like memoization or converting to iteration. Explain when recursion is natural and elegant (tree/graph traversal) versus when iteration is better (linear problems).