iTechGuides is reader-supported. When you buy through links on our site, we may earn an affiliate commission. As an Amazon Associate I earn from qualifying purchases. Learn more
Recursion in Python is a technique where a function calls itself with a smaller or simpler input until it reaches a stopping condition. A sound recursive function needs both a base case that stops the calls and a recursive step that moves the input toward that case.
How recursion works in Python
Each time a function runs, Python creates a local symbol table for that call. A recursive call is a new function call, so it has its own local variables while earlier calls remain active. Those earlier calls resume after the recursive call returns, using the result to finish their work. The Python tutorial’s explanation of function definitions and calls describes this call behavior.
Think of a recursive function as having two jobs:
- Base case: Recognize an input that can be answered immediately and return a result without another recursive call.
- Recursive step: Reduce or simplify the input, call the function again, and use that call’s result.
If the recursive step does not make progress toward the base case, the calls may continue until Python raises RecursionError.
Factorial: a first recursive function
For a nonnegative integer n, the factorial is the product of the integers from 1 through n; by definition, 0! is 1. This function implements that definition:
#1 Best Overall
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)The base case is n == 0, which returns 1. For a positive integer, the recursive step multiplies n by the factorial of n - 1. For example, factorial(4) first becomes 4 * factorial(3), then 4 * 3 * factorial(2), and continues until factorial(0) returns 1. As the calls return, the pending multiplications resolve to 24.
This teaching implementation assumes a nonnegative integer. It does not validate its input; for instance, a negative integer will keep decreasing rather than reach zero. In production code, validate the input or choose a base case and error behavior that match the function’s intended contract.
Why recursion can repeat work
Recursion describes a way to structure a solution, not a guarantee that each subproblem is computed only once. A naïve recursive Fibonacci function branches into smaller calls that overlap, so it recalculates the same Fibonacci values repeatedly. When calls use repeatable, hashable arguments, functools.cache can retain results and reuse them.
Quick wins for a faster PC:
Fix the driver behind crashes, sound loss and screen glitchesFind Drivers →Repair Windows errors before they cause bigger problemsFix Now →Scan for outdated or missing drivers - takes under a minuteDriver Scan →Memoize results with functools.cache
from functools import cache
@cache
def factorial(n):
return n * factorial(n - 1) if n else 1cache is an unbounded cache, equivalent to lru_cache(maxsize=None), and was added in Python 3.9. The official functools documentation uses recursive factorial to illustrate caching: its first call to factorial(10) makes 11 recursive calls, while later calls with cached arguments can return without new calls for those arguments.
Caching helps when the same arguments recur, but it does not shorten a single chain of nested calls: the first computation still has to reach its base case. Because this cache is unbounded, it also retains entries; if a workload creates many distinct arguments, that retained data can use substantial memory. Use caching when repeated work justifies the memory cost, rather than adding it automatically to every recursive function.
What causes RecursionError?
RecursionError means Python detected that the maximum recursion depth was exceeded. It is a subclass of RuntimeError, as described in the built-in exceptions documentation. Common causes include a recursive step that never reaches its base case and a valid but very deep chain of calls.
When debugging, trace how each call changes its input. Check that the base case covers the intended endpoint and that every recursive step moves toward it. A negative input to the factorial example, for instance, never reaches its n == 0 base case.
How to check or change the recursion limit
sys.getrecursionlimit() returns the interpreter’s current recursion limit. Python uses a limit to help prevent infinite recursion from overflowing the C stack. The sys.setrecursionlimit() function can change the limit, but a safe upper bound depends on the platform; setting it too high can crash Python. See the Python sys documentation for both functions and their cautions.
import sys
print(sys.getrecursionlimit())For a very deep linear problem, first consider whether a loop or a redesigned algorithm can avoid a long chain of active calls. Raising the limit is not a routine fix: it does not repair a missing base case or repeated work, and an unsafe value risks process failure.
Independent reader supportYour contribution helps us test, update, and keep practical guides available for everyone.Recursion or iteration: which should you use?
Choose based on the shape of the problem and the costs it creates. Recursion can closely express nested structures or algorithms that break into smaller instances. Iteration often suits a long linear sequence, where a loop avoids maintaining a deep chain of function calls. The Python tutorial demonstrates Fibonacci generation with a while loop.
- Call depth: Estimate how many calls can be active at once. A long chain can approach the interpreter’s recursion limit.
- Repeated subproblems: If the same inputs recur, memoization may avoid duplicate computation; if the subproblems are distinct, caching may offer little benefit.
- Memory: Active recursive calls need their own call state. A cache retains results for reuse and can grow as new arguments appear.
- Clarity: Prefer the form that makes the algorithm’s structure easiest to understand and maintain—recursive for naturally nested or smaller-instance problems, iterative when a loop is simpler to trace.
These are design considerations, not a universal performance ranking. Without measurements for the actual workload, there is no basis to claim that recursion is categorically slower than iteration.
Further reading
The Recursive Book of Recursion by Al Sweigart focuses on recursive programming and includes Python and JavaScript examples. Publisher information is available from No Starch Press and Penguin Random House. It is an optional deeper resource, not a prerequisite for the examples above.
Quick Recap
Product prices and availability are accurate as of the date/time indicated and are subject to change. Any price and availability information displayed on Amazon at the time of purchase will apply.
