Day 5: Recursion & Divide and Conquer

What You'll Learn Today

• Fundamentals of recursion and the call stack
• Base cases and recursive cases
• The divide and conquer paradigm
• Practical recursive algorithms

---

What Is Recursion?

Recursion is when a function calls itself. It breaks a large problem into smaller subproblems of the same structure.

flowchart TB
    subgraph Recursion["Recursion Flow"]
        F5["factorial(5)"] --> F4["5 × factorial(4)"]
        F4 --> F3["4 × factorial(3)"]
        F3 --> F2["3 × factorial(2)"]
        F2 --> F1["2 × factorial(1)"]
        F1 --> BASE["1 (base case)"]
    end
    style Recursion fill:#3b82f6,color:#fff
    style BASE fill:#22c55e,color:#fff

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

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

---

Two Essential Components

Every recursive function needs:

1. Base Case

The condition that stops the recursion. Without it, you get infinite recursion.

2. Recursive Case

The part that reduces the problem and calls itself.

function countdown(n) {
  if (n <= 0) {
    console.log("Done!");
    return;
  }
  console.log(n);
  countdown(n - 1);
}

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

---

The Call Stack

Each recursive call is pushed onto the call stack. When the base case is reached, return values propagate back up.

flowchart TB
    subgraph CallStack["Call Stack"]
        direction TB
        S1["factorial(1) → 1"]
        S2["factorial(2) → 2 × 1"]
        S3["factorial(3) → 3 × 2"]
        S4["factorial(4) → 4 × 6"]
        S5["factorial(5) → 5 × 24"]
    end
    S5 --> S4 --> S3 --> S2 --> S1
    S1 -.->|return 1| S2
    S2 -.->|return 2| S3
    S3 -.->|return 6| S4
    S4 -.->|return 24| S5
    style CallStack fill:#8b5cf6,color:#fff

Stack Overflow

Too-deep recursion causes a stack overflow.

// This will crash!
function infinite() {
  return infinite();
}
// RangeError: Maximum call stack size exceeded

---

Common Recursive Patterns

Sum of an Array

function sum(arr) {
  if (arr.length === 0) return 0;
  return arr[0] + sum(arr.slice(1));
}

console.log(sum([1, 2, 3, 4, 5])); // 15

String Reversal

function reverse(str) {
  if (str.length <= 1) return str;
  return reverse(str.slice(1)) + str[0];
}

console.log(reverse("hello")); // "olleh"

Exponentiation

// O(n) version
function power(base, exp) {
  if (exp === 0) return 1;
  return base * power(base, exp - 1);
}

// O(log n) version using divide and conquer
function fastPower(base, exp) {
  if (exp === 0) return 1;
  if (exp % 2 === 0) {
    const half = fastPower(base, exp / 2);
    return half * half;
  }
  return base * fastPower(base, exp - 1);
}

console.log(fastPower(2, 10)); // 1024

---

Divide and Conquer

Divide and conquer solves problems in three steps:

flowchart TB
    P["Problem"] --> D["1. Divide\nBreak into subproblems"]
    D --> C["2. Conquer\nSolve recursively"]
    C --> M["3. Combine\nMerge results"]
    style P fill:#3b82f6,color:#fff
    style D fill:#22c55e,color:#fff
    style C fill:#f59e0b,color:#fff
    style M fill:#8b5cf6,color:#fff

Example: Merge Sort

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

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

  const sortedLeft = mergeSort(left);
  const sortedRight = mergeSort(right);

  return merge(sortedLeft, sortedRight);
}

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

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

  return [...result, ...left.slice(i), ...right.slice(j)];
}

console.log(mergeSort([38, 27, 43, 3, 9, 82, 10]));
// [3, 9, 10, 27, 38, 43, 82]

flowchart TB
    A["[38, 27, 43, 3, 9, 82, 10]"] --> B["[38, 27, 43]"]
    A --> C["[3, 9, 82, 10]"]
    B --> D["[38]"]
    B --> E["[27, 43]"]
    E --> F["[27]"]
    E --> G["[43]"]
    C --> H["[3, 9]"]
    C --> I["[82, 10]"]
    H --> J["[3]"]
    H --> K["[9]"]
    I --> L["[82]"]
    I --> M["[10]"]
    F -.-> N["[27, 43]"]
    G -.-> N
    D -.-> O["[27, 38, 43]"]
    N -.-> O
    J -.-> P["[3, 9]"]
    K -.-> P
    L -.-> Q["[10, 82]"]
    M -.-> Q
    P -.-> R["[3, 9, 10, 82]"]
    Q -.-> R
    O -.-> S["[3, 9, 10, 27, 38, 43, 82]"]
    R -.-> S
    style A fill:#3b82f6,color:#fff
    style S fill:#22c55e,color:#fff

---

Binary Search (Divide and Conquer)

function binarySearch(arr, target, left = 0, right = arr.length - 1) {
  if (left > right) return -1;

  const mid = Math.floor((left + right) / 2);

  if (arr[mid] === target) return mid;
  if (arr[mid] < target) {
    return binarySearch(arr, target, mid + 1, right);
  }
  return binarySearch(arr, target, left, mid - 1);
}

const sorted = [1, 3, 5, 7, 9, 11, 13, 15];
console.log(binarySearch(sorted, 7));  // 3
console.log(binarySearch(sorted, 6));  // -1

---

Recursion vs. Iteration

Every recursive solution can be rewritten as an iterative one.

// Recursive fibonacci: O(2ⁿ)
function fibRecursive(n) {
  if (n <= 1) return n;
  return fibRecursive(n - 1) + fibRecursive(n - 2);
}

// Iterative fibonacci: O(n)
function fibIterative(n) {
  if (n <= 1) return n;
  let prev = 0, curr = 1;
  for (let i = 2; i <= n; i++) {
    [prev, curr] = [curr, prev + curr];
  }
  return curr;
}

// Memoized fibonacci: O(n)
function fibMemo(n, memo = {}) {
  if (n <= 1) return n;
  if (memo[n]) return memo[n];
  memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
  return memo[n];
}

Approach	Time	Space
Naive recursion	O(2ⁿ)	O(n)
Memoized recursion	O(n)	O(n)
Iteration	O(n)	O(1)

---

Tail Recursion

Tail recursion is when the recursive call is the very last operation. Some languages optimize this.

// Not tail recursive
function factorial(n) {
  if (n <= 1) return 1;
  return n * factorial(n - 1);
}

// Tail recursive
function factorialTail(n, acc = 1) {
  if (n <= 1) return acc;
  return factorialTail(n - 1, n * acc);
}

---

Summary

Concept	Description
Recursion	A function calling itself
Base Case	Condition that stops recursion
Call Stack	Stack where recursive calls accumulate
Divide & Conquer	Divide → Conquer → Combine
Memoization	Caching results to avoid redundant computation

Key Takeaways

1. Every recursion needs a base case and a recursive case
2. Divide and conquer splits problems into divide → conquer → combine
3. Memoization can reduce exponential time to linear
4. Too-deep recursion causes stack overflow

---

Practice Problems

Problem 1: Basic

Implement a recursive function to find the maximum value in an array.

Problem 2: Intermediate

Implement a recursive function to check whether a string is a palindrome.

Challenge

Implement a recursive function to generate all subsets (power set) of an array with N elements.

---

References

• MDN - Recursion
• Wikipedia - Divide and conquer
• Wikipedia - Merge sort

---

Next up: In Day 6, we'll explore "Sorting Algorithms" — comparing the mechanics and performance of major sorting algorithms.