Recursion occurs when a function calls itself to solve a smaller version of the same problem. It can make some algorithms and tree-shaped problems easier to express, but every recursive function needs a clear stopping condition and progress toward it. Without those, the calls can continue until Python raises a recursion-related error.
The two parts of a recursive function
A recursive function needs a base case that can be answered directly and a recursive case that reduces the problem. For factorial, the base case is 0! = 1, and the recursive rule is n! = n × (n − 1)! for positive integers.
The function below assumes n is a non-negative integer. Real code should validate inputs if the function is called with external or user-provided values.
def factorial(n: int) -> int:
if n < 0:
raise ValueError('n must be non-negative')
if n in (0, 1):
return 1
return n * factorial(n - 1)
print(factorial(5)) # 120Trace the calls for factorial(4)
The calls reduce the input one step at a time: factorial(4) waits for factorial(3), which waits for factorial(2), which waits for factorial(1). The base case returns 1, after which the waiting calls multiply their results as they return.
Writing the call sequence helps reveal whether each recursive call makes progress toward the base case. A function that calls itself with the same input can recurse forever unless another condition stops it.
factorial(4)
= 4 * factorial(3)
= 4 * 3 * factorial(2)
= 4 * 3 * 2 * factorial(1)
= 4 * 3 * 2 * 1
= 24Recursion on lists and trees
Recursive thinking is useful when a data structure is defined in terms of smaller parts, such as a tree with child subtrees. A recursive function can process a node and then call itself on each child. For a flat list, a loop is usually simpler, but recursion can be instructive for divide-and-conquer algorithms.
In all cases, check the empty or terminal structure. A tree traversal needs to handle a missing node; a recursive list function needs a condition for an empty or exhausted list.
Recursion versus iteration
An iterative solution uses a loop, while a recursive solution uses function calls. Recursion can make the logic close to the mathematical definition, but it also uses call-stack space and can hit Python's recursion limit for deep inputs.
For a simple factorial, an iterative version may use less call-stack memory. For trees and divide-and-conquer algorithms, recursion can be more natural. Compare clarity, depth, complexity and input size before choosing.
def factorial_iterative(n: int) -> int:
if n < 0:
raise ValueError('n must be non-negative')
result = 1
for value in range(2, n + 1):
result *= value
return resultCommon recursion mistakes
The most common bugs are a missing base case, a recursive call that does not reduce the problem, an incorrect return value, and misunderstanding how results flow back through waiting calls.
Test the smallest valid input, one step above the base case, an ordinary example and an invalid input. If the recursion is deep or could be very large, consider an iterative or stack-based approach.
- Write the base case before the recursive case.
- Ensure each call moves closer to the base case.
- Return recursive results when needed.
- Test boundary inputs and invalid values.
- Consider iteration for deep or very large input.
Understanding the concept is the first step.
Explore related resources or learn about subject-focused tutoring designed to help you understand the material.