Last modified: Nov 19, 2026
Python Recursion Explained with Examples
Recursion is a technique where a function calls itself. It solves big problems by breaking them into smaller versions of the same problem.
This guide explains recursion in Python step by step. You will see real code, outputs, and common pitfalls. By the end, you will know when recursion helps and when to avoid it.
What Is Recursion in Python?
A recursive function solves a problem by calling itself with a smaller input. Each call moves closer to a stopping point.
Every recursive function needs two parts. The base case stops the recursion. The recursive case calls the function again with simpler input.
Without a base case, the function calls itself forever. Python then raises a RecursionError.
The Two Parts of a Recursive Function
Think of recursion like Russian nesting dolls. You open one doll and find a smaller one inside. You keep opening until you reach the smallest doll. That smallest doll is the base case.
Here is the general pattern:
def recursive_function(input):
if base_case_condition:
return base_case_result # stop here
else:
return recursive_function(smaller_input) # call again
Keep this pattern in mind. Every example below follows it.
Example 1: Countdown with Recursion
Let's start with a simple countdown. The base case is when the number reaches zero.
def countdown(n):
if n == 0: # base case: stop counting
print("Done!")
return
print(n)
countdown(n - 1) # recursive case: smaller input
countdown(3)
3
2
1
Done!
Each call prints a number and passes a smaller value. When n hits zero, the base case ends the chain.
Example 2: Factorial with Recursion
The factorial of a number multiplies all positive integers up to that number. For example, 5 factorial is 5 × 4 × 3 × 2 × 1 = 120.
This problem fits recursion perfectly. The factorial of n equals n times the factorial of n - 1.
def factorial(n):
if n == 0 or n == 1: # base case
return 1
return n * factorial(n - 1) # recursive case
print(factorial(5))
print(factorial(0))
120
1
The base case returns 1. Then each stacked call multiplies its value on the way back up. The result builds from the smallest call to the largest.
How the Call Stack Works
Python tracks function calls with the call stack. Each recursive call adds a new frame to the stack. When a call finishes, its frame is removed.
For factorial(3), the stack grows like this:
factorial(3) -> needs factorial(2)
factorial(2) -> needs factorial(1)
factorial(1) -> base case, returns 1
Then the stack unwinds. Each frame returns its result to the caller above it.
This is why deep recursion can be expensive. Python limits the stack depth by default, usually around 1000 frames.
Example 3: Fibonacci Numbers
The Fibonacci sequence starts with 0 and 1. Each next number is the sum of the two before it: 0, 1, 1, 2, 3, 5, 8, and so on.
def fibonacci(n):
if n <= 1: # base case
return n
return fibonacci(n - 1) + fibonacci(n - 2) # two recursive calls
print(fibonacci(6))
8
This version is easy to read but very slow for large n. It recalculates the same values many times.
Recursion is not always the best tool. For Fibonacci, an iterative loop or memoization is much faster.
Example 4: Recursion with Lists
Recursion also works well with nested data. Here is a function that sums all numbers in a nested list.
def sum_nested(data):
total = 0
for item in data:
if isinstance(item, list): # nested list found
total += sum_nested(item) # recurse into it
else:
total += item
return total
print(sum_nested([1, [2, 3], [4, [5, 6]]]))
21
This pattern is common in file systems, JSON data, and tree structures. Each level of nesting triggers one more call.
Recursion vs Iteration
Anything you can do with recursion, you can usually do with a loop. So how do you choose?
Use recursion when the problem is naturally nested or tree-like. Examples include directory trees, parsing, and divide-and-conquer algorithms.
Use loops when you simply need to repeat steps. Loops are faster and use less memory.
Python has no tail-call optimization. That means every recursive call uses stack space. For deep data, prefer loops.
Common Mistakes with Recursion
Missing base case. The function calls itself forever until Python raises a RecursionError.
Base case never reached. If the input does not shrink each time, the recursion never stops.
Recalculating the same results. Slow functions like naive Fibonacci waste time. Use memoization or caching to fix this.
Too much stack depth. Very deep recursion crashes. Convert it to a loop or raise the limit with care.
You can inspect the current limit like this:
import sys
print(sys.getrecursionlimit()) # default is usually 1000
1000
Recursion with Other Python Tools
Recursion often works alongside other Python features. For example, you can pass flexible arguments to a recursive helper. The guide on Python *args and **kwargs explained shows how to do that cleanly.
You can also apply a small function to every item in a recursive result. Learn how with the Python map function explained tutorial.
When you need to keep only matching values, the Python filter function explained with examples article is a great follow-up read.
When to Use Recursion
Recursion shines in these cases:
Tree and graph traversal, such as walking folders or JSON objects.
Divide-and-conquer algorithms, like merge sort and quicksort.
Problems defined in terms of themselves, like factorials and the Towers of Hanoi.
In each case, recursion makes the code shorter and easier to reason about. If the problem feels nested, recursion is often the natural choice.
Conclusion
Recursion is a powerful idea. A function solves a problem by calling itself with smaller input.
Always include a clear base case. Make sure the input shrinks on every call. Watch the call stack for deep problems.
Start with small examples like countdown and factorial. Then try nested lists and trees. With practice, recursion becomes a natural tool in your Python toolbox.