Thinking Recursively: Recursion in Python
A function that solves a problem by calling a smaller copy of itself
- define recursion and identify the base case and recursive case,
- trace how the call stack grows and unwinds during a recursive call,
- write classic recursions: factorial, Fibonacci, sum of a list, and directory walking,
- decide when recursion reads better than a loop and when a loop is the safer choice,
- explain Python's recursion limit and why deep recursion raises
RecursionError.
1. What recursion means
You already write functions that call other functions. Recursion is simply a function that calls itself. That sounds circular, and it would be, except each call works on a smaller piece of the problem until the piece is so small the answer is obvious and no further call is needed.
Think of a task defined in terms of itself. "The factorial of n is n times the factorial of n - 1." That sentence describes a bigger problem (factorial of n) using a smaller one (factorial of n - 1). Recursion turns that self-referential description directly into code.
def factorial(n):
if n == 0: # base case: nothing left to multiply
return 1
return n * factorial(n - 1) # recursive case: a smaller problem
print(factorial(4)) # 24The function refers to itself on the last line. There is no loop, yet it multiplies 4 * 3 * 2 * 1. The magic is that each call waits for a smaller call to finish before doing its own multiplication.