Base Case, Recursive Case and the Call Stack

18 min · Intermediate

A recursive function solves a problem by solving a smaller copy of the same problem. Two parts keep it correct: a base case that stops the chain and a recursive case that shrinks the input. Python also keeps a call stack that records the waiting calls.

A function that calls itself

Recursion is when a function solves a problem by calling itself on a smaller version of the same problem, until the problem is small enough to answer directly.

A countdown prints a number, then needs the countdown from the number below it. A function can do that by calling itself with a smaller number.

Python

1def countdown(n):2    if n == 0:3        print("Go!")4        return5    print(n)6    countdown(n - 1)7
8
9countdown(3)

Example 1 · Before or after the call

Python

1def show(n):2    if n == 0:3        return4    print("down", n)5    show(n - 1)6    print("up", n)7
8
9show(3)

Output

down 3
down 2
down 1
up 1
up 2
up 3

What this code does

Lines before the recursive call run on the way down.
Lines after it run on the way back up, in reverse order.

Each call handles one number and hands the rest to a new call. The call with 0 ends the chain.

Base case and recursive case

Base case and recursive case are the two parts of every recursive function. The base case returns an answer with no further call. The recursive case calls the function again on a smaller input.

The total of the first n orders is n plus the total of the first n - 1. That chain needs a place to stop.

Python

1def total_to(n):2    if n == 0:3        return 04    return n + total_to(n - 1)5
6
7print(total_to(4))

Example 2 · Factorial

Python

1def factorial(n):2    if n <= 1:3        return 14    return n * factorial(n - 1)5
6
7for n in (0, 1, 5, 10):8    print(n, factorial(n))

Output

What this code does

The base case covers 0 and 1, so no input skips past it.
Python integers never overflow, so even large factorials stay exact.

Example 3 · Sum of digits

Python

1def digit_sum(n):2    if n < 10:3        return n4    return n % 10 + digit_sum(n // 10)5
6
7print(digit_sum(4821))

Output

What this code does

n % 10 is the last digit and n // 10 is the number without it.
A one-digit number is the base case.

The if is the base case and the last line is the recursive case. The argument shrinks each time, so the base case is always reached.

The call stack

Call stack is the pile of function calls that are waiting to finish. A new call goes on top and the top call finishes first, so the most recent call is always answered first.

Each call waits for the call below it to finish. Python keeps the waiting calls in a pile and finishes the newest one first.

Python

1def total_to(n, depth=0):2    pad = "  " * depth3    print(pad + "call", n)4    if n == 0:5        return 06    result = n + total_to(n - 1, depth + 1)7    print(pad + "return", result)8    return result9
10
11total_to(3)

The call stack for total_to(3). Four calls are stacked, total_to(3) at the bottom and total_to(0) on top. The top call returns 0, then 1, 3 and 6 pass back down as each call finishes.

Calls go down to 0 first. Then the answers come back up, newest call first. Every waiting call uses memory, so depth costs space.

No base case, no end

RecursionError is the exception Python raises when the call stack grows deeper than the recursion limit. It usually means a missing base case or an input that never shrinks toward it.

If the base case is missing or never reached, calls keep piling up. Python stops them with an error instead of running forever.

Python

1def broken(n):2    return n + broken(n - 1)3
4
5try:6    broken(5)7except RecursionError:8    print("Stopped: too many calls")

Example 4 · A base case that is skipped

Python

1def bad(n):2    if n == 0:3        return 04    return n + bad(n - 1)5
6
7def good(n):8    if n <= 0:9        return 010    return n + good(n - 1)11
12
13try:14    bad(-1)15except RecursionError:16    print("bad(-1) never reaches 0")17print(good(-1), good(4))

Output

bad(-1) never reaches 0
0 10

What this code does

For -1 the argument moves away from 0, so bad never stops.
Testing n <= 0 catches every input at or below the base.

Before running a recursive function, ask whether every call moves closer to the base case.

Next step

Check your understanding

10 quick questions

A function that calls itself

Recursion is when a function solves a problem by calling itself on a smaller version of the same problem, until the problem is small enough to answer directly.

A countdown prints a number, then needs the countdown from the number below it. A function can do that by calling itself with a smaller number.

1def total_to(n, depth=0):2 pad = " " * depth3 print(pad + "call", n)4 if n == 0:5 return 06 result = n + total_to(n - 1, depth + 1)7 print(pad + "return", result)8 return result9 10 11total_to(3)

No base case, no end

RecursionError is the exception Python raises when the call stack grows deeper than the recursion limit. It usually means a missing base case or an input that never shrinks toward it.

If the base case is missing or never reached, calls keep piling up. Python stops them with an error instead of running forever.

1def bad(n):2 if n == 0:3 return 04 return n + bad(n - 1)5 6 7def good(n):8 if n <= 0:9 return 010 return n + good(n - 1)11 12 13try:14 bad(-1)15except RecursionError:16 print("bad(-1) never reaches 0")17print(good(-1), good(4))