Base case
Overview
The base case is the stopping condition of a recursive function — a block of code that returns a direct result without making any further recursive calls.
Without a reachable base case, a recursive function will call itself infinitely, leading to a stack overflow or 'RecursionError'. It ensures the recursion eventually terminates by handling the simplest possible instance of the problem. When the base case is hit and returns its value, that value bubbles back up through the chain of previous calls.
Why learn this
- Understanding the base case is the very first step to writing any recursive function.
- Failing to write a reachable base case is the most common cause of fatal crashes (stack overflows) in recursive code.
- It teaches you the two unbreakable rules of recursion: you must have a base case, and every recursive step must shrink the input strictly toward that base case.
Aha moment
def countdown(n):
# This is the base case
if n <= 0:
print('Liftoff!')
return
print(n)
countdown(n - 1)Prediction: The base case is `if n <= 0: return`, which stops the countdown when it reaches zero.
Common guess: Recursion just knows when to stop once the numbers get small enough.
Recursion isn't magic and has no built-in awareness of 'stopping'. The base case (`n <= 0`) is explicitly doing the work of terminating the function when the countdown finishes.
Common mistakes
- Assuming recursion 'just knows when to stop': Recursion has no built-in awareness of when to terminate. If you do not explicitly define a base case and return without making another recursive call, the function will recurse infinitely.
- Unreachable base case: The base case exists, but the recursive step never shrinks the input toward it. For example, if the base case is n == 0, but the recursive step is f(n + 1), it will never terminate for positive n.
Recall questions
- What is a base case in recursion?
- What happens if a recursive function lacks a reachable base case?
- What two properties must a valid recursive function have?
Understanding checks
A student writes a recursive countdown function: `def count(n): if n == 0: return; else: print(n); count(n)` What is the bug?
The recursive step `count(n)` passes the exact same input instead of shrinking it. The argument never moves strictly toward the base case `n == 0`, leading to infinite recursion.
A base case is only effective if every recursive call guarantees the input becomes strictly smaller, moving measurably closer to the stopping condition.
What happens when you call `factorial(-1)` on this function: `def factorial(n): if n == 1: return 1; return n * factorial(n - 1)`?
It causes a stack overflow. Because the input -1 is already less than 1, subtracting 1 moves it further away from the base case `n == 1`, making the base case unreachable.
Base cases must handle the smallest possible valid inputs and the bounds must be robust. A safer base case would be `if n <= 1: return 1` to catch edge cases.
Practice tasks
Identify the missing base case
The following recursive function is supposed to sum all integers from `n` down to 1. Currently, it crashes with a RecursionError. Identify why and add the appropriate base case to fix it.
Continue learning
Next: Recursive relation