Have you ever stood between two mirrors and seen your reflection repeat again and again? Or opened a set of Russian dolls, where each doll contains a smaller doll, until you reach the tiniest one?
That idea, something defined in terms of a smaller version of itself, is called recursion. In programming, it means a function that calls itself.
Recursion is a key idea for Data Structures and Algorithms (trees, backtracking, divide and conquer), so it's worth understanding well.
What is Recursion?
Recursion is a technique where a function solves a problem by calling itself on a smaller version of the same problem.
A function that calls itself is called a recursive function.
Every correct recursive function has two parts:
Part | What it does |
|---|---|
Base case | The simplest version of the problem, answered directly without calling the function again. This is where recursion stops. |
Recursive case | The function calls itself with a smaller input, moving closer to the base case. |
A First Example: Countdown
def countdown(n):
if n == 0: # base case
print("Liftoff!")
return
print(n)
countdown(n - 1) # recursive case
countdown(3)Output:
3
2
1
Liftoff!Each call prints a number and then calls countdown with a number one smaller. When n reaches 0, the base case stops the chain.
Of course, a simple while loop could do this too. Recursion becomes really useful when a problem naturally breaks into smaller copies of itself.
Factorial: The Classic Example
The factorial of n (written n!) is the product of all numbers from 1 to n:
5! = 5 × 4 × 3 × 2 × 1 = 120Notice that 5! = 5 × 4!, and 4! = 4 × 3!, and so on. The problem contains a smaller copy of itself:
n! = n × (n - 1)! for n > 1
1! = 1 (and 0! = 1)That translates directly into code:
def factorial(n):
if n <= 1: # base case
return 1
return n * factorial(n - 1) # recursive case
print(factorial(5))
print(factorial(0))
print(factorial(10))Output:
120
1
3628800How Recursion Works: The Call Stack
Every time a function is called, Python creates a frame that stores that call's local variables. Frames are kept on the call stack. A new call is pushed on top; when a call returns, its frame is removed.
Here's what happens for factorial(4):
Going down (calls are pushed):
factorial(4) = 4 * factorial(3)
factorial(3) = 3 * factorial(2)
factorial(2) = 2 * factorial(1)
factorial(1) = 1 <-- base case
Coming back up (results are returned):
factorial(1) returns 1
factorial(2) returns 2 * 1 = 2
factorial(3) returns 3 * 2 = 6
factorial(4) returns 4 * 6 = 24Each call waits for the call below it to finish, then uses its result. You can see this order by adding some prints:
def factorial(n):
print(f"Calling factorial({n})")
if n <= 1:
return 1
result = n * factorial(n - 1)
print(f"factorial({n}) returns {result}")
return result
factorial(3)Output:
Calling factorial(3)
Calling factorial(2)
Calling factorial(1)
factorial(2) returns 2
factorial(3) returns 6Complexity
factorial(n) makes n calls, each doing a constant amount of work, so its time complexity is O(n). Because up to n frames sit on the stack at once, it also uses O(n) extra space. An iterative loop would use only O(1) space.
More Recursive Examples
Sum of Digits
The sum of digits of 1234 is 4 + (sum of digits of 123):
def sum_of_digits(n):
if n < 10: # a single digit
return n
return n % 10 + sum_of_digits(n // 10)
print(sum_of_digits(1234))
print(sum_of_digits(9075))Output:
10
21Power (an)
def power(a, n):
if n == 0:
return 1
return a * power(a, n - 1)
print(power(2, 10))
print(power(3, 4))Output:
1024
81Reversing a String
The reverse of a string is (reverse of everything after the first character) followed by the first character:
def reverse(text):
if len(text) <= 1:
return text
return reverse(text[1:]) + text[0]
print(reverse("python"))Output:
nohtypPalindrome Check
A string is a palindrome if its first and last characters match and the middle part is also a palindrome:
def is_palindrome(text):
if len(text) <= 1:
return True
if text[0] != text[-1]:
return False
return is_palindrome(text[1:-1])
print(is_palindrome("madam"))
print(is_palindrome("racecar"))
print(is_palindrome("python"))Output:
True
True
FalseFibonacci and the Cost of Repeated Work
In the Fibonacci sequence, each number is the sum of the two before it:
0, 1, 1, 2, 3, 5, 8, 13, 21, ...
fib(0) = 0, fib(1) = 1, fib(n) = fib(n-1) + fib(n-2)This function makes two recursive calls:
def fib(n):
if n <= 1:
return n
return fib(n - 1) + fib(n - 2)
for i in range(10):
print(fib(i), end=" ")Output:
0 1 1 2 3 5 8 13 21 34It looks elegant, but it is very slow for larger n. Look at the calls made for fib(4):
fib(4)
/ \
fib(3) fib(2)
/ \ / \
fib(2) fib(1) fib(1) fib(0)
/ \
fib(1) fib(0)fib(2) is calculated twice. For bigger inputs, the same values are recalculated again and again, and the number of calls grows exponentially (roughly O(2n) time; the stack depth is only O(n)). Let's count:
calls = 0
def fib(n):
global calls
calls += 1
if n <= 1:
return n
return fib(n - 1) + fib(n - 2)
print(fib(30))
print("Calls made:", calls)Output:
832040
Calls made: 2692537Over 26 lakh calls to compute one number!
Fixing It with Memoization
Memoization means remembering results that were already calculated. Python's functools module provides cache (available since Python 3.9) to do this automatically:
from functools import cache
@cache
def fib(n):
if n <= 1:
return n
return fib(n - 1) + fib(n - 2)
print(fib(30))
print(fib(100))Output:
832040
354224848179261915075The @cache line is a decorator (covered in the Decorators chapter). It stores each result, so every fib(k) is calculated only once. The time complexity drops from exponential to O(n). This idea is the foundation of Dynamic Programming.
Recursion Limit and RecursionError
Each call adds a frame to the stack, and the stack isn't infinite. Python sets a limit on how deep recursion can go:
import sys
print(sys.getrecursionlimit())Output:
1000If you forget the base case, the function keeps calling itself until it hits this limit:
def countdown(n):
print(n)
countdown(n - 1) # no base case!
countdown(3)This prints numbers for a while and then stops with:
RecursionError: maximum recursion depth exceededYou can raise the limit with sys.setrecursionlimit(), but that's usually a sign you should use a loop instead. Unlike some languages, Python does not perform tail-call optimisation, so deep recursion always uses stack space.
Common Mistakes
Missing base case: the function never stops and raises
RecursionError.Not moving towards the base case: for example, calling
factorial(n)instead offactorial(n - 1).Forgetting to
returnthe recursive call: writingn * factorial(n - 1)withoutreturnmakes the function returnNone.Wrong base case for some inputs:
if n == 1fails forfactorial(0):ngoes 0, -1, -2, ... and never reaches 1, so it ends in aRecursionError.if n <= 1is safer.
Recursion vs Iteration
Recursion | Iteration (loops) |
|---|---|
Function calls itself | Repeats using |
Stops at the base case | Stops when the loop condition is false |
Uses stack space for every call | Usually uses constant extra space |
Can hit | No depth limit |
Natural for trees, backtracking, divide and conquer | Natural for simple repetition and counting |
Any recursive solution can be rewritten with loops (sometimes with an explicit stack). Choose whichever is clearer for the problem.
Summary
A recursive function calls itself on a smaller version of the problem.
It always needs a base case (where it stops) and a recursive case (that moves towards the base case).
Python tracks calls on the call stack; the default recursion limit is 1000.
Recursion uses O(depth) extra space for stack frames.
Repeated sub-problems (like naive Fibonacci) can be fixed with memoization.
Practice Problems
Print the numbers from 1 to
nusing recursion (no loops).Count the number of digits in a positive integer.
Find the GCD of two numbers using Euclid's rule:
gcd(a, b) = gcd(b, a % b), withgcd(a, 0) = a.Count how many times a character appears in a string.
Convert a decimal number to its binary string (for example,
10becomes"1010").
Trust the recursion: assume the smaller call already works, and focus on how to use its answer plus a correct base case.