Back to Learning Area

Recursion

Recursion: the programming technique that looks simple until you understand it. And then too.

  • Fundamentals
  • 14 min
  • Beginner

Plain Language

This preview is in Plain Language. The whole portal is also available in Plain Language. You can change the language at the top. Or use the button below. Our Plain Language texts are AI-assisted and editorially reviewed. They follow the core principles of easy-to-read language, but they are not certified Easy Read: a review panel of people with learning difficulties does not test them.

Preview: Recursion

What is recursion?

A function can call itself. This is called recursion. Recursion means: the problem gets smaller and smaller. At some point, there is a simple answer. The function stops there.

The base case

Every recursion needs a base case. Base case means: the recursion ends here. Without a base case, the function calls itself forever. The program crashes.

Where recursion helps

Recursion helps with nested structures. Nested means: something is inside something else. For example: folders inside folders. A normal program can only search one level. Recursion can search all levels.

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 is how well known this crash is among programmers.

The Self-Calling Function

Definition

Recursion

Analogy

Recursion works like Matryoshka dolls: You open the largest doll and find a smaller one inside with a note: "Do the same with me." Each doll is handed to the next person, and this continues until someone reaches the smallest doll, which cannot be opened, and finds a number written on it — the base case. Then the number travels back up: each person takes the result, adds their own contribution, and passes it on.

The Matryoshka analogy breaks in two places. A set of dolls always has a smallest doll; a recursion without a base case lacks one, and the opening goes on forever until memory runs out or, as in Python, the recursion limit kicks in. And while a person simply remembers their contribution, in a program each stack frame has to explicitly store its state (parameters, local variables) while it waits for the result from the call below.

Example: Factorial (5!) — Descent and Return

  1. 1. factorial(5) calls factorial(4) — remembers 5 * ?
  2. 2. factorial(4) calls factorial(3) — remembers 4 * ?
  3. 3. factorial(3) calls factorial(2) — remembers 3 * ?
  4. 4. factorial(2) calls factorial(1) — remembers 2 * ?
  5. 5. factorial(1) reaches BASE CASE → returns 1
  6. 6. factorial(2) = 2 * 1 = 2
  7. 7. factorial(3) = 3 * 2 = 6
  8. 8. factorial(4) = 4 * 6 = 24
  9. 9. factorial(5) = 5 * 24 = 120

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."

Note

Python Code: Factorial

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 or, as in Python, a fixed recursion limit kicks in.

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.

Note

Countdown: Without vs. With 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

The difference is a single if check — but it decides between a working program and a crash. The base case must appear BEFORE the recursive call in the function body.

Caution

Common Mistake: Increasing the Recursion Limit

sys.setrecursionlimit(10000) does not add more memory. With endless recursion it only delays the crash, and a limit set too high can crash Python itself. If the recursion runs forever or the problem requires very deep recursion, the real fix is either a proper base case or switching to an iterative approach.

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."

Recursive (implicit stack)

def find_pdfs(folder): results = [] for item in os.listdir(folder): path = os.path.join(folder, item) if os.path.isfile(path) and path.endswith('.pdf'): results.append(path) elif os.path.isdir(path): results.extend(find_pdfs(path)) return results Shorter, reads like the problem description. Uses the call stack implicitly.

Iterative (explicit stack)

def find_pdfs_iterative(root): results = [] stack = [root] while stack: folder = stack.pop() for item in os.listdir(folder): path = os.path.join(folder, item) if os.path.isfile(path) and path.endswith('.pdf'): results.append(path) elif os.path.isdir(path): stack.append(path) return results Avoids Python's recursion limit for very deep directories.

Note

Recursion in the Wild

File Search Searching folder structures of unknown depth
HTML Parsing Traversing nested DOM elements
JSON Traversal Processing nested objects and arrays
Game Trees MinMax algorithm for chess, tic-tac-toe
Fractals Sierpinski triangle, Koch snowflake
Divide & Conquer Merge sort, quicksort, binary search

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 the fact that fib(3) is computed twice and fib(2) is called three times.

5 fib(5)
Step 1 / 13fib(5)
Controls
Steps

Note

Synthesis: Recursion Is Not Magic

Recursion is not magic — it is a disciplined delegation pattern: break the problem down, trust your future self to handle the smaller piece, and define the point where delegation stops.

In AI, recursion is everywhere: tree traversals, depth-first search (DFS), divide-and-conquer algorithms, and game-tree evaluation (MinMax) — all are built on the recursive principle.

Note

Key Takeaways

  1. Recursion = a function calls itself to reduce a problem to a smaller version of the same problem.
  2. Every recursive function needs two parts: the base case (when to stop) and the recursive case (how to continue).
  3. Without a base case: infinite calls → stack overflow (in Python: RecursionError). The base case is the safety net.
  4. Recursion is ideal for hierarchical problems (folders, trees, nested structures) where the depth is unknown.
  5. Recursion and iteration can solve the same problems, but recursion maps hierarchical problems more naturally.

Check

Quiz: Recursion

Not completed

What are the two essential parts of every recursive function?

Select one answer

Answer Key: 1) B · 2) C · 3) B · 4) B

Check

Checkpoint: Test Your Knowledge

Can you explain this in your own words? Tick what you've got.

0 of 3 done