Recursion occurs when a function solves a problem by calling itself.
This may seem strange at first – why would a function call itself? — but once you’ve clicked on it, you’ll often find a more natural way to express certain types of problems in code.
In this article, you’ll learn what recursion is, how it works, and how to use it in Python with examples that go from the basics to practical real-world use cases.
You can get the code. on GitHub.
Conditions
Before we begin, make sure you have:
Python 3.10 or higher is installed.
A basic understanding of Python functions and how they work.
Familiarity with loops and conditionals
Table of Contents
What is repetition?
Repetition is a technique where a A function solves a problem by breaking it down into smaller versions of the same problem and calling itself on that smaller version..
Think Russian nesting dolls or matryoshka doll sets. To find the smallest doll, you open the outer doll, then the next doll inside, and so on until there are none left to open. Each step is the same process — open the doll — on a smaller doll than before.
This is iteration in a nutshell: the same process, applied to a shrinking problem, until you reach a point where there is nothing left to do.
Two rules for every recursive function
Every correct recursive function must have exactly two things.
1. A base case – the condition where the function stops calling itself and returns the result directly.
2. A recurring case — The part where the function calls itself with a shortened or simplified version of the input.
If you forget the base case, the function will continue to call itself forever — until Python raises a RecursionError. We will talk more about this later.
Your first recursive function
Let’s start with the classic example: calculating factorials.
The factorial of n (Written as n!) is the product of all integers from 1 to n. So 5! = 5 × 4 × 3 × 2 × 1 = 120.
Pay attention to the pattern: 5! = 5 × 4!. And 4! = 4 × 3!. Every factorial is just. n Multiply by the factorial of the number below it. It is perfect for repetition.
def factorial(n):
# Base case: factorial of 0 or 1 is 1
if n <= 1:
return 1
# Recursive case: n! = n * (n-1)!
return n * factorial(n - 1)
print(factorial(5))
print(factorial(10))
These results:
120
3628800
There is a base case. n <= 1. When we hit 0 or 1, we stop and return 1. It is repetitive. n * factorial(n - 1). We multiply. n By factoring the number below that, trust the function to figure out the remainder.
How does Python handle recursion calls?
When a function calls itself, Python doesn’t just replace the current call — it stacks them. Each call waits for the call below it to return a value before terminating.
Let’s trace. factorial(4) step by step:
factorial(4)
└── 4 * factorial(3)
└── 3 * factorial(2)
└── 2 * factorial(1)
└── returns 1 ← base case
└── 2 * 1 = 2
└── 3 * 2 = 6
└── 4 * 6 = 24
Each call is pushed to Python. Call stack. Once the base case returns, the stack is opened – each waiting call is answered and terminated. This is why deep recursion can be a problem: too many stacked calls and Python runs out of stack space.
Repetition vs Repetition
Most problems that you can solve repeatedly, you can also solve with loops. Let’s compare the two methods for assembling a list of numbers.
Iterative approach:
def sum_iterative(numbers):
total = 0
for n in numbers:
total += n
return total
Iterative approach:
def sum_recursive(numbers):
if not numbers: # base case: empty list
return 0
return numbers(0) + sum_recursive(numbers(1:))
print(sum_recursive((10, 20, 30, 40)))
The recursive function call gives the following output:
100
The iterative version says: The set of a list is the set of all elements except the first element.. The base case is an empty list, whose sum is 0.
Both iterative and iterative methods work. Repetition is more expressive. This is close to how you would describe the problem in plain English. Recursion is more efficient in Python. Knowing which is a skill you will develop with practice.
Working with nested data
This is where repetition really starts to make sense. Loops are great for flat data, but nested structures — like folder trees or deeply nested dictionaries — are often awkward to handle with loops.
Suppose you have a nested dictionary representing a product catalog, and you want to find all the values buried within it:
catalog = {
"electronics": {
"laptops": {
"ThinkPad X1": 1299.99,
"MacBook Air": 1099.99
},
"accessories": {
"USB-C Hub": 49.99,
"Laptop Stand": 34.99
}
},
"stationery": {
"Notebook A5": 8.99,
"Gel Pen Set": 12.49
}
}
def find_all_prices(data):
prices = ()
for value in data.values():
if isinstance(value, dict):
# It's a nested dict — recurse into it
prices.extend(find_all_prices(value))
else:
# It's a price — collect it
prices.append(value)
return prices
all_prices = find_all_prices(catalog)
print(f"All prices: {all_prices}")
print(f"Total inventory value: ${sum(all_prices):.2f}")
The function evaluates each value. If it’s another dictionary, it repeats it. If it’s a number, it adds it.
To write it with nested loops you need to know the depth of the structure in advance. Repetition doesn’t care how deep it goes.
Output:
All prices: (1299.99, 1099.99, 49.99, 34.99, 8.99, 12.49)
Total inventory value: $2506.44
Recursive Tree Traversal
Oh The tree is a structure where each node can have child nodes, and each child node is itself a tree. That self-similar structure maps directly to a recursive function.
Let’s create a simple file system tree and calculate the total size of all files.
class FileNode:
def __init__(self, name, size=0, children=None):
self.name = name
self.size = size # 0 for folders
self.children = children or ()
def total_size(node):
# Base case: it's a file (no children)
if not node.children:
return node.size
# Recursive case: sum this node's size + all children's sizes
return node.size + sum(total_size(child) for child in node.children)
# Build a small file tree
project = FileNode("project", children=(
FileNode("src", children=(
FileNode("main.py", size=12400),
FileNode("utils.py", size=5800),
)),
FileNode("data", children=(
FileNode("sales_jan.parquet", size=302914),
FileNode("sales_feb.parquet", size=289000),
)),
FileNode("README.md", size=3200)
))
print(f"Total project size: {total_size(project):,} bytes")
print(f"Source files only: {total_size(project.children(0)):,} bytes")
For each node, we either return its size directly (base case: it’s a file) or add its size to the collection of all its children (recursive case: it’s a folder). The code structure mirrors the tree structure.
Running the above should yield the following output:
Total project size: 613,314 bytes
Source files only: 18,200 bytes
Memorization: correcting slow repetition
Repetition can sometimes get too repetitive. is a classic example Fibonacci sequencewhere each number is the sum of the two preceding it.
def fib(n):
if n <= 1:
return n
return fib(n - 1) + fib(n - 2)
It works, but fib(35) Already takes a noticeable break. The problem is that fib(30) Counted dozens of times in different branches.
ok Memory This includes caching results so each value is computed only once. Python makes this extremely easy. functools.lru_cachewhich you can use like this:
from functools import lru_cache
@lru_cache(maxsize=None)
def fib_fast(n):
if n <= 1:
return n
return fib_fast(n - 1) + fib_fast(n - 2)
print(fib_fast(10))
print(fib_fast(50))
print(fib_fast(100))
Output:
55
12586269025
354224848179261915075
Adding @lru_cache Saves the result of each call. next time fib_fast(30) If needed, it returns the cached value immediately instead of recomputing the entire subtree.
Note: Memory is reachable any time your recursive function can solve the same subproblem more than once.
Python iteration limit
Sets a default iteration limit for Python. 1000 calls. If your function goes deeper than that, you’ll get one. RecursionError:
def countdown(n):
if n == 0:
return "Done"
return countdown(n - 1)
print(countdown(5)) # works fine
print(countdown(2000)) # raises RecursionError
Here countdown(5) works and we get Done During the message countdown(2000) Gives a RecursionError Because it exceeds the preset iteration limit of 1000 iteration calls.
Done
RecursionError: maximum recursion depth exceeded
You can increase the limit with it. sys.setrecursionlimit()but this is usually a sign that iteration—or memory—is the better tool for that particular problem.
import sys
sys.setrecursionlimit(5000) # use with caution
For most tree trips and Divide and conquer Algorithm, the default limit is more than enough. You’ll only hit this when working with very deep input structures.
When to use Recursion
Repetition is a good fit when:
A problem naturally has a self-structured structure – trees, graphs, nested data, file systems
You’re implementing divide-and-conquer algorithms — merge sort, binary search, quick sort
The iterative solution is significantly clearer than the iterative equivalent.
The depth of the structure is not known at compile time.
Prefer iteration when:
You’re working with flat sort — summarizing a list, searching an array
Performance is important – Python doesn’t optimize tail calls, so deep recursion is overhead
Input may be too large or deeply nested – risk of Recursion Error
The result
It takes a while for the iteration to feel natural, but the basic idea is simple: solve a small version of the problem, trust the function to handle the rest, and always define a base case to stop.
You’ve covered the basics: how the call stack works, how to handle nested data, tree traversal, and how to speed things up with memoization. These patterns come up again and again in practice, especially when working with file systems, parsers, and hierarchical data.
The best way to get relief from repetition is to choose a suitable problem and try to write it repeatedly before reaching the loop. Thinking becomes easier every time. You can also solve related programming challenges on HackerRank or Leetcode.
Happy coding!