Python Recursion
In this page:
def function_name(parameter):
if base_condition:
return base_value
return function_name(smaller_parameter)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 # base case, stops the recursion
print(n)
countdown(n - 1) # calls itself with a smaller value
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 # base case
return fib(n - 1) + fib(n - 2) # recursive case, mirrors the math definition
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) # calls itself until n reaches 0
def factorial_iterative(n):
result = 1
for i in range(1, n + 1):
result *= i # accumulates the product without recursive calls
return result
print(factorial_recursive(5), factorial_iterative(5))- Forgetting the base case, so the function calls itself forever and raises
RecursionError. - Writing a recursive step that does not move toward the base case, like
f(n)callingf(n)instead off(n - 1). - Using naive recursion for something like Fibonacci with large
n, which repeats work exponentially and is very slow.
Chapter Quiz — Complete all 9 topics to unlock
0/9 topics done
Complete these topics first: