Python Recursion: How It Works, When to Use It, and Examples
Imagine a set of Russian nesting dolls. You open the biggest one and find a smaller one inside. Open that, and there's an even smaller one. You keep opening until you reach the tiniest doll that doesn't open — that's the end.
Recursion works the same way. A recursive function calls itself with a smaller version of the problem, again and again, until it hits a stopping point. It's one of the most elegant techniques in programming — and once it clicks, you'll see it everywhere.
In this tutorial, you'll learn what recursion is, how the call stack tracks each step, when recursion is the right tool, and how to avoid the most common mistakes. We'll build up from simple examples to classic algorithms like factorial and Fibonacci.
What Is Recursion?
Recursion is when a function calls itself. That's the entire definition. But why would you ever want a function to call itself?
Think about counting down from 5. You could describe the process like this: "To count down from N, say N, then count down from N minus 1. Stop when you reach 0." That's a recursive description — the instruction refers to itself.
The function countdown(5) prints 5, then calls countdown(4). That prints 4 and calls countdown(3). This keeps going until countdown(0) prints "Go!" and stops. No more calls.
Every recursive function has two essential parts. Without both, the function will run forever (or until Python stops it).
The Base Case: When to Stop
The base case is the condition that stops the recursion. It's the tiniest nesting doll — the one that doesn't open. Without a base case, the function calls itself forever.
The recursive case is the part where the function calls itself with a simpler input. Each call should bring you closer to the base case.
A good rule of thumb: always write the base case first. Then write the recursive case that moves toward it. This order prevents you from accidentally forgetting the exit condition.
How the Call Stack Works
When a function calls itself, Python doesn't forget where it was. It uses a call stack — a stack of "frames" where each frame remembers the function's local variables and where to resume.
Think of it like a stack of sticky notes. Each time you call a function, Python writes a new note with that call's details and places it on top. When a function returns, Python peels off the top note and goes back to the one underneath.
Notice how the "Calling" messages go deeper and deeper, then the results bubble back up. The call stack grows as calls go in, then shrinks as results come back out. This "in and out" pattern is the heartbeat of recursion.
Classic Recursion Examples
Factorial
The factorial of a number N (written as N!) is N multiplied by every positive integer below it. For example, 5! = 5 x 4 x 3 x 2 x 1 = 120.
Factorial is naturally recursive: 5! = 5 x 4!, and 4! = 4 x 3!, and so on. The base case is 1! = 1.
Sum of a List
Here's another pattern: to sum a list recursively, add the first element to the sum of the rest.
The pattern is: handle the base case (empty list returns 0), then break the problem into "first element" plus "recursive call on the rest." This pattern works for many list operations.
Recursion vs Loops: When to Use Which
Anything you can do with recursion, you can also do with a loop. So when should you choose one over the other?
def factorial(n):
if n <= 1:
return 1
return n * factorial(n - 1)
print(factorial(5)) # 120def factorial(n):
result = 1
for i in range(2, n + 1):
result = result * i
return result
print(factorial(5)) # 120For simple problems like factorial, loops are usually faster and use less memory. Each recursive call adds a frame to the call stack, while a loop just reuses the same variables.
Recursion shines when the problem is naturally tree-shaped or self-similar. Examples include exploring folder structures, parsing nested data (like JSON or HTML), and tree/graph traversal. In these cases, recursion produces cleaner and shorter code.
When Recursion Is the Right Tool
Recursion excels at problems where you need to explore all branches of a tree-like structure. Here's a practical example: flattening a nested list.
Try writing this without recursion. You would need a manual stack and complex bookkeeping. The recursive version reads almost like English: "For each item, if it's a list, flatten it. Otherwise, keep it."
Common Recursion Mistakes
Mistake 1: No Base Case
Mistake 2: Not Moving Toward the Base Case
Practice Exercises
Start with the easier ones and work your way up. Each exercise builds on what you've learned. Remember: always write the base case first!
Read this code and predict the output. Then write print() statements that produce the exact same output.
def mystery(n):
if n <= 0:
return
mystery(n - 1)
print(n)
mystery(3)Notice that the print(n) is after the recursive call. Think carefully about the order.
Write a recursive function called sum_to that takes a positive integer n and returns the sum of all numbers from 1 to n.
For example: sum_to(5) should return 1 + 2 + 3 + 4 + 5 = 15.
Base case: sum_to(1) returns 1.
Print the results of sum_to(5) and sum_to(10) on separate lines.
This recursive function should calculate base raised to the power of exp (like base ** exp). But it has two bugs.
Fix both bugs so the output is:
8
1
81Write a recursive function called fibonacci that returns the nth Fibonacci number.
The Fibonacci sequence starts: 0, 1, 1, 2, 3, 5, 8, 13, ...
Rules:
fibonacci(0) returns 0fibonacci(1) returns 1fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)Print the results for n = 0, 1, 5, and 10 on separate lines.
Write a recursive function called reverse that takes a string and returns it reversed.
For example: reverse("hello") should return "olleh".
Hint: the last character plus the reverse of everything except the last character.
Print the results of reverse("hello") and reverse("Python") on separate lines.
Write a recursive function called count_digits that takes a non-negative integer and returns the number of digits it has.
For example:
count_digits(0) returns 1count_digits(5) returns 1count_digits(123) returns 3count_digits(99999) returns 5Hint: dividing by 10 using // removes the last digit.
Print the results for 0, 5, 123, and 99999 on separate lines.
Summary
| Here's what you've learned about recursion: | |
|---|---|
| --- | --- |
| Recursion | A function that calls itself |
| Base case | The condition that stops the recursion |
| Recursive case | The part that calls itself with a simpler input |
| Call stack | Python's system for tracking nested function calls |
| Stack overflow | What happens when recursion goes too deep (no base case) |
| Recursion vs loops | Loops for simple repetition, recursion for tree-like problems |
The golden rule of recursion: always write the base case first, and make sure every recursive call moves toward it. If you can do that, you can write any recursive function.
What's Next?
Next up is [map(), filter(), and reduce()](/python/python-map-filter-reduce) — Python's powerful functional programming tools. You'll learn how to transform, filter, and combine collections of data in a single line.