Recursion is a programming technique in which a function calls itself to solve a problem. A recursive solution expresses a problem in terms of smaller versions of the same problem, together with a simple case that stops the calling chain. The two essential ingredients are a base case, which can be solved directly without recursion, and a recursive case, which reduces the problem towards the base case.
Recursion often produces short, elegant and readable solutions for problems that are naturally defined in terms of themselves, such as computing factorials, Fibonacci numbers, powers, and the Fibonacci-like structures of trees and fractals. The mathematical definition of the factorial, n! = n x (n-1)!, is literally a recursive definition, and translating it into a function is straightforward.
This chapter explains how recursion works, the roles of the base case and recursive case, how to trace a recursive function, the common recursive algorithms of factorial, Fibonacci, power and sum of digits, and the concept of the call stack. It also contrasts recursion with iteration and discusses the efficiency and limits of recursion, such as the recursion depth limit. Recursion questions appear as output tracing, code-writing and concept questions in the board examination.
A recursive function has two parts. The base case is a condition under which the function returns a value directly without calling itself; without it, the recursion never ends. The recursive case calls the function again with a smaller or simpler input, moving towards the base case.
def factorial(n):
if n == 0: # base case
return 1
return n * factorial(n - 1) # recursive case
print(factorial(5)) # 120
For factorial(5), the function computes 5 x factorial(4), which is 5 x (4 x factorial(3)), and so on until factorial(0) returns 1. Only then do the multiplications unwind to produce 120.
If the base case is missing or unreachable, the function keeps calling itself forever. Python detects this and raises a RecursionError after a certain number of calls (the recursion limit, by default about 1000). Every recursive function must guarantee progress toward its base case.
Each call to a recursive function creates a new frame on the call stack, holding its own parameters and local variables. The frames accumulate as the recursion descends, and they are removed as each call returns. This is the same stack data structure studied in earlier chapters. Because each frame occupies memory, deep recursion can exhaust the stack.
Tracing factorial(4) step by step:
factorial(4) = 4 * factorial(3)
factorial(3) = 3 * factorial(2)
factorial(2) = 2 * factorial(1)
factorial(1) = 1 * factorial(0)
factorial(0) = 1 base case reached
factorial(1) = 1 * 1 = 1
factorial(2) = 2 * 1 = 2
factorial(3) = 3 * 2 = 6
factorial(4) = 4 * 6 = 24
The calls go down until the base case, then the returns unwind in reverse order.
The Fibonacci sequence is defined as fib(0) = 0, fib(1) = 1, and fib(n) = fib(n-1) + fib(n-2) for n > 1. The recursive version follows the definition directly but recomputes many values, giving exponential time in the worst case.
def fib(n):
if n <= 1: # base cases
return n
return fib(n - 1) + fib(n - 2) # recursive case
for i in range(7):
print(fib(i), end=" ") # 0 1 1 2 3 5 8
Computing x raised to the power n recursively: x^0 = 1, and x^n = x * x^(n-1).
def power(x, n):
if n == 0:
return 1
return x * power(x, n - 1)
print(power(2, 5)) # 32
def sum_digits(n):
if n == 0:
return 0
return n % 10 + sum_digits(n // 10)
print(sum_digits(1234)) # 10
The function adds the last digit to the recursive sum of the remaining digits.
def reverse_string(s):
if s == "":
return ""
return reverse_string(s[1:]) + s[0]
print(reverse_string("PYTHON")) # NOHTYP
def gcd(a, b):
if b == 0:
return a
return gcd(b, a % b)
print(gcd(48, 18)) # 6
Any problem solved recursively can also be solved with a loop. Iteration uses explicit loops and an accumulator; recursion uses function calls and the call stack. Recursive code is often shorter and closer to the mathematical definition, while iterative code is usually faster and uses constant extra memory. The choice depends on readability, efficiency and the nature of the problem.
def factorial_iterative(n):
result = 1
for i in range(1, n + 1):
result *= i
return result
print(factorial_iterative(5)) # 120
Both versions produce the same answer, but the iterative one avoids deep call stacks.
Recursive solutions can be inefficient. The naive Fibonacci recursion recomputes fib(k) many times for the same k, leading to exponential time O(2^n). Techniques such as memoization (storing already-computed results) convert such recursion to near-linear time. Every recursive function should be examined for wasted recomputation.
memo = {0: 0, 1: 1}
def fib_memo(n):
if n not in memo:
memo[n] = fib_memo(n - 1) + fib_memo(n - 2)
return memo[n]
print(fib_memo(30)) # 832040, computed quickly
Python limits the depth of recursion to prevent the call stack from overflowing. The default recursion limit is usually 1000; functions can check and change it with sys.getrecursionlimit() and sys.setrecursionlimit(). Exceeding the limit raises RecursionError. Problems requiring very deep recursion are better solved iteratively.
import sys
print(sys.getrecursionlimit()) # typically 1000
| Component | Role |
|---|---|
| Base case | Stops recursion; solves the smallest instance directly |
| Recursive case | Calls the function with a smaller input |
| Progress | Each call must move towards the base case |
| Call stack | Stores each pending call's frame |
| Algorithm | Base Case | Recurrence |
|---|---|---|
| Factorial | factorial(0) = 1 | n * factorial(n-1) |
| Fibonacci | fib(0)=0, fib(1)=1 | fib(n-1) + fib(n-2) |
| Power | x^0 = 1 | x * x^(n-1) |
| GCD | gcd(a,0) = a | gcd(b, a % b) |
Recursion is a powerful and elegant technique in which a function solves a problem by calling itself on smaller instances. Every recursive function rests on a base case that stops the chain and a recursive case that moves towards it, all tracked by the call stack. The classic algorithms of factorial, Fibonacci, power, sum of digits and GCD demonstrate the pattern clearly, though naive recursion can be inefficient, as the exponential Fibonacci computation shows. Compared with iteration, recursion trades efficiency for clarity and is best applied to problems that are naturally recursive. The final chapter closes the course by studying the idea of efficiency, formalising the complexity analysis that recursion and all other algorithms require.