Recursion

What you'll learn

• Write a function that calls itself and explain why that is allowed
• Identify the base case and the recursive case every recursion needs
• Trace a recursive call by hand and see the stack of pending calls
• Decide when recursion is clearer than a loop, and when it is not

Concept

A recursive function is one that calls itself. That sounds circular, and it would be, except that each call works on a smaller piece of the problem, and there is always a case small enough to answer directly. Counting down is the simplest example: to count down from 5, say 5, then count down from 4. To count down from 0, stop. The "stop" is the base case; the "count down from a smaller number" is the recursive case.

Every recursion has exactly those two parts, and forgetting the base case is the recursive version of the infinite loop. Python protects you: after about a thousand nested calls it raises a RecursionError instead of running forever. When you see that error, the base case is missing or never reached.

Recursion works because each call gets its own local variables, as you learned two lessons ago. Python keeps the pending calls on a stack: countdown(3) is paused while countdown(2) runs, which is paused while countdown(1) runs, and so on. When the base case returns, each paused call resumes where it left off, in reverse order. Tracing this once by hand, on paper, is the moment recursion stops being mysterious.

Recursion is the natural fit for problems that contain smaller copies of themselves: folders that contain folders, nested lists inside lists, tree-shaped data like JSON, and "divide the problem in half" algorithms. For a plain sequence, a loop is usually clearer and always faster, because every recursive call costs memory on that stack. The rule of thumb: if you would explain the solution as "and then do the same thing to the smaller part", recursion fits; if you would say "for each item", use a loop.

Code

The countdown, with the two cases labeled. Note that the base case comes first; checking it before recursing is the habit that prevents runaway calls.

# countdown.py
def countdown(n):
    if n == 0:            # base case
        print("liftoff")
        return
    print(n)
    countdown(n - 1)      # recursive case: a smaller problem

countdown(3)

3
2
1
liftoff

Factorial, where the result is built on the way back up. Each call waits for the smaller call's answer and multiplies it.

# factorial.py
def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

for n in range(0, 6):
    print(n, factorial(n))
print(factorial(20))

0 1
1 1
2 2
3 6
4 24
5 120
2432902008176640000

A problem that genuinely needs recursion: summing a list whose items may themselves be lists, to any depth. A loop cannot know how deep to go; recursion does not need to.

# nested_sum.py
def nested_sum(items):
    total = 0
    for item in items:
        if isinstance(item, list):
            total += nested_sum(item)
        else:
            total += item
    return total

print(nested_sum([1, 2, 3]))
print(nested_sum([1, [2, 3], [4, [5, 6]]]))
print(nested_sum([[[[7]]]]))

6
21
7

What a missing base case looks like. The traceback is long and repetitive, which is itself the clue: the same line keeps calling itself.

# no_base_case.py
import sys
sys.setrecursionlimit(50)   # fail fast for the demo; the default is 1000

def forever(n):
    return forever(n + 1)

forever(1)

Traceback (most recent call last):
  File "no_base_case.py", line 7, in <module>
    forever(1)
    ~~~~~~~^^^
  File "no_base_case.py", line 5, in forever
    return forever(n + 1)
  File "no_base_case.py", line 5, in forever
    return forever(n + 1)
  File "no_base_case.py", line 5, in forever
    return forever(n + 1)
  [Previous line repeated 46 more times]
RecursionError: maximum recursion depth exceeded

Try it yourself

Create recurse.py with two functions. count_down_up(n) prints n, recurses, then prints n again after the call returns, so count_down_up(3) prints 3 2 1 1 2 3 on separate lines; trace on paper why. depth(items) returns how deeply nested a list is: depth([1, 2]) is 1, depth([1, [2, [3]]]) is 3.

Common mistakes

• No base case, or one that is never reached. factorial(n) with the base case n == 0 loops forever for factorial(-1); use n <= 1.
• Forgetting to use the result of the recursive call. factorial(n - 1) on its own line computes the answer and throws it away; it must be returned or combined.
• Reaching for recursion on flat data. A loop over a list is clearer and does not risk the recursion limit; save recursion for nested shapes.

What's next

• A recursive function calls itself on a smaller problem and needs a base case that answers without recursing.
• Each call has its own locals and waits on the stack; results come back up in reverse order.
• Use recursion for self-similar data like nested lists and folder trees, and loops for flat sequences.

You have every tool for control flow now. Next you will learn to read the error messages that all of this code will inevitably produce, calmly and bottom-up.