Recursion is when a function calls itself. Unlike a loop, recursive calls work inside each other — each waiting for the deeper call to finish before continuing.
The factorial of is defined as , with the base case .
Notice the pattern: to compute you only need — then multiply by . To compute you need , and so on, until you reach which is just 1. This is exactly how recursion works.
Every recursive function must have two parts:
How the call unfolds for factorial(4):
Each call is paused and stacked until the base case is reached, then the results unwind back up.
A simple example to build intuition. The sum from 1 to can be defined as:
Of course for this specific problem a loop or the formula n * (n + 1) // 2 is simpler. The point here is to see how recursion expresses the idea naturally.
Fibonacci numbers are a sequence where the first two are 0 and 1, and each next number is the sum of the two before it:
This definition translates directly into code:
This is clean, but it is very slow. Computing fib(40) already takes seconds because the same values are computed over and over. For example, fib(5) calls fib(4) and fib(3). fib(4) calls fib(3) and fib(2). fib(3) is computed twice. The total number of calls grows exponentially — .
The fix is memoization — cache results you have already computed. In Python, one line is enough:
With caching, each value is computed exactly once — the complexity drops to .
Given and , compute . The naive recursive definition:
This runs in — fine for small , too slow for .
We can do much better. Notice that for even :
So instead of multiplications we can compute once and square it. For odd we reduce to which is even:
This runs in — for that is just 30 recursive calls instead of a billion.
Note: Python's built-in pow(a, n, mod) already implements this and handles modular exponentiation too. In CP you should use that directly. Understanding the algorithm is important though.
sys.setrecursionlimitPython limits how deep recursion can go. The default limit is 1000 calls. Exceeding it raises RecursionError:
To fix this, increase the limit at the top of your solution:
In competitive programming, always set this when using recursion. A common value is 200000–300000.
The key skill with recursion is learning to trust the recursive call. When writing a recursive function, assume it already works correctly for smaller inputs — then just think about:
You do not need to trace the entire call stack in your head. Trust the definition.
Binary search can be written iteratively (which is usually preferred), but it maps naturally to recursion:
A classic recursion problem: move disks from peg A to peg C using peg B as auxiliary, never placing a larger disk on a smaller one.
The recursive insight: to move disks from A to C, first move the top disks from A to B, then move the largest disk from A to C, then move disks from B to C.
Output:
The total number of moves for disks is . This cannot be done faster — recursion reveals the lower bound naturally.
Recursion shines for enumeration problems. To generate all subsets of a list, at each step decide to include the current element or not:
For a list of elements there are subsets — each element is either included or excluded, giving two branches at every level.
This pattern — mark as used, recurse, unmark — is called backtracking and is one of the most important techniques in competitive programming. Recursion makes it natural to express.
| Concept | Key point |
|---|---|
| Base case | Always required — stops infinite recursion |
| Recursive case | Reduce to a smaller problem |
| Call stack | Each call waits for the deeper one to finish |
sys.setrecursionlimit | Set to 200000–300000 in CP |
| Memoization | Cache results with @lru_cache to avoid recomputation |
| Backtracking | Recurse → explore → undo |
| Fast exponentiation | via squaring — know the idea, use pow(a, n, mod) in practice |
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
print(factorial(5)) # 120
print(factorial(0)) # 1
factorial(4)
→ 4 * factorial(3)
→ 3 * factorial(2)
→ 2 * factorial(1)
→ 1 * factorial(0)
→ 1 ← base case
← 1 * 1 = 1
← 2 * 1 = 2
← 3 * 2 = 6
← 4 * 6 = 24
def sum_to(n):
if n == 0:
return 0
return n + sum_to(n - 1)
print(sum_to(5)) # 15
print(sum_to(10)) # 55
def fib(n):
if n == 0:
return 0
if n == 1:
return 1
return fib(n - 1) + fib(n - 2)
print(fib(10)) # 55
print(fib(15)) # 610
from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
if n == 0:
return 0
if n == 1:
return 1
return fib(n - 1) + fib(n - 2)
print(fib(100)) # 354224848179261915075 — instant
def power(a, n):
if n == 0:
return 1
return a * power(a, n - 1)
print(power(2, 10)) # 1024
def power(a, n):
if n == 0:
return 1
if n % 2 == 0:
half = power(a, n // 2)
return half * half # compute once, reuse!
return a * power(a, n - 1)
print(power(2, 10)) # 1024
print(power(3, 20)) # 3486784401
def count_down(n):
if n == 0:
return
count_down(n - 1)
count_down(5000) # RecursionError: maximum recursion depth exceeded
import sys
sys.setrecursionlimit(300000)
def binary_search(a, target, lo, hi):
if lo > hi:
return -1 # base case: not found
mid = (lo + hi) // 2
if a[mid] == target:
return mid
if a[mid] < target:
return binary_search(a, target, mid + 1, hi)
return binary_search(a, target, lo, mid - 1)
a = [1, 3, 5, 7, 9, 11, 15]
print(binary_search(a, 7, 0, len(a) - 1)) # 3
print(binary_search(a, 6, 0, len(a) - 1)) # -1
def hanoi(n, source, auxiliary, target):
if n == 0:
return
hanoi(n - 1, source, target, auxiliary)
print(f"Move disk {n} from {source} to {target}")
hanoi(n - 1, auxiliary, source, target)
hanoi(3, "A", "B", "C")
Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C
def subsets(a, index, current):
if index == len(a):
print(current)
return
# exclude a[index]
subsets(a, index + 1, current)
# include a[index]
subsets(a, index + 1, current + [a[index]])
subsets([1, 2, 3], 0, [])
# []
# [3]
# [2]
# [2, 3]
# [1]
# [1, 3]
# [1, 2]
# [1, 2, 3]
def permutations(a, current, used):
if len(current) == len(a):
print(current)
return
for i in range(len(a)):
if not used[i]:
used[i] = True
permutations(a, current + [a[i]], used)
used[i] = False
a = [1, 2, 3]
permutations(a, [], [False] * len(a))
# [1, 2, 3]
# [1, 3, 2]
# [2, 1, 3]
# [2, 3, 1]
# [3, 1, 2]
# [3, 2, 1]