MainExamplesHistoryRecommended Reading
“
To understand recursion, you must first understand recursion.
Recursion is when a function calls itself. It's like a Russian nesting doll — each doll contains a smaller version of itself, and you keep opening them until you reach the smallest one.
The Basics:
- A base case: The condition that stops the recursion (the smallest doll)
- A recursive case: The function calls itself with a smaller problem
Classic Example - Factorial:
# 5! = 5 × 4 × 3 × 2 × 1
# 5! = 5 × 4!
def factorial(n):
if n == 1: # Base case
return 1
return n * factorial(n - 1) # Recursive case
Why Use It:
- Elegant: Some problems are naturally recursive (like tree traversal)
- Divide and conquer: Break big problems into smaller ones
- Mathematical: Maps well to mathematical definitions
When to Avoid:
- Performance: Iterative solutions are often faster
- Stack overflow: Deep recursion can cause memory issues
- Clarity: Sometimes loops are easier to understand
FAQ
Is recursion always slower than iteration?
Often yes, due to function call overhead. But modern compilers can optimize tail recursion, and some problems are clearer with recursion.
What's tail recursion?
A special form where the recursive call is the last operation. Some languages optimize this to avoid stack growth.
Can recursion cause problems?
Yes! Infinite recursion (missing base case) will crash your program. Deep recursion can cause stack overflow errors.