🔄 JavaScript Recursion Basics

Parent: Recursion & Backtracking Index

---

What is Recursion?

Recursion is when a function calls itself to solve a smaller version of the same problem. Every recursive solution has two parts:

1. Base Case — The condition that stops the recursion
2. Recursive Case — The function calls itself with a smaller input

function countdown(n) {
    // Base case — stop here
    if (n <= 0) {
        console.log("Done!");
        return;
    }

    console.log(n);

    // Recursive case — smaller input (n-1)
    countdown(n - 1);
}

countdown(5);
// Output: 5, 4, 3, 2, 1, Done!

---

How the Call Stack Works

Every function call gets its own stack frame. Frames pile up until the base case is hit, then they unwind:

countdown(3) called
  └─ countdown(2) called
       └─ countdown(1) called
            └─ countdown(0) called → "Done!" → returns
            countdown(1) returns
       countdown(2) returns
  countdown(3) returns

Maximum call stack exceeded is JavaScript's stack overflow. Default limit is ~10,000–15,000 frames. Always ensure the base case is reachable.

---

Q1. Factorial

Problem: Compute n! = n × (n-1) × ... × 1

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

n! = n × (n-1)! — reduces to a smaller version of itself.

Step 2 — Base case: 0! = 1, 1! = 1

Step 3 — Recursive case: factorial(n) = n × factorial(n-1)

Step 4 — Edge cases:

- n=0: return 1 (0! defined as 1)

function factorial(n) {
    // Base case
    if (n <= 1) return 1;

    // Recursive case
    return n * factorial(n - 1);
}

// Call stack for factorial(4):
// 4 * factorial(3)
//      3 * factorial(2)
//           2 * factorial(1) = 1  ← base case
//           = 2
//      = 6
// = 24

console.log(factorial(5));   // 120
console.log(factorial(0));   // 1
console.log(factorial(10));  // 3628800

Time: O(n) | Space: O(n) — n frames on call stack

---

Q2. Fibonacci Number

Problem: Return the nth Fibonacci number. F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)

---

🧠 How to Approach This

Step 1 — Naive approach:

Direct recursion → O(2ⁿ) — recalculates the same values millions of times.

Step 2 — Memoization (Top-down DP):

Store computed values in a Map. fib(30) computed only once.

Step 3 — Bottom-up (best for space):

Build from F(0), F(1) up to F(n) iteratively.

Step 4 — Edge cases:

- n=0 → 0, n=1 → 1

// ── Naive — O(2ⁿ) — DO NOT USE for large n ──
function fibNaive(n) {
    if (n <= 1) return n;
    return fibNaive(n - 1) + fibNaive(n - 2);
}

// ── Memoized — O(n) time, O(n) space ──
function fib(n, memo = new Map()) {
    if (n <= 1) return n;
    if (memo.has(n)) return memo.get(n);

    const result = fib(n - 1, memo) + fib(n - 2, memo);
    memo.set(n, result);
    return result;
}

// ── Bottom-up DP — O(n) time, O(1) space (best) ──
function fibDP(n) {
    if (n <= 1) return n;
    let a = 0, b = 1;
    for (let i = 2; i <= n; i++) {
        [a, b] = [b, a + b];
    }
    return b;
}

console.log(fib(10));    // 55
console.log(fib(40));    // 102334155
console.log(fibDP(50));  // 12586269025

Time: O(n) memoized | Space: O(n)

---

Q3. Sum of 1 to N

Problem: Compute 1 + 2 + ... + n using recursion.

---

🧠 How to Approach This

Step 1: sum(n) = n + sum(n-1). Base case: sum(0) = 0

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

// O(1) math formula (best!)
const sumFormula = n => (n * (n + 1)) / 2;

console.log(sumN(10));          // 55
console.log(sumFormula(100));   // 5050

Time: O(n) | Space: O(n)

---

Q4. Power (Fast Exponentiation)

Problem: Compute x^n. Handle negative exponents. O(log n).

---

🧠 How to Approach This

Step 1 — Key insight: x^n = (x^(n/2))² — cuts n in half each call.

Step 2 — Even n: return half * half

Odd n: return x half half

function myPow(x, n) {
    if (n === 0) return 1;
    if (n < 0)   return 1 / myPow(x, -n);

    const half = myPow(x, Math.floor(n / 2));

    return n % 2 === 0
        ? half * half          // Even
        : x * half * half;     // Odd
}

console.log(myPow(2, 10));   // 1024
console.log(myPow(2, -2));   // 0.25
console.log(myPow(3, 5));    // 243

Time: O(log n) | Space: O(log n)

---

Q5. Reverse a String Using Recursion

Problem: Reverse a string using recursion.

---

🧠 How to Approach This

Step 1: reverseStr("hello") = reverseStr("ello") + "h"

function reverseStr(s) {
    if (s.length <= 1) return s;         // Base case
    return reverseStr(s.slice(1)) + s[0]; // Recursive case
}

// In-place with two pointers (more efficient)
function reverseInPlace(chars, left = 0, right = chars.length - 1) {
    if (left >= right) return;
    [chars[left], chars[right]] = [chars[right], chars[left]];
    reverseInPlace(chars, left + 1, right - 1);
}

console.log(reverseStr("hello"));    // "olleh"
console.log(reverseStr("recursion")); // "noisrucer"

Time: O(n) | Space: O(n)

---

Q6. Check Palindrome (Recursive)

Problem: Check if a string is a palindrome using recursion.

---

🧠 How to Approach This

Step 1: First char == last char? Recurse on inner portion.

function isPalindrome(s, left = 0, right = s.length - 1) {
    if (left >= right) return true;          // Base case: pointers met
    if (s[left] !== s[right]) return false;  // Mismatch
    return isPalindrome(s, left + 1, right - 1);
}

console.log(isPalindrome("racecar")); // true
console.log(isPalindrome("hello"));   // false
console.log(isPalindrome("abba"));    // true

Time: O(n) | Space: O(n)

---

Q7. Sum of Digits

Problem: Sum the digits of a number recursively.

---

🧠 How to Approach This

Step 1: Peel last digit: sumDigits(1234) = 4 + sumDigits(123)

function sumDigits(n) {
    n = Math.abs(n);
    if (n < 10) return n;
    return (n % 10) + sumDigits(Math.floor(n / 10));
}

console.log(sumDigits(1234)); // 10
console.log(sumDigits(9999)); // 36

Time: O(log n) | Space: O(log n)

---

Recursion vs Iteration

// Sum 1..n — Three approaches

// ITERATIVE — O(n) time, O(1) space
function sumIterative(n) {
    let sum = 0;
    for (let i = 1; i <= n; i++) sum += i;
    return sum;
}

// RECURSIVE — O(n) time, O(n) space
function sumRecursive(n) {
    if (n <= 0) return 0;
    return n + sumRecursive(n - 1);
}

// FORMULA — O(1) time, O(1) space (best!)
const sumFormula = n => (n * (n + 1)) / 2;

---

Common Mistakes in JS