Recursion Fundamentals

0/12 in this phase0/57 across the roadmap

📖 Concept

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

Base case — The simplest case that can be answered directly (stops the recursion)
Recursive case — Break the problem into a smaller sub-problem and call itself

Why it matters: Recursion is the foundation of trees, graphs, dynamic programming, backtracking, divide & conquer — most of DSA. If you don't master recursion, you can't solve 60%+ of interview problems.

How recursion works internally:

Each function call creates a new stack frame on the call stack
The frame stores: local variables, parameters, return address
When base case is hit, frames start unwinding (returning values back up)
If no base case is reached → stack overflow (infinite recursion)

The three laws of recursion:

Must have a base case
Must move toward the base case (problem gets smaller)
Must call itself

Recursion vs the call stack:

factorial(4)
  → 4 * factorial(3)          ← stack frame 1
       → 3 * factorial(2)      ← stack frame 2
            → 2 * factorial(1)  ← stack frame 3
                 → return 1     ← base case hit!
            → return 2 * 1 = 2  ← unwind
       → return 3 * 2 = 6      ← unwind
  → return 4 * 6 = 24          ← unwind

Patterns for thinking recursively:

Leap of faith — Assume the recursive call works correctly. Focus only on: what do I do with the result?
Identify the sub-problem — How is this problem a smaller version of itself?
Identify the base case — What's the simplest input I can answer immediately?

🏠 Real-world analogy: Russian nesting dolls (matryoshka). To find the smallest doll, you open each one until you find one that doesn't contain another (base case). Then you close them back up (unwinding).

💻 Code Example

codeTap to expand ⛶

1// FACTORIAL — The classic recursive example
2function factorial(n) {
3  if (n <= 1) return 1;        // Base case
4  return n * factorial(n - 1); // Recursive case
5}
6// factorial(5) = 5 * 4 * 3 * 2 * 1 = 120
7
8// FIBONACCI — Two recursive calls
9function fibonacci(n) {
10  if (n <= 0) return 0;        // Base case 1
11  if (n === 1) return 1;       // Base case 2
12  return fibonacci(n - 1) + fibonacci(n - 2); // Two sub-problems
13}
14// ⚠️ Time: O(2ⁿ) — very slow! We'll optimize later with DP
15
16// SUM OF ARRAY — Recursion on arrays
17function sumArray(arr, index = 0) {
18  if (index === arr.length) return 0;           // Base case
19  return arr[index] + sumArray(arr, index + 1); // Process one, recurse rest
20}
21
22// REVERSE A STRING — Recursion on strings
23function reverseStr(str) {
24  if (str.length <= 1) return str;  // Base case
25  return reverseStr(str.slice(1)) + str[0]; // Last char + reverse rest
26}
27
28// POWER — O(log n) using recursion
29function power(base, exp) {
30  if (exp === 0) return 1;
31  if (exp % 2 === 0) {
32    const half = power(base, exp / 2);
33    return half * half;  // Only recurse once, square the result
34  }
35  return base * power(base, exp - 1);
36}
37// power(2, 10) — only ~4 calls instead of 10!
38
39// TypeScript — recursive type for nested arrays
40function flatten<T>(arr: (T | T[])[]): T[] {
41  const result: T[] = [];
42  for (const item of arr) {
43    if (Array.isArray(item)) {
44      result.push(...flatten(item)); // Recursive call
45    } else {
46      result.push(item);
47    }
48  }
49  return result;
50}
51
52// COUNT DOWN — simplest recursion to build intuition
53function countDown(n: number): void {
54  if (n <= 0) {
55    console.log("Done!");
56    return; // Base case
57  }
58  console.log(n);
59  countDown(n - 1); // Recursive case — smaller input
60}

🏋️ Practice Exercise

Practice Problems (Easy → Hard):

Write a recursive function to calculate the sum of digits of a number
Write a recursive function to check if a string is a palindrome
Calculate power(base, exp) recursively in O(log n) time
Count the number of occurrences of a character in a string recursively
Write a recursive binary search
Implement a recursive function to find the GCD of two numbers (Euclidean)
Recursively generate all subsets of an array
Flatten a deeply nested array recursively
Implement Tower of Hanoi (3 pegs, n disks)
Write a recursive function to check if an array is sorted

Debugging Exercise:

// This causes stack overflow — why?
function badRecursion(n) {
  if (n === 0) return 0;
  return badRecursion(n - 2); // Bug: skips 0 when n is odd!
}
badRecursion(5); // 5 → 3 → 1 → -1 → -3 → ... 💥

⚠️ Common Mistakes

Missing or wrong base case — leads to infinite recursion and stack overflow
Not moving toward the base case — recursive call must make the problem SMALLER
Forgetting that each recursive call uses stack space — O(n) recursion depth = O(n) space
Using recursion when iteration is simpler (factorial, fibonacci) — not everything needs recursion
Not using the 'leap of faith' — trying to trace every recursive call instead of trusting the recursive step

💼 Interview Questions

🎤 Mock Interview

Practice a live interview for Recursion Fundamentals

Was this topic helpful?

← PreviousAmortized Analysis Next →Call Stack & Memory Model (Stack vs Heap)