RecursionLesson 1

Understanding Recursion

A function that calls itself. What recursion is, why it exists, and how to think about problems recursively.

What Is It?

Recursion is when a function calls itself.

That is the whole idea. A function that, while running, calls itself to solve a smaller version of the same problem.

Every recursive function needs two things:

Base case — the simplest version of the problem that can be solved directly, without calling itself. This is the "stop" condition.
Recursive case — where the function calls itself with a smaller input, making progress toward the base case.

If you forget the base case, the function calls itself forever and crashes — this is called a stack overflow.

Analogy

You are standing in a long line and you want to know what position you are in. You do not want to count every person yourself. So you ask the person in front: "What position are you in?" They do not know either, so they ask the person in front of them. This continues all the way to the front.

The person at the very front says: "I am position 1." That is the base case. The person behind them hears this and says: "Then I am position 2." The answer travels back through the line, each person adding 1, until it reaches you.

You solved a big problem by reducing it to a smaller one — and doing a tiny bit of work yourself (add 1).

Try It Yourself

How It Works

Example 1: Factorial

The factorial of n (written n!) is n × (n-1) × (n-2) × ... × 1.

So 4! = 4 × 3 × 2 × 1 = 24.

Recursive definition:

factorial(0) = 1 (base case — stop here)
factorial(n) = n × factorial(n-1) (recursive case — smaller problem)

pseudocode

function factorial(n):
    if n == 0:                        // base case
        return 1
    return n * factorial(n - 1)       // recursive case

Tracing factorial(4)

pseudocode

factorial(4)
  = 4 * factorial(3)
  = 4 * (3 * factorial(2))
  = 4 * (3 * (2 * factorial(1)))
  = 4 * (3 * (2 * (1 * factorial(0))))
  = 4 * (3 * (2 * (1 * 1)))     <- base case returns 1
  = 4 * (3 * (2 * 1))
  = 4 * (3 * 2)
  = 4 * 6
  = 24

Two phases:

Winding (going deeper): Each call waits for the next call to return.
Unwinding (coming back): Return values travel back up, and each waiting multiplication happens.

Winding

factorial(4) waits...
factorial(3) waits...
factorial(2) waits...
factorial(1) waits...
factorial(0) returns 1 (base case)

Going deeper — each call waits for the next

building up deferred multiplications

Unwinding

factorial(0) = 1
factorial(1) = 1 * 1 = 1
factorial(2) = 2 * 1 = 2
factorial(3) = 3 * 2 = 6
factorial(4) = 4 * 6 = 24

Coming back — return values propagate upward

deferred multiplications execute

Example 2: Countdown

pseudocode

function countdown(n):
    if n < 0:              // base case
        return
    print(n)
    countdown(n - 1)       // recursive case

Trace for countdown(5):

countdown(5)— prints 5, calls countdown(4)

countdown(4)— prints 4, calls countdown(3)

countdown(3)— prints 3, calls countdown(2)

countdown(2)— prints 2, calls countdown(1)

countdown(1)— prints 1, calls countdown(0)

countdown(0)— prints 0, calls countdown(-1)

countdown(-1)— n < 0, return (base case)

-1STOP

Each call reduces n by 1. When n goes below 0, the function stops.

The Leap of Faith

When you write recursive functions, do NOT try to trace every single call in your head. That gets exhausting fast.

Instead, use the leap of faith: assume the recursive call correctly solves the smaller problem. Use that result to solve the current problem.

For factorial:

I need factorial(n).
I trust that factorial(n-1) gives the right answer for n-1.
So factorial(n) = n × factorial(n-1). Done.

You do not need to mentally trace factorial(3), factorial(2), factorial(1), factorial(0). Just trust it works and focus on the current level.

Recursion vs a Loop

Iterative Factorial

result = 1
for i from 1 to n:
result = result * i
return result

Uses a loop to accumulate the result

explicit loop with running product

Recursive Factorial

if n == 0: return 1
return n * factorial(n - 1)

Function calls itself with a smaller input

self-referential with base case

Both produce the same result. Recursion is not magic — anything done with recursion can also be done with a loop. But some problems have a naturally recursive structure (like trees or divide-and-conquer) where recursion is much cleaner.

Examples

Sum of numbers from 1 to n

pseudocode

function sumTo(n):
    if n == 0:                    // base case
        return 0
    return n + sumTo(n - 1)       // recursive case
sumTo(4) = 4 + sumTo(3)
         = 4 + 3 + sumTo(2)
         = 4 + 3 + 2 + sumTo(1)
         = 4 + 3 + 2 + 1 + sumTo(0)
         = 4 + 3 + 2 + 1 + 0
         = 10

Fibonacci

The Fibonacci sequence is: 0, 1, 1, 2, 3, 5, 8, 13, ...

Each number is the sum of the two before it.

pseudocode

function fib(n):
    if n == 0: return 0    // base case 1
    if n == 1: return 1    // base case 2
    return fib(n - 1) + fib(n - 2)   // recursive case
fib(4) = fib(3) + fib(2)
       = (fib(2) + fib(1)) + (fib(1) + fib(0))
       = ((fib(1) + fib(0)) + 1) + (1 + 0)
       = ((1 + 0) + 1) + 1
       = 3

Note: this naive version is very slow for large n because it recalculates the same values over and over. We will fix this later with a technique called memoization.

Common Mistakes

Missing the base case. This is the most common recursion bug. Without it, the function calls itself forever and crashes.

Base case that does not cover all stopping conditions. For example, checking n == 0 but someone passes a negative number — the function blows past 0 and never stops. Check n <= 0 instead.

Recursive call does not make the problem smaller. If you call factorial(n) instead of factorial(n-1), you are not making progress and will loop forever.

Forgetting to return the recursive result. Writing factorial(n-1) instead of return n * factorial(n-1). The call happens but the result gets thrown away.

Best Practices

Write the base case first. Before thinking about recursion, handle the simplest input.
Check that each recursive call gets closer to the base case. n-1 is closer to 0 than n. A shorter string is closer to empty than the original.
Use the leap of faith. Trust the recursive call works. Focus only on the current level.
Test with the smallest inputs first. Does factorial(0) return 1? Does factorial(1) return 1? These catch base case bugs immediately.

DFS — Iterative The Call Stack