Recursion-in-JS.md

What is recursion in JavaScript ?

Recursion is a programming concept where a function calls itself in order to solve a problem. A recursive function is defined by two key components:

1. Base Case: The condition that stops the recursion. Without a base case, the function will call itself indefinitely, leading to a stack overflow error.
2. Recursive Case: The part of the function where it calls itself with a smaller or simpler input, moving closer to the base case.

How Recursion Works

When a recursive function is called, it performs some task and then calls itself with modified input. Each function call is added to the call stack, and execution proceeds until the base case is met. Once the base case is reached, the function starts returning values, and the call stack unwinds.

Example: Factorial of a Number

The factorial of a number ( n ) is the product of all positive integers less than or equal to ( n ). For example:

[ 5! = 5 \times 4 \times 3 \times 2 \times 1 = 120 ]

A recursive implementation of factorial in JavaScript:

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

console.log(factorial(5)); // 120

Explanation:

1. factorial(5) calls factorial(4).
2. factorial(4) calls factorial(3).
3. This continues until factorial(1) is reached, which returns 1 (base case).
4. The call stack then unwinds, calculating the result step-by-step.

Key Concepts in Recursion

1. Base Case: Essential for stopping the recursion and avoiding infinite loops.
2. Call Stack: Each recursive call is added to the call stack, and JavaScript processes them in a "last in, first out" (LIFO) order.
3. Depth of Recursion: Recursion depth should be managed carefully to prevent stack overflow.

Applications of Recursion

Recursion is commonly used in problems that can be broken into smaller subproblems, such as:

1. Traversing Data Structures

Recursion is ideal for traversing trees and graphs.

Example: Summing Nodes in a Binary Tree

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

function sumTree(root) {
    if (root === null) {
        return 0;
    }
    return root.value + sumTree(root.left) + sumTree(root.right);
}

const root = new Node(5);
root.left = new Node(3);
root.right = new Node(8);

console.log(sumTree(root)); // 16

2. Sorting Algorithms

Many sorting algorithms, like Merge Sort and Quick Sort, use recursion.

Example: Merge Sort

function mergeSort(arr) {
    if (arr.length <= 1) {
        return arr;
    }

    const mid = Math.floor(arr.length / 2);
    const left = mergeSort(arr.slice(0, mid));
    const right = mergeSort(arr.slice(mid));

    return merge(left, right);
}

function merge(left, right) {
    let result = [], i = 0, j = 0;

    while (i < left.length && j < right.length) {
        if (left[i] < right[j]) {
            result.push(left[i]);
            i++;
        } else {
            result.push(right[j]);
            j++;
        }
    }

    return result.concat(left.slice(i)).concat(right.slice(j));
}

console.log(mergeSort([4, 2, 7, 1, 3])); // [1, 2, 3, 4, 7]

3. Solving Mathematical Problems

Recursion is often used for problems like the Fibonacci sequence, Tower of Hanoi, and Greatest Common Divisor (GCD).

Example: Fibonacci Sequence

function fibonacci(n) {
    if (n === 0) {
        return 0;
    }
    if (n === 1) {
        return 1;
    }
    return fibonacci(n - 1) + fibonacci(n - 2);
}

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

Advantages of Recursion

• Simplifies code for problems that have a natural recursive structure.
• Useful for traversing hierarchical data (e.g., trees, graphs).

Disadvantages of Recursion

• Can lead to stack overflow if the base case is not reached or recursion depth is too large.
• Often less efficient due to function call overhead and potential for repeated calculations (unless optimized with techniques like memoization).

Optimizing Recursive Functions

1. Tail Recursion

A tail-recursive function performs its recursive call as the last operation. This allows some JavaScript engines to optimize recursion and avoid stack overflow.

Example:

function tailFactorial(n, acc = 1) {
    if (n === 0) {
        return acc;
    }
    return tailFactorial(n - 1, acc * n);
}

console.log(tailFactorial(5)); // 120

2. Memoization

Caching results of previous function calls to avoid redundant calculations.

Example:

function fibonacciMemoized(n, memo = {}) {
    if (n in memo) {
        return memo[n];
    }
    if (n === 0) {
        return 0;
    }
    if (n === 1) {
        return 1;
    }
    memo[n] = fibonacciMemoized(n - 1, memo) + fibonacciMemoized(n - 2, memo);
    return memo[n];
}

console.log(fibonacciMemoized(50)); // 12586269025

Summary

• Recursion is a technique where a function calls itself to solve smaller instances of a problem.
• It requires a well-defined base case and recursive case.
• Recursion is widely used for traversing data structures, implementing algorithms, and solving mathematical problems.
• Optimizations like tail recursion and memoization can improve efficiency and prevent stack overflow.