Python Functions
Python Recursion
Recursion is when a function calls itself to solve a smaller version of the same problem, until it reaches a simple case it can answer directly. It is a powerful alternative to loops for certain problems.
Base Case and Recursive Case
Every recursive function needs two parts: a base case, which is the simplest version of the problem that can be answered directly without another function call, and a recursive case, where the function calls itself with a smaller or simpler input, moving closer to the base case each time.
Forgetting the base case (or never actually reaching it) causes infinite recursion, which eventually crashes with a RecursionError.
Factorial with Recursion
The factorial of n (written n!) is n * (n-1) * (n-2) * ... * 1. It maps beautifully onto recursion: factorial(0) is the base case (equal to 1), and factorial(n) is n times factorial(n-1) for anything else.
def factorial(n):
if n == 0: # base case
return 1
return n * factorial(n - 1) # recursive case
print(factorial(5)) # 5*4*3*2*1 = 120Fibonacci with Recursion
The Fibonacci sequence (0, 1, 1, 2, 3, 5, 8, ...) is another classic recursion example, where each number is the sum of the two before it.
def fibonacci(n):
if n <= 1: # base case
return n
return fibonacci(n - 1) + fibonacci(n - 2) # recursive case
for i in range(8):
print(fibonacci(i), end=" ")
# 0 1 1 2 3 5 8 13The recursive Fibonacci above is simple but slow for large n because it repeats the same calculations many times — an iterative loop or caching (memoization) is much faster in practice.
Python's Recursion Limit
Python protects against infinite recursion by capping how deep function calls can nest, by default around 1000 levels. Going beyond that raises a RecursionError. You can check or change it with the sys module, though changing it is rarely a good idea for beginners.
import sys
print(sys.getrecursionlimit()) # usually 1000Recursion vs Iteration
| Aspect | Recursion | Iteration (loops) |
|---|---|---|
| Readability | Often shorter for tree/nested problems | Often clearer for simple repeats |
| Memory | Uses more (each call stacks up) | Uses less (no call stack growth) |
| Speed | Usually slower due to function call overhead | Usually faster |
| Best for | Trees, nested structures, divide-and-conquer | Simple counting, summing, scanning |