🗓️ Day 16: Recursion

🧠 Concept Deep Dive

Recursion is a method of solving problems where a function calls itself.

A recursive function typically solves a small piece of the problem and delegates the rest to itself.

To be valid, every recursive function must follow two rules:

1. Base Case – the condition to stop recursion
2. Recursive Case – how the problem is reduced and the function calls itself

🛡️ Think Like a Stack

Each recursive call is added to the call stack, and the function pauses until the recursive call finishes. After reaching the base case, calls start unwinding from the stack.

📦 Stack Trace Example:

factorial(3)
-> 3 * factorial(2)
  -> 2 * factorial(1)
    -> 1 (base case)

🔁 Classic Recursion Pattern

function recurse(problem: Problem): ReturnType {
  if (baseCase(problem)) {
    return baseResult;
  }

  // reduce the problem
  return combine(
    currentWork,
    recurse(smallerProblem)
  );
}

💡 Example: Factorial

function factorial(n: number): number {
  if (n <= 1) return 1;         // base case
  return n * factorial(n - 1);  // recursive call
}

🔪 Example

Input: factorial(5)
Output: 120

Explanation:
5 * 4 * 3 * 2 * 1 = 120

💡 Example: Fibonacci

function fibonacci(n: number): number {
  if (n <= 1) return n;
  return fibonacci(n - 1) + fibonacci(n - 2);
}

🔪 Example

Input: fibonacci(6)
Output: 8

⚠️ Note: This has exponential time complexity. Use memoization (covered later) to improve.

🧠 Real-world Analogy

Recursion is like stacking dinner plates.

• Every plate you stack is like a function call.
• When you're done stacking (base case), you start removing them in reverse order — just like unwinding the recursive stack.

📊 Big O Complexity

🔪 LeetCode-style Homework

Problem: Reverse a String (recursive)

Write a function to reverse a string using recursion.

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

Example

Input: "hello"
Output: "olleh"

⚠️ Common Pitfalls

• Missing a base case causes infinite recursion (stack overflow)
• Forgetting to return the result of the recursive call
• Not reducing the problem each time

📆 Summary

• Recursion solves a big problem by breaking it into smaller versions of itself
• Every recursion needs a base case
• Stack memory is a major constraint
• Learn to visualize how recursion flows

🔮 Up Next

▶️ Day 17: Backtracking