1. Introduction
Recursion is a technique where a function calls itself to solve a smaller instance of the same problem. A recursive function typically has two parts: a base case that stops the recursion, and a recursive case that reduces the problem and calls the function again. Recursion is well suited to problems with a naturally recursive structure, such as factorials, Fibonacci numbers, tree traversal, and divide-and-conquer algorithms.
Cricket analogy: Recursion is like calculating a team's total boundary count by asking 'boundaries in this over plus boundaries in the rest of the innings', reducing down to a single-ball base case, well suited to tree-like tournament bracket calculations too.
Every recursive call adds a new frame to the call stack. Python tracks these frames and enforces a maximum recursion depth to prevent a runaway recursive function from crashing the interpreter.
Cricket analogy: Every recursive call is like a new fielder added to a relay throw chain -- each holds the ball briefly before passing it back -- and if the chain of throws (calls) never breaks, the whole relay collapses under too many hands.
2. Syntax
def recursive_function(n):
if n <= 0: # base case
return 0
return n + recursive_function(n - 1) # recursive case
3. Explanation
The base case is the condition under which the function returns a value directly, without making another recursive call; it is what eventually stops the recursion. The recursive case calls the function again with an argument that moves closer to the base case (for example, n - 1 instead of n). Without a correct base case, or if the recursive case never actually reaches it, the function will call itself indefinitely.
Cricket analogy: The base case is like the final ball of a super over that ends play directly, while the recursive case is like each preceding ball moving the match closer to that final ball -- skip a real base case and the match never ends.
If a recursive function has no base case, or the base case is unreachable due to a logic error, Python will keep calling the function until it exceeds the maximum recursion depth (by default around 1000 frames in CPython) and raises a RecursionError. This is analogous to an infinite loop, but manifesting through the call stack instead of a while loop condition. Always verify that every recursive path makes measurable progress toward the base case.
4. Example
def factorial(n):
if n in (0, 1): # base case
return 1
return n * factorial(n - 1) # recursive case
def fibonacci(n):
if n < 2: # base case
return n
return fibonacci(n - 1) + fibonacci(n - 2) # recursive case
print(factorial(5))
print([fibonacci(i) for i in range(8)])
import sys
print(sys.getrecursionlimit())
5. Output
120
[0, 1, 1, 2, 3, 5, 8, 13]
1000
6. Key Takeaways
- A recursive function needs a base case that terminates the recursion and a recursive case that progresses toward it.
- Each recursive call adds a frame to the call stack, consuming memory until the base case is reached.
- A missing or unreachable base case leads to a RecursionError once Python's recursion limit is exceeded.
- sys.getrecursionlimit() reports the maximum recursion depth (1000 by default in standard CPython) and sys.setrecursionlimit() can change it, though raising it risks a stack overflow crash.
- Recursive solutions are elegant for naturally recursive problems but can be less efficient than iterative solutions without memoization (e.g. naive Fibonacci recomputes overlapping subproblems).
Practice what you learned
1. What are the two essential parts of a correct recursive function?
2. What exception does Python raise when a recursive function calls itself too many times without reaching a base case?
3. What does factorial(5) return, given the recursive definition in the Example?
4. What does sys.getrecursionlimit() return by default in a standard CPython installation?
5. Why is a missing base case dangerous in a recursive function, compared to a missing terminating condition in a while loop?
6. In the naive fibonacci(n) implementation shown, why can it become slow for larger n?
Was this page helpful?
You May Also Like
Functions in Python
How to define, call, and document reusable blocks of code with Python functions, including the def keyword and implicit None return.
Function Arguments in Python
Understanding positional, positional-only, keyword-only, *args, and **kwargs arguments in Python function signatures.
Scope and Namespaces in Python
Understanding Python's LEGB scope resolution order and how the global and nonlocal keywords let functions modify variables outside their local scope.
while Loop in Python
Learn how Python's while loop repeats code as long as a condition stays True, and how to avoid infinite loops.
Related Reading
Related Study Notes in Programming
Browse all study notesApache Spark Study Notes
Programming · 30 topics
ProgrammingApache Flink Study Notes
Programming · 30 topics
ProgrammingHadoop Study Notes
Programming · 30 topics
ProgrammingSnowflake Study Notes
Programming · 30 topics
ProgrammingApache Airflow Study Notes
Programming · 30 topics
Programmingdbt (Data Build Tool) Study Notes
Programming · 30 topics