Recursion

What if a function could solve a problem by asking a slightly simpler version of itself for help — over and over, until the answer is trivially obvious? That is recursion.

The developer Q&A platform "Stack Overflow" was named after exactly the crash that happens when a recursion never ends. That alone shows how important — and how common — this concept is in computer science.

The Self-Calling Function

The Matryoshka analogy breaks because in real life, no one "remembers" the context of the previous doll. In a program, each stack frame explicitly stores its own state (parameters, local variables) and actively waits for the result from the call below.

At peak depth, 5 stack frames exist simultaneously in memory, each with its own copy of n. When the base case returns, frames are removed one by one in reverse order — the so-called "unwinding."

def factorial(n):
    if n <= 1:              # Base case
        return 1
    return n * factorial(n - 1)  # Recursive case

print(factorial(5))  # Output: 120

The Base Case: Your Safety Net

The base case is the single most critical line in any recursive function. It defines WHEN the function stops calling itself and WHAT it returns at that point. Without a base case, the function calls itself infinitely — each call adds a stack frame until available memory is exhausted.

Imagine a circular maze with no exit signs. Without a marker, a person wanders endlessly in circles. Place a red marker at one specific spot with the instruction "When you see the red marker, stop walking" — and infinite wandering becomes a finite search. That marker is the base case.

# BROKEN — no base case
def countdown(n):
    print(n)
    countdown(n - 1)  # calls forever: 3, 2, 1, 0, -1, ...
# → RecursionError after ~1000 calls

# CORRECT — base case stops at 0
def countdown(n):
    if n <= 0:           # Base case
        print(0)
        return           # STOP
    print(n)
    countdown(n - 1)     # Recursive case

Where Loops Fail: Recursion for Hierarchies

Loops (for, while) excel at processing linear sequences: iterate through a list, count from 1 to n. But when the data structure itself is nested to unknown depth — folders within folders, HTML elements within elements, branches of a game tree — a simple loop cannot see deeper than one level.

You need to find all .pdf files on a hard drive. Checking each file in the top-level folder is easy. But some items are folders containing more files and folders, nested to unknown depth. The recursive approach: "Open the folder. Check each item. If it is a file, evaluate it. If it is a folder, apply the same procedure to it."

Interactive: Fibonacci Call Tree

Step through the call tree of fib(5). Observe how the function keeps calling itself until it reaches a base case — and how the results then travel back up the tree. Pay special attention to how often fib(2) and fib(3) are computed multiple times.