Python Recursion
In this page:
Introduction to Recursion
Recursion is when a function calls itself to solve a smaller version of the same problem; every correct recursive function needs a base case that stops the recursion, or it will keep calling itself indefinitely.
Example: Introduction to Recursion
def countdown(n):
if n == 0:
return
print(n)
countdown(n - 1)
countdown(3)Base Case and Recursive Case
The base case is the simplest version of the problem, answered directly without another recursive call, while the recursive case calls the function again with an input that's one step closer to that base case — together they guarantee the recursion eventually terminates.
Example: Base Case and Recursive Case
def factorial(n):
if n == 0: # base case
return 1
return n * factorial(n - 1) # recursive case
print(factorial(5))Fibonacci Sequence
Computing the Fibonacci sequence recursively — fib(n) = fib(n-1) + fib(n-2) — mirrors the mathematical definition almost exactly, which is why it's a classic teaching example, even though it's inefficient without additional caching.
Example: Fibonacci Sequence
def fib(n):
if n <= 1:
return n
return fib(n - 1) + fib(n - 2)
print(fib(6))Infinite Recursion
Without a reachable base case, a recursive function keeps calling itself until Python's call stack runs out, at which point it raises a RecursionError rather than exhausting all system memory silently.
Example: Infinite Recursion
def bad_recursion(n):
return bad_recursion(n) # no base case
try:
bad_recursion(1)
except RecursionError:
print("RecursionError: maximum recursion depth exceeded")Recursion vs Iteration
Any recursive function can be rewritten as an equivalent loop, and loops are usually faster and use less memory since they don't add a new stack frame for every call — recursion is chosen for clarity on naturally self-similar problems, not for raw performance.
Example: Recursion vs Iteration
def factorial_recursive(n):
return 1 if n == 0 else n * factorial_recursive(n - 1)
def factorial_iterative(n):
result = 1
for i in range(1, n + 1):
result *= i
return result
print(factorial_recursive(5), factorial_iterative(5))Chapter Quiz — Complete all 9 topics to unlock
0/9 topics done
Complete these topics first: