Python Recursion Exercises: Base Cases and Smaller Problems
Recursion is easier when you write the stopping condition first. Then ask one question: what smaller input can this function pass to itself?
Write the base case first
The base case is the input you can answer immediately. For a countdown, zero is the natural stopping point. Test the base case by itself before adding the recursive branch.
def countdown(n):
if n == 0:
return 0
return 1 + countdown(n - 1)
print(countdown(4))A countable recursion
Shrink the input
Each call must move toward the base case. Factorial multiplies n by factorial(n - 1), so the input decreases every time. Without that decrease, the function would call itself forever.
def factorial(n):
if n <= 1:
return 1
return n * factorial(n - 1)
print(factorial(5))A smaller input each time
Branch carefully
Some problems need two recursive calls. Fibonacci uses fib(n - 1) and fib(n - 2). Draw the call tree for n = 5 and notice the repeated branches; that is why caching can help larger inputs.
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
print(fib(6))Two recursive branches
Walk a nested list
A recursive list function handles the first item and delegates the rest to a smaller list. The empty list returns a base value. This pattern extends to trees and other nested structures.
def total(items):
if not items:
return 0
return items[0] + total(items[1:])
print(total([2, 4, 6]))The list gets shorter
Debug a recursion error
If Python raises RecursionError, print the input at the start of each call. Check that a base case exists and that every branch moves closer to it. A loop may be clearer when the problem is flat and repetitive.
def total(items, depth=0):
print(" " * depth, len(items))
if not items:
return 0
return items[0] + total(items[1:], depth + 1)
print(total([1, 2, 3]))Trace the shrinking input
Your practice checklist
- Identify the smallest input before writing the recursive call.
- Make sure every branch reduces the input.
- Trace a small example by hand.
- Use a loop when recursion adds no clarity.
Common questions
What is a base case?
The input for which the function returns an answer without calling itself. It stops the recursion.
Why is my recursive function slow?
It may repeat the same subproblems, as naive Fibonacci does. Memoisation or an iterative version can avoid that work.
Can every loop be written as recursion?
In principle, yes, but not every problem becomes clearer. Use recursion when the data or problem is naturally nested.
Practice recursion
12 questions on base cases, factorial, Fibonacci, list recursion, and debugging.
Keep reading: