1. Home
  2. Blog
  3. Software Development

Software Development

Python Recursion Explained: 9 Examples, Memoization and the Recursion Limit

Python recursion means a function solving a problem by calling itself on a smaller piece of it. Learn base cases with a traced call stack, nine practical examples, how memoization turned 2.7 million calls into 31, why Python stops at about 1,000 levels, and when a loop is the better choice.

9 min read
Python recursion explained: 9 examples, memoization and the recursion limit

Key takeaways

  • Python recursion needs a base case that stops it and a recursive case that moves toward the base case.
  • Python’s default recursion limit is 1000; going deeper raises RecursionError. Our 5,000-level count failed.
  • Naive recursive Fibonacci made 2,692,537 calls for fib(30); functools.lru_cache cut that to 31 computed values.
  • Recursion shines for trees, nested data and divide-and-conquer. For simple counting, loops are faster and safer.

Some problems contain smaller copies of themselves: a folder holds folders, a JSON object holds objects, a sorted list splits into two sorted halves. Python recursion lets you write the solution for one level and let the function handle the rest by calling itself. Done well, it produces short, clear code. Done carelessly, it crashes with RecursionError or runs for minutes.

Every example ran on Python 3.13.6, with output copied from the run. If functions are new to you, start with our Python tutorial for beginners.

What is recursion in Python?

A recursive function is a function that calls itself. Each call gets its own local variables on Python’s call stack, and waits for the inner call to return before it finishes. The calls pile up until one of them hits a stopping condition, then the results flow back up the stack one by one.

The two parts: base case and recursive case

  • Base case: the simplest input, answered directly without another call. Without it, the function never stops.
  • Recursive case: breaks the problem into a smaller version and calls itself on that. Each call must move closer to the base case.

Example 1: factorial

def fact(n):
    return 1 if n <= 1 else n * fact(n - 1)

print(fact(5))   # 120

The definition mirrors the maths: 5! = 5 x 4!, and 1! = 1. The base case is n <= 1; the recursive case multiplies n by the factorial of a smaller number.

Example 2: tracing the call stack

def fact_trace(n, depth=0):
    print("  " * depth + f"fact({n})")
    r = 1 if n <= 1 else n * fact_trace(n - 1, depth + 1)
    print("  " * depth + f"-> {r}")
    return r

fact_trace(3)
# fact(3)
#   fact(2)
#     fact(1)
#     -> 1
#   -> 2
# -> 6

The indentation shows the stack growing as calls go down, and shrinking as results return. fact(3) cannot finish until fact(2) returns, which waits for fact(1). Adding a depth parameter like this is the quickest way to debug any recursive function.

Example 3: the recursion limit

import sys
print(sys.getrecursionlimit())   # 1000

def count(n):
    return 0 if n == 0 else 1 + count(n - 1)

count(5000)
# RecursionError: maximum recursion depth exceeded

Every call uses a stack frame, and CPython caps the depth to protect itself from running out of memory or crashing. The default limit is 1000 frames. You can raise it with sys.setrecursionlimit(), but that only moves the cliff; very deep recursion can still crash the interpreter. If an input can be thousands of levels deep, such as a long linked list, use a loop instead. Our exception handling guide explains catching errors like this.

Example 4: naive Fibonacci and exponential calls

def fib(n):
    return n if n < 2 else fib(n - 1) + fib(n - 2)

# fib(30) = 832040, calls = 2,692,537, time = 226 ms

Each call spawns two more, and the same values are recomputed again and again: fib(28) is calculated twice, fib(27) three times, and so on. The number of calls grows exponentially, so fib(40) needs about 331 million calls, roughly 123 times as many, which at this rate means about half a minute. Elegant code, terrible algorithm.

Example 5: memoization with lru_cache

import functools

@functools.lru_cache(maxsize=None)
def fib_m(n):
    return n if n < 2 else fib_m(n - 1) + fib_m(n - 2)

fib_m(30)               # 832040
fib_m.cache_info()      # CacheInfo(hits=28, misses=31, maxsize=None, currsize=31)
# time: about 25 microseconds

Memoization stores each result the first time it is computed. Only 31 distinct values were ever calculated, and the run dropped from 226 ms to about 25 microseconds, roughly 9,000 times faster. Reach for it whenever a recursive function solves the same subproblem more than once; our functools guide covers lru_cache and cache.

Memoization does not fix depth, though. Calling fib_m(3000) on an empty cache still raised RecursionError, because the first call has to descend 3,000 levels. The iterative version has neither problem:

def fib_iter(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

fib_iter(30)                 # 832040
len(str(fib_iter(1000)))     # 209 digits, no recursion needed

Example 6: flattening nested lists

def flatten(x):
    return [y for i in x for y in (flatten(i) if isinstance(i, list) else [i])]

flatten([1, [2, [3, [4, 5]], 6], [[7]]])   # [1, 2, 3, 4, 5, 6, 7]

You do not know in advance how deep the nesting goes, which is exactly when recursion helps. Each call handles one level and delegates any inner list to another call. The same shape works for nested JSON from an API; see Python JSON.

Example 7: walking a tree

tree = {"name": "root", "children": [
    {"name": "src", "children": [
        {"name": "app.py", "children": []},
        {"name": "utils", "children": [{"name": "io.py", "children": []}]}]},
    {"name": "README.md", "children": []}]}

def show(node, depth=0):
    print("  " * depth + node["name"])
    for c in node["children"]:
        show(c, depth + 1)

def size(node):
    return 1 + sum(size(c) for c in node["children"])

show(tree)
# root
#   src
#     app.py
#     utils
#       io.py
#   README.md
print(size(tree))   # 6

Trees are recursion’s natural home: a tree is a node plus smaller trees. The base case is implicit, since a node with no children simply loops zero times. Real-world versions include menus, comment threads, organisation charts and the HTML DOM. A directory walk with os.scandir followed the same pattern in our run and returned ['a', 'a/b', 'a/b/f.txt', 'top.txt']; in production, os.walk or pathlib‘s rglob already do this for you.

Example 8: binary search

def bsearch(a, x, lo=0, hi=None):
    hi = len(a) - 1 if hi is None else hi
    if lo > hi:
        return -1
    mid = (lo + hi) // 2
    if a[mid] == x:
        return mid
    return bsearch(a, x, mid + 1, hi) if a[mid] < x else bsearch(a, x, lo, mid - 1)

a = list(range(0, 2_000_000, 2))     # one million even numbers
bsearch(a, 1_234_568)   # 617284
bsearch(a, 7)           # -1

Divide-and-conquer algorithms halve the problem each call, so the depth stays tiny: about 20 levels for a million items, far below the limit. Merge sort and quicksort work the same way. For real code, the standard library’s bisect module is faster and tested.

Example 9: permutations

def perms(s):
    if len(s) <= 1:
        return [s]
    return [c + p for i, c in enumerate(s) for p in perms(s[:i] + s[i+1:])]

perms("abc")   # ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']

Pick each character as the first, then recursively permute the rest. This backtracking pattern also solves subsets, combinations, Sudoku and maze search. For production use, itertools.permutations is faster and lazy; see our itertools guide.

Tip: before writing a recursive function, say the base case and the “smaller problem” out loud. If you cannot name both, the design is not ready.

Python has no tail call optimisation

def sum_tail(n, acc=0):
    return acc if n == 0 else sum_tail(n - 1, acc + n)

sum_tail(5000)   # RecursionError

Some languages reuse the stack frame when the recursive call is the very last action (a tail call), so tail-recursive functions never run out of stack. CPython deliberately does not, to keep tracebacks complete. Writing your function in tail-recursive style therefore buys nothing in Python; convert it to a loop instead.

Recursion vs loops: speed and safety

Task Recursive Alternative
fact(500) vs math.factorial(500) 88.5 microseconds 8.8 microseconds
Count to 100,000 RecursionError Loop: works
fib(30) 226 ms naive, 25 microseconds memoized Loop: instant, no depth limit

Function calls in Python have real overhead, so a recursive version is usually slower than a loop or a built-in. Choose recursion when the data is recursive (trees, nested structures) or when the recursive version is much clearer, and the depth is known to be small. Choose a loop when the depth could be large or performance matters. You can also convert any recursion to a loop with an explicit stack list. Generators with yield from are another elegant way to walk trees lazily.

Common recursion mistakes

  • Missing or unreachable base case, leading to RecursionError.
  • Not shrinking the problem, for example calling f(n) instead of f(n - 1).
  • Repeated subproblems without memoization, causing exponential time.
  • Mutable default arguments such as def walk(node, seen=[]), which share state between calls.
  • Forgetting to return the recursive call’s result, so the function returns None.
  • Raising the recursion limit to hide a design problem.

Final thoughts

Python recursion is a way of thinking: solve the smallest case directly, and express every other case in terms of a smaller one. It makes tree walking, nested data, divide-and-conquer and backtracking remarkably clean. Respect the 1,000-frame limit, memoize repeated subproblems, and switch to a loop when depth can grow. Used that way, recursion is one of the most expressive tools in your Python kit.

Frequently asked questions

What is recursion in Python?

Recursion is when a function calls itself to solve a smaller version of the same problem. It needs a base case that returns directly and a recursive case that moves toward that base case.

What is the maximum recursion depth in Python?

The default limit is 1000 frames, which you can read with sys.getrecursionlimit. Exceeding it raises RecursionError. You can raise it with sys.setrecursionlimit, but deep recursion should usually become a loop.

How do I fix RecursionError in Python?

Check that the base case is reachable and that each call shrinks the problem. If the input is genuinely deep, rewrite the function as a loop or use an explicit stack instead of raising the limit.

Is recursion slower than a loop in Python?

Usually yes, because each function call has overhead. In our test a recursive factorial of 500 took about ten times longer than math.factorial. Choose recursion for clarity on recursive data, not for speed.

What is memoization in recursion?

Memoization caches the result of each call so repeated inputs are not recomputed. In Python, the functools.lru_cache decorator adds it in one line and turned millions of Fibonacci calls into 31 computed values in our test.

Keep learning

Work with Stack Quora

Need help with testing, WordPress or SEO?

We help teams ship better software and grow their sites. Tell us what you are working on and we will suggest a clear next step.

Keep reading

More guides on testing, AI & modern development

Enjoyed this article? Pick a topic and jump straight into our newest tutorials.

Artificial Intelligence

Linear Regression in Python: Least Squares From Scratch, With R Squared

Linear regression in Python from scratch: closed form, NumPy least squares and gradient descent, R squared, RMSE, outliers and curved…

Read article →
Software Development

301 vs 302 Redirect: Differences, SEO Impact, 307 and 308

301 vs 302 redirect: the differences, SEO impact, 307 and 308, method changes, redirect chains and loops, all tested on…

Read article →
DevOps

Git Remote Explained: Add, Set-URL, Rename, Remove and Push URLs

Git remote explained: add, set-url, separate push URLs, rename, remove and prune, plus how to avoid leaking tokens in remote…

Read article →
Test Automation

Pytest Mock: mocker.patch, spy, side_effect and autospec Explained

Pytest mock explained: mocker.patch, return_value, side_effect, spy, autospec and PropertyMock, with tested examples for APIs, clocks and retries.

Read article →
Software Testing

System Testing Explained: Types, Process and a Real End-to-End Example

System testing explained: types, entry and exit criteria, the process, and a real end-to-end test suite run against a small…

Read article →
Databases & SQL

SQL Random Rows: How to Select Random Rows Fast and Fairly

SQL random rows: how to select random rows fast and fairly, timing ORDER BY RANDOM, offsets and ID jumps, and…

Read article →
Databases & SQL

SQL Median: 4 Ways to Calculate the Median, With Tested Queries

SQL median explained: four tested ways to calculate the median, including percentile functions, window ranks, offsets and per group medians.

Read article →
Software Development

JavaScript Regex Explained: Patterns, Flags, Groups and Pitfalls

JavaScript regex explained: literals, flags, groups, named groups, lookarounds, matchAll, replace and the catastrophic backtracking trap, tested in Node.

Read article →
Software Development

Python property: Getters, Setters, Validation and cached_property

Python property explained: getters, setters, deleters, validation, read-only and computed attributes, and cached_property, with tested code.

Read article →
Software Development

Python Enum Explained: auto, IntEnum, StrEnum, Flag and Best Practices

Python enum explained with tested examples: Enum, auto, IntEnum, StrEnum, Flag, aliases, unique, JSON serialisation and match statements.

Read article →
Artificial Intelligence

Naive Bayes Classifier Explained: Build a Spam Filter in Python

Naive Bayes classifier explained by building a spam filter in Python: Bayes rule, the naive assumption, Laplace smoothing, log probabilities…

Read article →
Software Development

401 vs 403: Unauthorized vs Forbidden, and When to Use Each

401 vs 403 explained: authentication vs authorization, the WWW-Authenticate header, when to return 404 instead, client reactions and a tested…

Read article →
DevOps

Git Branch Explained: Create, Switch, Rename, Delete and Recover

Git branch explained with tested commands: list, create, switch, rename, delete, merged checks, recovering deleted branches, remote tracking and naming.

Read article →
Test Automation

Pytest raises: Testing Exceptions, match and excinfo

Pytest raises explained with tested examples: match regexes, excinfo, custom and chained exceptions, parametrized error cases, pytest.warns and common mistakes.

Read article →
Software Testing

Non Functional Testing: Types, Metrics and a Real Load Test

Non functional testing explained: 10 key types, measurable requirements, latency percentiles and what a small real load test revealed about…

Read article →
Databases & SQL

SQL ROUND Function: Decimals, Ties, CEIL, FLOOR and Money

SQL ROUND explained with tested queries: decimals, tie rules, the 2.675 float trap, negative digits, CEIL, FLOOR, truncation and rounding…

Read article →
Databases & SQL

Recursive CTE in SQL: Hierarchies, Paths, Series and Cycles

Recursive CTE in SQL explained with tested queries: org charts with levels and paths, walking up a tree, team sizes,…

Read article →
Software Development

JavaScript Deep Copy: structuredClone vs JSON vs Spread, Tested

JavaScript deep copy compared: spread, Object.assign, the JSON trick, structuredClone and a custom copy, tested on Dates, Maps, Sets, BigInt…

Read article →
Artificial Intelligence

K Means Clustering Explained: How It Works, With Python Code

K means clustering explained: the algorithm, a from-scratch NumPy version, choosing k with the elbow and silhouette methods, k-means++, scaling…

Read article →
DevOps

Git Log Explained: 15 Useful Commands and Pretty Formats

Git log explained with 15 tested commands: oneline, graph, filters by author, date, message and code, file history, stats, pretty…

Read article →
Test Automation

Pytest conftest.py Explained: Shared Fixtures, Hooks and Overrides

Pytest conftest.py explained with a tested suite: shared fixtures, scope and teardown, folder overrides, autouse, custom options, markers and useful…

Read article →
Software Testing

Usability Testing: Methods, Metrics, SUS Score and Checklist

Usability testing explained: methods, planning, writing tasks, running sessions, metrics, SUS scoring, how many users you need and a practical…

Read article →
Databases & SQL

SQL UPDATE Statement: Safe Updates, UPDATE With JOIN and RETURNING

The SQL UPDATE statement explained with tested examples: WHERE guards, CASE updates, UPDATE with JOIN, the subquery NULL trap, RETURNING…

Read article →
Databases & SQL

SQL COUNT: COUNT(*) vs COUNT(column) vs COUNT(DISTINCT) Explained

SQL COUNT explained: COUNT(*) vs COUNT(column) vs COUNT(DISTINCT), NULLs and empty strings, conditional counts, HAVING, the LEFT JOIN trap and…

Read article →
Artificial Intelligence

K Nearest Neighbors (KNN) Explained: How It Works, With Python Code

K nearest neighbors explained: the KNN algorithm, a from-scratch NumPy version, choosing k, feature scaling, distance metrics, regression and vector…

Read article →
DevOps

Git Rebase Interactive: Squash, Fixup, Reword and Autosquash

Git rebase interactive explained step by step: pick, reword, squash, fixup, edit, drop, autosquash, conflicts and undoing a rebase with…

Read article →
Software Testing

Alpha vs Beta Testing: Key Differences, Exit Criteria and Checklist

Alpha vs beta testing compared: who tests, what each phase finds, entry and exit criteria, how to run a beta,…

Read article →
Test Automation

Pytest Monkeypatch: 10 Tested Examples for Env Vars, Time and APIs

Pytest monkeypatch explained with 10 passing tests: environment variables, functions, config, time, sleeps, paths, blocking the network and the wrong-target…

Read article →
Artificial Intelligence

Softmax Function Explained: Formula, Python Code and Stable Version

The softmax function explained: formula, worked example, NumPy code, the stable version that avoids NaN, temperature, cross-entropy and softmax vs…

Read article →
DevOps

Git Diff Explained: Staged Changes, Branches and Commits

Git diff explained: read the output, compare unstaged and staged changes, commits and branches, two dots vs three dots, and…

Read article →
Test Automation

Pytest Xdist: Run Tests in Parallel and Cut Test Time

Run pytest tests in parallel with pytest-xdist: install, the -n option, distribution modes, real timings and how to fix shared-state…

Read article →
Software Testing

Verification vs Validation in Software Testing: Example and Table

Verification vs validation in software testing explained with a comparison table and a tested coupon example where every spec test…

Read article →
Artificial Intelligence

Levenshtein Distance: Formula, Worked Table and Python Code

Levenshtein distance explained: the edit operations, the dynamic programming table for kitten and sitting, Python code with two-row memory, normalised…

Read article →
DevOps

Gitignore: Patterns, Negation and Fixing Tracked Files

A tested gitignore guide: pattern rules, leading and trailing slashes, negation with !, the ignored parent folder trap, git check-ignore…

Read article →
Software Testing

Acceptance Criteria: Given When Then Examples and Checklist

How to write acceptance criteria testers can run: rule-based and Given When Then formats, a worked discount code example turned…

Read article →
Test Automation

Python Unittest: Assert Methods, setUp and Mocks With Examples

A practical Python unittest tutorial: TestCase, assert methods, setUp and tearDown, subTest, skips, expected failures and mock, with a test…

Read article →