Recursion Basics
Recursion is when a function calls itself to solve a smaller version of the same problem. It is one of the most elegant and powerful ideas in computer science — and one that trips up nearly every beginner the first time they encounter it.
The Mental Model: Thinking Recursively
Every recursive problem has the same shape. Ask yourself: 1. What is the simplest version of this problem? (Base case) 2. How can I express the current problem in terms of a smaller version? (Recursive case) That is all recursion is. If you can answer those two questions, you can write the code.
Anatomy of a Recursive Function
Base case: The condition where recursion stops. Without it, the function calls itself forever.
Recursive case: The part where the function calls itself with a smaller/simpler input.
Progress toward base case: Each recursive call must get closer to the base case.
def countdown(n):
# Base case: stop when we reach 0
if n <= 0:
print("Go!")
return
# Recursive case: print n, then count down from n-1
print(n)
countdown(n - 1) # smaller input (n-1 < n)
countdown(5)5 4 3 2 1 Go!
Notice: every call passes n - 1, which is always smaller than n. So the
base case (n <= 0) is guaranteed to be reached eventually. This is called
making progress.
The Call Stack — What Actually Happens
When a function calls itself, the computer does not replace the current call — it pauses it and starts a new one. Each paused call is a stack frame sitting in memory, waiting for the call below it to finish.
# Trace of countdown(3): # # countdown(3) called # prints 3 # calls countdown(2) ← paused here # prints 2 # calls countdown(1) ← paused here # prints 1 # calls countdown(0) ← paused here # prints "Go!" # returns ← stack unwinds from here # countdown(1) resumes and returns # countdown(2) resumes and returns # countdown(3) resumes and returns # # Stack at deepest point: # | countdown(0) | ← top (currently running) # | countdown(1) | # | countdown(2) | # | countdown(3) | ← bottom (waiting)
Factorial — The Classic Example
Factorial of n (written n!) is defined as n × (n-1) × (n-2) × ... × 1. And 0! = 1 by convention. Mathematically: n! = n × (n-1)! This is already recursive in its definition — which means writing a recursive function is almost mechanical.
def factorial(n):
# Base case
if n == 0:
return 1
# Recursive case: n! = n × (n-1)!
return n * factorial(n - 1)
# Trace of factorial(4):
# factorial(4)
# = 4 * factorial(3)
# = 4 * (3 * factorial(2))
# = 4 * (3 * (2 * factorial(1)))
# = 4 * (3 * (2 * (1 * factorial(0))))
# = 4 * (3 * (2 * (1 * 1)))
# = 4 * (3 * (2 * 1))
# = 4 * (3 * 2)
# = 4 * 6
# = 24factorial(0) = 1 factorial(1) = 1 factorial(4) = 24 factorial(5) = 120
function factorial(n) {
// Base case
if (n === 0) return 1;
// Recursive case
return n * factorial(n - 1);
}
console.log(factorial(5)); // 120Fibonacci — Multiple Recursive Calls
Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21 ... Each number is the sum of the two before it. Definition: fib(n) = fib(n-1) + fib(n-2), with fib(0) = 0, fib(1) = 1. This has two base cases and two recursive calls.
def fib(n):
# Base cases — two of them
if n == 0:
return 0
if n == 1:
return 1
# Recursive case: sum of previous two
return fib(n - 1) + fib(n - 2)
for i in range(8):
print(f"fib({i}) = {fib(i)}")fib(0) = 0 fib(1) = 1 fib(2) = 1 fib(3) = 2 fib(4) = 3 fib(5) = 5 fib(6) = 8 fib(7) = 13
Recursion vs Iteration
Anything you can do recursively, you can also do iteratively (with explicit loops and a stack if needed). So when should you choose recursion?
Use Recursion When... | Use Iteration When... |
|---|---|
The problem is naturally self-similar (trees, graphs, divide-and-conquer) | Performance is critical and call-stack overhead matters |
The recursive definition is clearer than a loop | The input is very deep (risk of stack overflow) |
You are traversing recursive data structures (trees, nested lists) | The language lacks tail call optimization |
Divide and conquer is the algorithmic strategy | You need fine-grained control over memory usage |
The Trust Principle — Recursive Leap of Faith
The hardest part of recursion for beginners is mentally tracing every call. Stop doing that. Instead, use the leap of faith: Assume your function correctly solves the problem for smaller inputs. Then write the code that solves the current input using that assumption.
# Sum of all numbers from 1 to n
def sum_to(n):
# Base case
if n == 1:
return 1
# Recursive case:
# TRUST that sum_to(n-1) correctly returns 1+2+...+(n-1)
# Then sum_to(n) = that result + n
return sum_to(n - 1) + n
# Verification:
# sum_to(5) = sum_to(4) + 5 = 10 + 5 = 15
# sum_to(4) = sum_to(3) + 4 = 6 + 4 = 10
# sum_to(3) = sum_to(2) + 3 = 3 + 3 = 6
# sum_to(2) = sum_to(1) + 2 = 1 + 2 = 3
# sum_to(1) = 1 (base case)Power Function
def power(base, exp):
"""Compute base^exp recursively."""
# Base case
if exp == 0:
return 1
# Recursive case: base^exp = base * base^(exp-1)
return base * power(base, exp - 1)
# Can we do better? Yes — divide exp in half each time!
def fast_power(base, exp):
"""O(log exp) instead of O(exp)."""
if exp == 0:
return 1
if exp % 2 == 0:
# base^exp = (base^(exp/2))^2
half = fast_power(base, exp // 2)
return half * half
else:
# base^exp = base * base^(exp-1)
return base * fast_power(base, exp - 1)
print(fast_power(2, 10)) # 1024Binary Search — Recursion on Arrays
def binary_search(arr, target, low, high):
# Base case: search space exhausted
if low > high:
return -1
mid = (low + high) // 2
if arr[mid] == target:
return mid # found!
elif arr[mid] < target:
return binary_search(arr, target, mid+1, high) # search right half
else:
return binary_search(arr, target, low, mid-1) # search left half
arr = [1, 3, 5, 7, 9, 11, 13]
print(binary_search(arr, 7, 0, len(arr)-1)) # 3
print(binary_search(arr, 6, 0, len(arr)-1)) # -1Reverse a String Recursively
def reverse(s):
# Base case: empty string or single character
if len(s) <= 1:
return s
# Recursive case: reverse everything after the first char,
# then put the first char at the end
return reverse(s[1:]) + s[0]
print(reverse("hello")) # "olleh"
# Trace:
# reverse("hello")
# = reverse("ello") + "h"
# = (reverse("llo") + "e") + "h"
# = ((reverse("lo") + "l") + "e") + "h"
# = (((reverse("o") + "l") + "l") + "e") + "h"
# = ((("o" + "l") + "l") + "e") + "h"
# = "olleh"Common Mistakes Beginners Make
Complexity of Recursive Functions
The time complexity of a recursive function depends on: 1. How many recursive calls are made at each level 2. How fast the input shrinks with each call 3. How much work is done outside the recursive calls
Pattern | Calls per level | Input reduction | Time Complexity |
|---|---|---|---|
countdown(n) | 1 | n-1 | O(n) |
factorial(n) | 1 | n-1 | O(n) |
binary_search(n) | 1 | n/2 | O(log n) |
fib(n) naive | 2 | n-1 and n-2 | O(2ⁿ) |
merge_sort(n) | 2 | n/2 | O(n log n) |
Practice Problems
Sum of digits: Write a recursive function that sums the digits of a number (e.g., 123 → 6)
Count occurrences: Count how many times a value appears in a nested list recursively
Palindrome check: Check if a string is a palindrome recursively (compare first and last chars)
GCD: Implement the Euclidean algorithm for GCD recursively
Tower of Hanoi: Classic puzzle — move n disks from peg A to peg C using peg B as a helper
# Tower of Hanoi — elegant recursive solution
def hanoi(n, source, auxiliary, destination):
"""Move n disks from source to destination using auxiliary."""
if n == 1:
print(f"Move disk 1 from {source} to {destination}")
return
# Move n-1 disks from source to auxiliary (using destination as helper)
hanoi(n - 1, source, destination, auxiliary)
# Move the largest disk from source to destination
print(f"Move disk {n} from {source} to {destination}")
# Move n-1 disks from auxiliary to destination (using source as helper)
hanoi(n - 1, auxiliary, source, destination)
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