Recursive vs Iterative Trade-offs
Convert recursive factorial and Fibonacci to iterative loops and explain when Python's recursion limit and stack size make iteration preferable.
The Recursive-Iterative Duality
Every algorithm that can be written recursively can also be written iteratively, and vice versa. The recursive version often mirrors the problem's mathematical definition more closely, while the iterative version gives you explicit control over memory and avoids stack-overflow risks. Choosing between them is a pragmatic decision based on readability, depth limits, and performance requirements.
In interviews, being able to present both versions and explain the trade-offs is a strong signal of mastery.
Factorial: Recursive vs Iterative
Factorial is the canonical example. The recursive version directly encodes the mathematical definition n! = n × (n-1)!. It uses O(n) stack space due to n pending return values. The iterative version loops from 1 to n, using O(1) space. For n = 1000 the recursive version hits Python's default limit; the iterative version handles arbitrarily large n.
def factorial_rec(n):
if n == 0:
return 1
return n * factorial_rec(n - 1) # O(n) stack
def factorial_iter(n):
result = 1
for i in range(2, n + 1):
result *= i # O(1) stack
return result
print(factorial_rec(10)) # 3628800
print(factorial_iter(10)) # 3628800
# Large n: iterative works, recursive may overflow
print(factorial_iter(1000) > 0) # True (Python handles big ints)All lessons in this course
- Recursion Framework: Base Case, Trust, Build
- Visualising the Call Stack
- Recursive vs Iterative Trade-offs
- Memoisation: Caching Recursive Results