Python - Recursion with Examples
Recursion occurs when a function calls itself to solve a problem. Every recursive function needs two components: a base case that stops the recursion and a recursive case that moves toward the base...
Key Insights
- Recursion solves problems by breaking them into smaller instances of the same problem, requiring a base case to prevent infinite loops and a recursive case that progresses toward that base case
- Python’s default recursion limit is 1000 calls, which can be modified but should be approached cautiously as deep recursion can cause stack overflow errors
- Iterative solutions often outperform recursive ones in Python due to function call overhead, but recursion excels in tree traversal, backtracking, and divide-and-conquer algorithms
Understanding Recursion Fundamentals
Recursion occurs when a function calls itself to solve a problem. Every recursive function needs two components: a base case that stops the recursion and a recursive case that moves toward the base case.
def countdown(n):
# Base case
if n <= 0:
print("Done!")
return
# Recursive case
print(n)
countdown(n - 1)
countdown(5)
# Output: 5, 4, 3, 2, 1, Done!
The call stack grows with each recursive call. When countdown(5) executes, it creates a chain: countdown(5) → countdown(4) → countdown(3) → countdown(2) → countdown(1) → countdown(0). Each call waits for the next to complete before returning.
Factorial Calculation
The factorial function demonstrates classic recursion. n! equals n * (n-1)!, with 0! = 1 as the base case.
def factorial(n):
if n == 0 or n == 1:
return 1
return n * factorial(n - 1)
print(factorial(5)) # 120
print(factorial(0)) # 1
Compare with an iterative approach:
def factorial_iterative(n):
result = 1
for i in range(2, n + 1):
result *= i
return result
print(factorial_iterative(5)) # 120
The iterative version uses constant space O(1), while recursion uses O(n) space for the call stack.
Fibonacci Sequence
Fibonacci numbers follow the pattern where each number is the sum of the two preceding ones. This naturally maps to recursion but demonstrates performance pitfalls.
def fibonacci_naive(n):
if n <= 1:
return n
return fibonacci_naive(n - 1) + fibonacci_naive(n - 2)
print(fibonacci_naive(10)) # 55
This naive implementation has O(2^n) time complexity because it recalculates the same values repeatedly. fibonacci_naive(5) calls fibonacci_naive(3) twice, each calling fibonacci_naive(2) twice, creating exponential redundancy.
Memoization fixes this by caching results:
def fibonacci_memo(n, memo={}):
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo)
return memo[n]
print(fibonacci_memo(100)) # 354224848179261915075
Using Python’s functools.lru_cache decorator provides automatic memoization:
from functools import lru_cache
@lru_cache(maxsize=None)
def fibonacci_cached(n):
if n <= 1:
return n
return fibonacci_cached(n - 1) + fibonacci_cached(n - 2)
print(fibonacci_cached(100)) # 354224848179261915075
Tree Traversal
Recursion naturally handles tree structures. Consider a binary tree implementation:
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def inorder_traversal(node):
if node is None:
return []
result = []
result.extend(inorder_traversal(node.left))
result.append(node.value)
result.extend(inorder_traversal(node.right))
return result
def preorder_traversal(node):
if node is None:
return []
result = [node.value]
result.extend(preorder_traversal(node.left))
result.extend(preorder_traversal(node.right))
return result
# Build tree: 4
# / \
# 2 6
# / \ / \
# 1 3 5 7
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(6)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
root.right.left = TreeNode(5)
root.right.right = TreeNode(7)
print(inorder_traversal(root)) # [1, 2, 3, 4, 5, 6, 7]
print(preorder_traversal(root)) # [4, 2, 1, 3, 6, 5, 7]
Directory Tree Walking
Recursion excels at navigating nested file structures:
import os
def list_files(directory, indent=0):
try:
items = os.listdir(directory)
except PermissionError:
print(" " * indent + "[Permission Denied]")
return
for item in items:
path = os.path.join(directory, item)
print(" " * indent + item)
if os.path.isdir(path):
list_files(path, indent + 1)
# list_files("/path/to/directory")
A practical version that collects file information:
def find_files_by_extension(directory, extension):
results = []
try:
for item in os.listdir(directory):
path = os.path.join(directory, item)
if os.path.isfile(path) and path.endswith(extension):
results.append(path)
elif os.path.isdir(path):
results.extend(find_files_by_extension(path, extension))
except PermissionError:
pass
return results
# python_files = find_files_by_extension("/project", ".py")
Backtracking with Permutations
Backtracking algorithms use recursion to explore solution spaces. Generating permutations demonstrates this pattern:
def permutations(elements):
if len(elements) <= 1:
return [elements]
result = []
for i in range(len(elements)):
current = elements[i]
remaining = elements[:i] + elements[i+1:]
for perm in permutations(remaining):
result.append([current] + perm)
return result
print(permutations([1, 2, 3]))
# [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
Solving the N-Queens problem uses backtracking:
def solve_n_queens(n):
def is_safe(board, row, col):
# Check column
for i in range(row):
if board[i] == col:
return False
# Check diagonals
for i in range(row):
if abs(board[i] - col) == abs(i - row):
return False
return True
def backtrack(board, row):
if row == n:
solutions.append(board[:])
return
for col in range(n):
if is_safe(board, row, col):
board[row] = col
backtrack(board, row + 1)
board[row] = -1 # Backtrack
solutions = []
backtrack([-1] * n, 0)
return solutions
solutions = solve_n_queens(4)
print(f"Found {len(solutions)} solutions for 4-Queens") # 2 solutions
Managing Recursion Depth
Python limits recursion depth to prevent stack overflow:
import sys
print(sys.getrecursionlimit()) # Default: 1000
# Increase limit (use cautiously)
sys.setrecursionlimit(2000)
Convert deep recursion to iteration using an explicit stack:
def factorial_iterative_stack(n):
stack = []
result = 1
while n > 1:
stack.append(n)
n -= 1
while stack:
result *= stack.pop()
return result
print(factorial_iterative_stack(5)) # 120
Tail Recursion Optimization
Python doesn’t optimize tail recursion, but understanding the concept helps. Tail recursion occurs when the recursive call is the last operation:
def factorial_tail(n, accumulator=1):
if n <= 1:
return accumulator
return factorial_tail(n - 1, n * accumulator)
print(factorial_tail(5)) # 120
Despite the tail-recursive form, Python still builds the full call stack. Convert to iteration for better performance:
def factorial_optimized(n):
accumulator = 1
while n > 1:
accumulator *= n
n -= 1
return accumulator
Recursion provides elegant solutions for problems with self-similar structure. Use it when the problem naturally decomposes recursively—trees, graphs, backtracking—but consider iterative alternatives for simple linear recursion or when performance is critical. Memoization transforms exponential recursive algorithms into practical solutions, and understanding recursion depth limitations prevents runtime errors in production code.