Mojo Recursion
Recursion is a technique where a function solves a problem by calling itself on a smaller version of the same problem. It breaks a complex task into identical sub-tasks until the task becomes trivially simple. Recursion is the natural way to express tree traversal, divide-and-conquer algorithms, and mathematical definitions that reference themselves.
The Russian Nesting Doll Analogy
Open a doll → find another doll inside → open it → find another...
Until you reach the smallest doll that has nothing inside (base case).
count_dolls(doll):
if doll is empty:
return 0 ← base case (stop here)
else:
return 1 + count_dolls(inside_doll) ← recursive case
Two Required Parts of Every Recursive Function
Part 1: Base case
The simplest input where the answer is known directly.
Without a base case, the function calls itself forever → stack overflow.
Part 2: Recursive case
Reduce the problem toward the base case and call self on the smaller input.
Missing base case: factorial(0) keeps calling itself → crash
Missing reduction: factorial(n) calls factorial(n) → infinite loop
Classic Example: Factorial
fn factorial(n: Int) -> Int:
if n == 0: # base case: 0! = 1 by definition
return 1
return n * factorial(n - 1) # recursive case
fn main():
print(factorial(0)) # 1
print(factorial(5)) # 120
print(factorial(10)) # 3628800
Call stack for factorial(4):
factorial(4)
→ 4 × factorial(3)
→ 3 × factorial(2)
→ 2 × factorial(1)
→ 1 × factorial(0)
→ 1 ← base case reached
← 1 × 1 = 1
← 2 × 1 = 2
← 3 × 2 = 6
← 4 × 6 = 24
Result: 24
Fibonacci Sequence
The Fibonacci sequence defines each number as the sum of the two before it: 0, 1, 1, 2, 3, 5, 8, 13, 21 …
fn fib(n: Int) -> Int:
if n == 0: return 0 # base case 1
if n == 1: return 1 # base case 2
return fib(n - 1) + fib(n - 2) # recursive case
fn main():
for i in range(8):
print(fib(i), end=" ") # 0 1 1 2 3 5 8 13
print("")
Call tree for fib(4):
fib(4)
/ \
fib(3) fib(2)
/ \ / \
fib(2) fib(1) fib(1) fib(0)
/ \
fib(1) fib(0)
Notice: fib(2) and fib(1) are computed multiple times.
This is O(2^n) — exponential time. Memoization (below) fixes this.
Memoization: Caching Recursive Results
fn fib_memo(n: Int, cache: inout Dict[Int, Int]) -> Int:
if n in cache:
return cache[n] # return cached result immediately
if n == 0: return 0
if n == 1: return 1
var result = fib_memo(n - 1, cache) + fib_memo(n - 2, cache)
cache[n] = result # store before returning
return result
fn main():
var cache = Dict[Int, Int]()
print(fib_memo(10, cache)) # 55
print(fib_memo(40, cache)) # 102334155 (fast with cache)
Memoized call tree for fib(4):
fib(4) → fib(3) + fib(2)
fib(3) → fib(2) + fib(1)
fib(2) → fib(1) + fib(0) = 1
cache[2] = 1
fib(3) = 1 + 1 = 2
cache[3] = 2
fib(2) already in cache → 1 (no recomputation)
fib(4) = 2 + 1 = 3
cache[4] = 3
Each value computed exactly once → O(n) time.
Sum of a List (Recursive)
fn list_sum(data: List[Int], index: Int) -> Int:
if index == len(data): # base case: past the end
return 0
return data[index] + list_sum(data, index + 1)
fn main():
var nums = List[Int](1, 2, 3, 4, 5)
print(list_sum(nums, 0)) # 15
Recursive sum trace:
list_sum([1,2,3,4,5], 0)
= 1 + list_sum([1,2,3,4,5], 1)
= 2 + list_sum([1,2,3,4,5], 2)
= 3 + list_sum([1,2,3,4,5], 3)
= 4 + list_sum([1,2,3,4,5], 4)
= 5 + list_sum([1,2,3,4,5], 5)
= 0 ← base case
= 5 + 0 = 5
= 4 + 5 = 9
= 3 + 9 = 12
= 2 + 12 = 14... wait → 1+2+3+4+5=15 ✓
Binary Search (Recursive)
fn binary_search(data: List[Int], target: Int, lo: Int, hi: Int) -> Int:
if lo > hi:
return -1 # base case: not found
var mid = (lo + hi) // 2
if data[mid] == target:
return mid # base case: found
elif data[mid] < target:
return binary_search(data, target, mid + 1, hi)
else:
return binary_search(data, target, lo, mid - 1)
fn main():
var sorted = List[Int](2, 5, 8, 12, 16, 23, 38, 56, 72, 91)
print(binary_search(sorted, 23, 0, len(sorted)-1)) # 5
print(binary_search(sorted, 50, 0, len(sorted)-1)) # -1
Binary search on [2,5,8,12,16,23,38,56,72,91], target=23: lo=0, hi=9, mid=4 → data[4]=16 < 23 → search right lo=5, hi=9, mid=7 → data[7]=56 > 23 → search left lo=5, hi=6, mid=5 → data[5]=23 == 23 → found at index 5 ✓ Each step cuts the search space in half → O(log n).
Recursion vs Iteration
Recursive: Iterative:
fn sum_r(n: Int) -> Int: fn sum_i(n: Int) -> Int:
if n == 0: return 0 var total = 0
return n + sum_r(n-1) for i in range(1, n+1):
total += i
return total
Recursion pros: Iteration pros:
Mirrors the problem's Faster (no call stack overhead)
mathematical definition No stack overflow risk
Short, readable code Better for simple loops
Use recursion when: Use iteration when:
Tree/graph traversal Summing, searching lists
Divide and conquer Repetitive fixed patterns
Problem is naturally self- Performance is critical
similar (parsing, fractals)
Stack Overflow Warning
fn infinite(n: Int) -> Int:
return infinite(n + 1) # no base case → stack overflow!
Each function call uses stack memory.
Deep recursion (>10,000 levels typically) exhausts the call stack.
For very deep recursion, convert to an iterative loop
or use tail-call optimization if available.
Key Takeaways
Every recursive function needs a base case that returns a direct answer and a recursive case that moves toward the base case. The call stack tracks each pending call — deep recursion risks stack overflow. Memoize results in a dictionary when the same sub-problem is solved repeatedly (e.g., Fibonacci). Binary search and divide-and-conquer algorithms express cleanly as recursion. Prefer iteration for simple linear problems where a loop is equally readable. Use recursion when the problem structure is self-similar — trees, graphs, parsers, and mathematical sequences.