A function that calls itself sounds like a fast track to an infinite loop, yet Python recursion is one of the tidiest ways to walk a folder tree, sum a nested list, or compute a factorial. The secret is a stopping rule called the base case. This guide builds recursive functions step by step, watches the call stack grow and unwind, shows why a naive Fibonacci makes your laptop fan scream, and pins down when a plain loop wins instead.

“Now is better than never.”

Tim Peters, The Zen of Python (PEP 20)

Last Updated: July 2026 | Tested on: Python 3.14.6 | Difficulty: Beginner | Reading Time: 18 minutes

Picture yourself standing in a long queue, wanting to know your position. You could walk to the front and count every head. Or you could just tap the shoulder of the person ahead of you and ask, “What number are you?” That person asks the one in front of them. The question keeps travelling forward until it reaches the very first person, who says “I am number 1.” Now the answers ripple back: 2, then 3, then 4, until your answer reaches you. Nobody counted the whole line. Each person solved a tiny piece and trusted the person ahead to handle the rest.

That is Python recursion in plain English. It is a function that solves a problem by calling itself on a smaller version of the same problem, over and over, until it hits a case so simple it can answer straight away. That stopping point is called the base case, and we will lean on it the whole way through this post.

The Simplest Recursive Function

Tip: click the diagram to open it full screen, then use the zoom and pan controls for a closer look.

The diagram traces the call stack for factorial(4), a function we will build together two sections from now (for now, just know it multiplies 4 × 3 × 2 × 1). Each recursive call creates a fresh frame that parks itself and waits for its sub-call to finish, building a chain from factorial(4) all the way down to the base case factorial(1). Then the stack unwinds: each frame multiplies its result and hands it back to the caller sitting above it. That “build up, then unwind” rhythm is the heartbeat of every recursive function. Once you can see it, most recursion bugs stop being mysterious.

📄 countdown.py: recursion in 5 lines

def countdown(n):
    if n <= 0:          # Base case: stop here
        print("Go!")
        return
    print(n)
    countdown(n - 1)     # Recursive case: call yourself with n-1

countdown(5)

▶ Output

5
4
3
2
1
Go!

What happened here: countdown(5) prints 5, then calls countdown(4). That one prints 4 and calls countdown(3). The chain keeps going until countdown(0) reaches the base case (n <= 0), prints “Go!”, and returns. Every call has to wait for the call it made to finish first, exactly like each person in the queue waiting on the answer from the person ahead.

Anatomy of Recursion: Base Case Plus Recursive Case

Every recursive function needs exactly two things, no exceptions:

1. Base case: the condition where the function stops calling itself and just returns a direct answer
2. Recursive case: the function calls itself with a smaller or simpler input, taking one step closer to the base case

Forget the base case and your function calls itself forever, until Python pulls the plug with a RecursionError. Forget to shrink the input and you get the same endless loop, because the function keeps asking the same question and never reaches the answer it can give directly. Think of a recipe that says “to make soup, first make soup.” You would be stuck in the kitchen all day.

📄 sum_list.py: sum a list recursively

def sum_list(numbers):
    if not numbers:       # Base case: empty list
        return 0
    return numbers[0] + sum_list(numbers[1:])  # First element + sum of rest

result = sum_list([10, 20, 30, 40])
print(f"Sum: {result}")

# Trace the calls:
# sum_list([10, 20, 30, 40]) = 10 + sum_list([20, 30, 40])
# sum_list([20, 30, 40])     = 20 + sum_list([30, 40])
# sum_list([30, 40])         = 30 + sum_list([40])
# sum_list([40])             = 40 + sum_list([])
# sum_list([])               = 0  ← base case
# Unwind: 40+0=40, 30+40=70, 20+70=90, 10+90=100

▶ Output

Sum: 100

What happened here: Read the trace comments from top to bottom. The function never tries to add up the whole list at once. It grabs the first number, then trusts a smaller copy of itself to add the rest. sum_list([10, 20, 30, 40]) becomes 10 + whatever sum_list([20, 30, 40]) works out to be. That call splits off 20 and hands the rest down again, and so on, until the list is empty and the base case returns 0. Only then do the additions actually happen, on the way back up: 40, then 70, then 90, then 100. The empty list is the floor the whole thing stands on.

Factorial, The Classic Example

The factorial of n (written n!) is just n × (n-1) × (n-2) × … × 1. So 4! is 4 × 3 × 2 × 1, which equals 24. Factorials show up in real life whenever you count arrangements: if four friends line up for a group photo, there are exactly 4! = 24 different orders they can stand in. It is the textbook recursion example for one simple reason: the math definition is already recursive. Look closely: n! = n × (n-1)!. The factorial of n is defined in terms of the factorial of n-1. Python code can mirror that definition almost word for word.

📄 factorial.py: with a step-by-step trace

def factorial(n):
    print(f"  factorial({n}) called")
    if n <= 1:           # Base case
        print(f"  factorial({n}) returns 1")
        return 1
    result = n * factorial(n - 1)   # Recursive case
    print(f"  factorial({n}) returns {result}")
    return result

print("Computing 4!:")
answer = factorial(4)
print(f"\n4! = {answer}")

▶ Output

Computing 4!:
  factorial(4) called
  factorial(3) called
  factorial(2) called
  factorial(1) called
  factorial(1) returns 1
  factorial(2) returns 2
  factorial(3) returns 6
  factorial(4) returns 24

4! = 24

What happened here: Watch the order of those print lines. All four “called” messages fire first, going down: 4, 3, 2, 1. Not one multiplication has happened yet. Then the “returns” messages come back up: 1, 2, 6, 24. That down-then-up shape is the signature of recursion. Each call is frozen mid-calculation, holding its value of n, waiting for the call below it to hand back a number before it can finish its own multiplication.

The Call Stack: What Actually Happens

Every function call in Python creates a stack frame, a little block of memory that holds that call’s local variables, its parameters, and the spot to return to when it finishes. Recursive calls pile these frames on top of each other, like a stack of plates. The newest call sits on top, and Python can only ever finish the plate on top before getting to the one underneath.

📄 stack_visual.py: visualizing the call stack

def factorial_traced(n, depth=0):
    indent = "  " * depth
    print(f"{indent}PUSH: factorial({n}) at stack depth {depth + 1}")

    if n <= 1:
        print(f"{indent}BASE CASE HIT, start returning")
        return 1

    result = n * factorial_traced(n - 1, depth + 1)
    print(f"{indent}POP: factorial({n}) = {n} * ... = {result}")
    return result

print("=== Call Stack Trace ===")
print(f"Result: {factorial_traced(4)}")

▶ Output

=== Call Stack Trace ===
PUSH: factorial(4) at stack depth 1
  PUSH: factorial(3) at stack depth 2
    PUSH: factorial(2) at stack depth 3
      PUSH: factorial(1) at stack depth 4
      BASE CASE HIT, start returning
    POP: factorial(2) = 2 * ... = 2
  POP: factorial(3) = 3 * ... = 6
POP: factorial(4) = 4 * ... = 24
Result: 24

The growing indentation shows the stack getting deeper with each call (PUSH) and then shrinking as functions return (POP). At the deepest point, four stack frames are alive at the same time, each one holding its own value of n. That is the real cost of recursion: it uses memory in proportion to how deep the calls go, which matters a lot once we hit Python’s recursion limit later in this post.

Fibonacci, And Why Naive Recursion Is Slow

The Fibonacci sequence is the one where each number is the sum of the two before it: 0, 1, 1, 2, 3, 5, 8, 13, and so on. The definition is recursive (fib(n) = fib(n-1) + fib(n-2)), so it looks like a perfect job for recursion. It is a perfect job, right up until you try a slightly bigger number and your laptop fan starts screaming. Let me show you exactly why.

📄 fibonacci.py: the naive approach and why it falls apart

import time

# Naive recursive Fibonacci: DO NOT use for large n
def fib_naive(n):
    if n <= 1:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)

# Count how many times it's called
call_count = 0
def fib_counted(n):
    global call_count
    call_count += 1
    if n <= 1:
        return n
    return fib_counted(n - 1) + fib_counted(n - 2)

# fib(10): looks innocent
call_count = 0
result = fib_counted(10)
print(f"fib(10) = {result}, function called {call_count} times")

# fib(30): exponential explosion
call_count = 0
start = time.time()
result = fib_counted(30)
elapsed = time.time() - start
print(f"fib(30) = {result}, function called {call_count} times, took {elapsed:.3f}s")

▶ Output

fib(10) = 55, function called 177 times
fib(30) = 832040, function called 2692537 times, took 0.478s

What happened here: Look at that second number. To compute fib(30), the function ran nearly 2.7 million times. The reason is brutal: the naive version has no memory, so it recomputes fib(28), fib(27), and especially the small ones like fib(5) thousands of times over, as if it had never seen them before. It is like a student who re-reads the same page of a textbook every single time they need a fact on it. The fix is memoization: keep a cache of answers you have already worked out, and look them up instead of redoing the work.

📄 fibonacci_memo.py: memoized Fibonacci, the right way

from functools import lru_cache
import time

@lru_cache(maxsize=None)
def fib_memo(n):
    if n <= 1:
        return n
    return fib_memo(n - 1) + fib_memo(n - 2)

start = time.time()
result = fib_memo(100)
elapsed = time.time() - start
print(f"fib(100) = {result}")
print(f"Time: {elapsed:.6f}s")
print(f"Cache info: {fib_memo.cache_info()}")

▶ Output

fib(100) = 354224848179261915075
Time: 0.000025s
Cache info: CacheInfo(hits=98, misses=101, maxsize=None, currsize=101)

What happened here: The @lru_cache decorator wraps the function and quietly remembers every result the first time it is worked out. The next time you ask for the same n, it hands back the stored answer in an instant instead of recursing again. So fib(100), which would take the naive version millions of years at the call rate we just measured, now finishes in microseconds. The cache info line proves it: 101 real computations (one per unique n from 0 to 100) and 98 cache hits, which is exactly the mountain of repeated work that the cache wiped out. Same recursion, one decorator, night-and-day difference.

Practical Recursion: Flatten Nested Lists

This is where recursion really earns its keep. When you have no idea how deeply a structure is nested, a loop struggles, but recursion shrugs and handles it. Think of a set of those Russian nesting dolls: you open one, and there might be another doll inside, which might hold another. You do not need to know the count up front. You just open whatever is in front of you and repeat.

📄 flatten.py: flatten lists nested to any depth

def flatten(nested):
    result = []
    for item in nested:
        if isinstance(item, list):
            result.extend(flatten(item))  # Recurse into sub-lists
        else:
            result.append(item)
    return result

data = [1, [2, 3], [4, [5, 6, [7]]], 8, [[9, 10]]]
print(flatten(data))

# Works for any depth
deeply_nested = [[[[[42]]]]]
print(flatten(deeply_nested))

▶ Output

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[42]

What happened here: The function walks each item in the list. If the item is a plain value, it goes straight into the result. If the item is itself a list, the function calls itself on that inner list and splices the flattened pieces back in with extend. Because it does not care whether the nesting is one level deep or five, both data and the [[[[[42]]]]] case come out perfectly flat.

Now try writing this with a loop instead. You would need to build your own stack and track the depth by hand, and the code would easily be three times longer. Recursion wins here because the shape of the solution matches the shape of the data: a nested list is just a list that might contain more lists.

Directory Tree Walking

Folders on your computer are nested the exact same way. A folder holds files and more folders, and each of those folders holds files and yet more folders. There is no fixed depth, so this is textbook recursion territory.

📄 tree.py: print a directory tree recursively

from pathlib import Path

def print_tree(directory, prefix="", max_depth=3, current_depth=0):
    if current_depth >= max_depth:
        return
    path = Path(directory)
    entries = sorted(path.iterdir(), key=lambda e: (e.is_file(), e.name))
    for i, entry in enumerate(entries):
        connector = "└── " if i == len(entries) - 1 else "├── "
        print(f"{prefix}{connector}{entry.name}")
        if entry.is_dir():
            extension = "    " if i == len(entries) - 1 else "│   "
            print_tree(entry, prefix + extension, max_depth, current_depth + 1)

# Example (uses the current directory, so your output will differ)
print("Project structure:")
print_tree(".", max_depth=2)

Run this in any project folder and you get the familiar tree view, with each subfolder indented under its parent. The output depends on whatever folder you run it in, so I am not pinning an exact result here. One honest heads-up for Windows users: those branch characters (the box-drawing lines) need a UTF-8 console. If you see a UnicodeEncodeError, run the script with py -X utf8 tree.py or set the environment variable PYTHONUTF8=1, and it prints cleanly. On macOS and Linux it just works out of the box.

This is recursion’s sweet spot: tree-shaped data. A folder holds files and subfolders. Each subfolder is, again, a folder holding files and subfolders. The recursive shape of the data lines up with the recursive shape of the code, which is exactly when you should reach for recursion.

Recursion Limit and Stack Overflow

Every lift has a capacity sign: “Max 8 persons.” It is not there to annoy you, it is there so the cable does not snap. Python’s call stack has the same kind of sign. Pile on too many unfinished calls and Python refuses the next one, before your program can take the whole interpreter down with it. This limit is the guard rail of Python recursion.

📄 recursion_limit.py: Python’s safety net

import sys

print(f"Default recursion limit: {sys.getrecursionlimit()}")

# What happens when you exceed it
def infinite_recursion(n):
    return infinite_recursion(n + 1)

try:
    infinite_recursion(0)
except RecursionError as e:
    print(f"Caught: {e}")

# You CAN increase it (but usually shouldn't)
# sys.setrecursionlimit(10000)

▶ Output

Default recursion limit: 1000
Caught: maximum recursion depth exceeded

What happened here: Python caps recursion at 1000 calls deep by default, and our infinite_recursion function happily blew right past it. That cap is a safety net, not a bug. Without it, a runaway recursion would eat all your memory and crash the whole interpreter (a real stack overflow). The RecursionError stops you politely instead. If you are bumping into this limit, that is usually a sign your algorithm wants to be a loop, or that memoization could cut the depth down. Cranking up sys.setrecursionlimit() to muscle past it is almost always the wrong move, because you are just moving the crash a little further away, not fixing it.

Recursion vs Iteration: When to Use Which

A fair question at this point: if a loop and Python recursion can both compute a factorial, which should you actually use? Let me put them head to head and time them, because the numbers tell a clear story.

📄 recursion_vs_loop.py: factorial done both ways

# Iterative factorial: faster, less memory
def factorial_iter(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

# Recursive factorial: elegant, matches the math definition
def factorial_rec(n):
    if n <= 1:
        return 1
    return n * factorial_rec(n - 1)

# Both give the same answer
print(f"Iterative: {factorial_iter(10)}")
print(f"Recursive: {factorial_rec(10)}")

# Timing comparison
import time

start = time.time()
for _ in range(100000):
    factorial_iter(20)
iter_time = time.time() - start

start = time.time()
for _ in range(100000):
    factorial_rec(20)
rec_time = time.time() - start

print(f"\nIterative: {iter_time:.3f}s for 100K calls")
print(f"Recursive: {rec_time:.3f}s for 100K calls")

▶ Output

Iterative: 3628800
Recursive: 3628800

Iterative: 0.156s for 100K calls
Recursive: 0.294s for 100K calls

What happened here: Both functions return the same answer, but the recursive one takes noticeably longer for the same 100,000 calls. Every recursive call has to set up and tear down a stack frame, and that bookkeeping adds up. So the rule of thumb is simple. Reach for recursion when the data is recursive (trees, nested lists, graphs), the math definition is recursive, or a loop version would force you to build your own stack by hand.

Reach for a loop when you are marching through a flat sequence, when speed really matters, or when the depth could blow past Python’s recursion limit. Clean code first, and only trade elegance for speed when a measurement (like the one above) tells you to.

Common Mistakes

Mistake 1: Forgetting the base case

📄 mistake_no_base.py

# BAD: no base case
def countdown_bad(n):
    print(n)
    countdown_bad(n - 1)  # Never stops!

# GOOD: has a base case
def countdown_good(n):
    if n <= 0:
        return
    print(n)
    countdown_good(n - 1)

Mistake 2: Not moving toward the base case

📄 mistake_no_progress.py

# BAD: n never changes
def bad_recursion(n):
    if n == 0:
        return 0
    return n + bad_recursion(n)  # Still calling with n!

# GOOD: n decreases each time
def good_recursion(n):
    if n == 0:
        return 0
    return n + good_recursion(n - 1)  # n-1 moves toward base case

Mistake 3: Using recursion for simple loops

Do not recurse just to look clever. If a plain for loop does the job, use the loop. Recursion adds function-call overhead and eats stack space for no benefit on flat data. Save it for problems that are genuinely tree-shaped or nested.

Best Practices

• DO always define a clear base case before writing the recursive case
• DO use @lru_cache for recursive functions with overlapping subproblems (like Fibonacci)
• DO add print traces while debugging recursion, then remove them once it works
• DON’T use recursion for flat sequences where a loop works
• DON’T raise sys.setrecursionlimit() as a first resort; redesign the algorithm instead
• DON’T use naive recursion for Fibonacci or similar overlapping-subproblem functions

Conclusion

Python recursion is just a function calling itself to chew through smaller versions of the same problem. Every recursive function needs two parts: a base case that says when to stop, and a recursive case that breaks the problem down and steps toward that stopping point. Behind the scenes, the call stack grows with each call and shrinks as the calls return, which is both the elegance and the cost. When subproblems repeat, @lru_cache wipes out the wasted work for free. Use recursion for tree structures, nested data, and problems whose very definition is recursive. For plain flat sequences, a loop is the better tool.

Next up: Higher-Order Functions. The map, filter, and reduce trio takes your functions and applies them across whole collections at once. And if you want to see everything this series covers, from absolute basics to AI/ML, browse the Python + AI/ML tutorial series home.

Practice Exercises

1. Exercise 1: Write a recursive factorial.
2. Exercise 2: Recursively sum digits (1234 returns 10).
3. Exercise 3: Solve Tower of Hanoi for 4 disks, printing each move.

Frequently Asked Questions

Interview Questions on Python Recursion

These come from real screens and onsites. Practice answering before you read each answer.

Q: Walk me through what happens on the call stack when factorial(3) runs.

Python pushes a frame for factorial(3), which pauses at the multiplication and pushes a frame for factorial(2), which pauses and pushes factorial(1). That call hits the base case and returns 1, so the stack unwinds: factorial(2) computes 2 × 1 = 2 and returns, then factorial(3) computes 3 × 2 = 6. At the deepest point, three frames were alive at once, each holding its own value of n.

Q: Your script parses nested JSON configs recursively. It works for every client except one, whose file crashes with RecursionError. What do you check first?

First check how deeply that one client’s file is nested, because a structure more than roughly 1000 levels deep blows past Python’s default recursion limit even though the code is correct. Also check for a cycle, like an object that ends up referencing itself, which makes the recursion never reach a base case. The durable fix is rewriting the parser iteratively with an explicit stack; raising the limit with sys.setrecursionlimit() only postpones the crash.

Q: Your teammate, a developer named Anvay, ships a recursive Fibonacci function. fib(10) is instant but fib(45) hangs for minutes, and memory looks fine. What is wrong and what is the one-line fix?

Nothing is leaking; the function is recomputing the same subproblems exponentially many times, because fib(n) calls both fib(n-1) and fib(n-2) and each of those repeats work the other already did. The one-line fix is adding @functools.lru_cache above the function, which caches each result so every unique n is computed exactly once. That turns exponential time into linear time without touching the function body.

Q: Does Python optimize tail recursion?

No. CPython deliberately does not do tail-call optimization, so even a function whose recursive call is the very last statement still pushes a new stack frame every time and can hit RecursionError. The language designers chose this to keep full tracebacks intact for debugging. If depth is a concern, rewrite the function as a loop instead of relying on an optimization Python will not perform.

Q: How would you convert a recursive function into an iterative one when you are hitting the recursion limit?

Replace the implicit call stack with an explicit one: keep a plain list, append() the work you would have passed to a recursive call, and loop with pop() until the list is empty. For the nested-list flattener, that means pushing sub-lists onto the list instead of recursing into them. You get the same traversal with no depth limit, because a Python list can grow far beyond 1000 items.

Q: A junior developer named Aditi asks how ten paused calls of the same function can each remember a different value of n, when there is only one function. What do you tell her?

The function is one, but each call gets its own stack frame, a separate chunk of memory holding that call’s parameters and local variables. So factorial(4) and factorial(3) both run the same code, yet each frame stores its own n and its own return address. That is also why recursion costs memory in proportion to depth: all those frames stay alive until their calls return.

Further reading: for the full reference, see the official Python documentation.

Related Posts

Previous: Python: Lambda Functions, Anonymous Functions and When to Use

Next: Python: Higher-Order Functions, map(), filter(), reduce()

Series Home: Python + AI/ML Tutorial Series