functions~14 minRoute 01 9 of 12

Recursion

A function that calls itself — the matryoshka pattern.

Prerequisites:Functions Conditions & Booleans

Story — the matryoshka doll

A matryoshka is a wooden doll. Inside each one is a smaller doll. And inside that, an even smaller one. Eventually you reach the tiniest doll — solid wood. That tiny doll is the base case: the place where opening stops.

Recursion is a function that solves a problem by calling itself on a smaller version of the same problem — and trusts that smaller call to come back with the answer. The base case is what stops the unwrapping. Without it, you'd open forever.

Reka says

Two parts, always: the base case (a doll that doesn't open) and the recursive case (open this one, ask the next one). Forget the base case and you get a stack overflow — the function calls itself until the runtime gives up.

See it — the call stack going down and coming up

Pick n and press Start, then Step to watch the stack grow as the function calls itself, hit the base case, and unwind back up — each frame multiplying on its way home.

Call stack — top is the active frame

(idle — press Start)

n =

✎ Sharpen your pencil

After watching factorial(4) run, write one sentence describing why all four frames have to wait around until the base case returns.

Reka says

Watch the stack grow as we call deeper, then collapse as the base case fires and each frame returns.

Try it — predict the order

Exercise. Imagine factorial(5). How many different stack frames exist at the deepest point?

Reveal answer

Five. factorial(5) calls factorial(4), which calls factorial(3), … all the way to factorial(1). All five frames live on the stack at once until factorial(1) hits the base case and they collapse one by one. That stack-of-pending-work IS the cost of recursion.

Code it — five languages, one self-call

The pattern is identical in every language: an if for the base case, and a return that calls the function on a smaller input. Read each one and notice the shape repeats.

def factorial(n):
    if n == 1:        # base case
        return 1
    return n * factorial(n - 1)  # recursive case

print(factorial(4))  # 24

Walk through it line by line

Step 1 / 6python

1def factorial(n):
2    if n == 1:
3        return 1
4    return n * factorial(n - 1)
5 
6result = factorial(3)

Reka says

Forget the base case and the function calls itself forever — until the runtime kills it. "RecursionError: maximum recursion depth exceeded" is your first warning.

Quiz it — make it stick

Question 1
What two pieces does every recursive function need?
A loop and an arrayA base case and a recursive caseA return statement and a printA class and a constructor

Predict — Question 2

What does this print?

def count_down(n):
    if n == 0:
        return
    print(n)
    count_down(n - 1)

count_down(3)

Your guess

True or false — Question 3
A recursive function is always slower than its loop equivalent.

No Dumb Questions

Real questions other learners asked on this page.

Is recursion always the right way to solve a problem?
No. Use it when the problem has the same shape at smaller sizes — trees, file systems, mazes, divide-and-conquer algorithms. For straight iteration over a list, a loop is usually clearer and avoids stack overhead.
What is tail recursion?
A recursive call where nothing happens after it returns — the recursive call IS the return. Some languages (Scheme, OCaml, Scala) optimize tail calls into loops, so they use no extra stack. Python and JavaScript do not, so deep recursion in those languages can still overflow.
How deep can recursion go?
Depends on the language and platform. Python defaults to 1000. Java is around 10,000–25,000 depending on heap size. JavaScript is browser-dependent. If you need deeper, either rewrite as a loop or use an explicit stack data structure.