# 3.7 Recursion Primer

> A function that calls itself on a smaller problem until it reaches a base case. You need this for trees (Ch 6) and merge/quick sort (Ch 8).

Chapter: Simple Sorting & Searching · ~45 min · medium
URL: https://dsa.fetehadin.com/learn/recursion

## Mental model

Russian **matryoshka dolls**: to find the smallest doll you open a doll, and inside is… a smaller doll, which you open the same way. You stop when a doll doesn't open. That last doll is the **base case**.

### Two required parts

1. **Base case**: a small input you can answer directly, with no further calls (`n <= 1` → return 1).
2. **Recursive case**: solve the problem using the answer to a **smaller** version of itself (`n * factorial(n - 1)`). Each call must move **toward** the base case.

### The call stack

Every call gets its own **stack frame** (its own copy of `n`, its own return address). When `factorial(4)` calls `factorial(3)`, the first call **pauses** and waits. Frames pile up until the base case returns, then they **unwind** one by one, each finishing its multiplication.

That's why recursion uses **O(depth)** memory, and why a missing base case ends in a **stack overflow**.

### When to use it

Recursion shines when a problem naturally contains smaller copies of itself: **trees** (a subtree is a tree), **divide and conquer** sorts (merge and quick sort), and searching by halves.

## C++ code: recursion.cpp

```cpp
#include <iostream>
using namespace std;

int factorial(int n) {
    if (n <= 1) return 1;            // base case: stops the recursion
    return n * factorial(n - 1);     // recursive case: smaller problem
}

int bs(const int a[], int low, int high, int key) {
    if (low > high) return -1;               // base case 1: empty range
    int mid = (low + high) / 2;
    if (a[mid] == key) return mid;           // base case 2: found
    if (a[mid] < key) return bs(a, mid + 1, high, key);
    return bs(a, low, mid - 1, key);
}

void countDown(int n) {
    if (n == 0) { cout << "liftoff!\n"; return; }
    cout << n << " ";
    countDown(n - 1);
}

int main() {
    cout << "5! = " << factorial(5) << "\n";
    int a[] = {2, 5, 9, 14, 20, 27, 33, 41};
    cout << "bs(27) -> " << bs(a, 0, 7, 27) << "\n";
    cout << "bs(4)  -> " << bs(a, 0, 7, 4) << "\n";
    countDown(3);
}
```

Expected output:

```text
5! = 120
bs(27) -> 5
bs(4)  -> -1
3 2 1 liftoff!
```

## Complexity

| Case | Cost |
| --- | --- |
| factorial(n): time | O(n): n calls, O(1) work each |
| factorial(n): space | O(n) stack frames |
| recursive binary search: time | O(log n) |
| recursive binary search: space | O(log n) stack frames (iterative version: O(1)) |


Every recursive call uses a **stack frame**. Too deep (or no base case) means a stack overflow and a crash.

## Videos

- [Recursion (CS50 Shorts)](https://youtu.be/mz6tAJMVmfM) (CS50): CS50's short is the friendliest explanation of base case, recursive case and the call stack.
- [5 Simple Steps for Solving Any Recursive Problem](https://youtu.be/ngCos392W4w) (Reducible): A 5-step method for writing recursive functions. It pays off in Ch 6 and Ch 8.

## Exam lens

Likely questions:

- What is recursion? What are the two required parts of a recursive function?
- Trace `factorial(4)` showing the call stack.
- Write a recursive binary search function.
- What happens if a recursive function has no base case?

Common mistakes:

- No base case, or a base case that is never reached (e.g. `factorial(n + 1)`).
- Forgetting to `return` the recursive call's result (`bs(...)` instead of `return bs(...)`).
- Thinking recursion is always slower or always better. It trades stack memory for simpler code.

## Quick check

1. What does `f(3)` return?

```cpp
int f(int n) {
    if (n == 0) return 0;
    return n + f(n - 1);
}
```
   A. 3
   B. 5
   C. 6
   D. 0
   Answer: C. 3 + 2 + 1 + 0 = 6.

2. The base case of a recursive function…
   A. calls the function again
   B. stops the recursion with a direct answer
   C. is optional
   D. must be the last line
   Answer: B. Without it the calls never stop.

3. Calling `factorial(5)` creates at most how many frames on the stack at once?
   A. 1
   B. 5
   C. 6
   D. 120
   Answer: B. factorial(5) → (4) → (3) → (2) → (1). Five frames before unwinding.

4. Missing base case usually causes…
   A. a compile error
   B. a stack overflow at run time
   C. the wrong answer silently
   D. nothing
   Answer: B. Each call adds a frame until the stack memory runs out.

## Practice

**Trace by hand.** Trace `power(2, 4)` where `power(b, e)` returns 1 if e == 0, else `b * power(b, e - 1)`. Show the calls going down and the values coming back up.

Solution:

Down: power(2,4) → power(2,3) → power(2,2) → power(2,1) → power(2,0)

Up: power(2,0) = 1 → power(2,1) = 2 → power(2,2) = 4 → power(2,3) = 8 → power(2,4) = **16**


**Implement it.** Write recursive `sumArray(a, n)`, `reverseString(s, l, r)` and `fib(n)`. Which one is slow for n = 40 and why?

Hint: `fib(n) = fib(n-1) + fib(n-2)` recomputes the same values exponentially many times → O(2ⁿ).

```cpp
int sumArray(const int a[], int n) { return n == 0 ? 0 : a[n - 1] + sumArray(a, n - 1); }
void reverseString(string& s, int l, int r) { if (l >= r) return; swap(s[l], s[r]); reverseString(s, l + 1, r - 1); }
long long fib(int n) { return n < 2 ? n : fib(n - 1) + fib(n - 2); }   // exponential!
```


**Problems:**

- [Fibonacci Number](https://leetcode.com/problems/fibonacci-number/) (easy). Hint: Write it recursively first, then notice the repeated work.
- [Power of Two](https://leetcode.com/problems/power-of-two/) (easy). Hint: Base cases: n == 1 → true; n odd or n ≤ 0 → false. Recursive case: isPowerOfTwo(n / 2).
- [Reverse String](https://leetcode.com/problems/reverse-string/) (easy). Hint: Swap the ends, recurse on the inside. Base case — `l >= r`.

## Mastery checklist

- [ ] I can name the base case and recursive case of any recursive function.
- [ ] I can draw the call stack for factorial(4).
- [ ] I can write recursive binary search.
- [ ] I can explain stack overflow and the O(n) space of deep recursion.