Worked examples of Recursion to try before you open each solution, then practice
problems with answers.
Worked Examples
Example 1
hard
Trace the recursive function: FUNCTION factorial(n): IF n <= 1 THEN RETURN 1. ELSE RETURN n * factorial(n-1). Call factorial(4).Call stack while computing factorial(4); base case at factorial(1)
Show solution
Answer
24
First step
1.
Step 1: factorial(4) = 4 * factorial(3).
See the full worked solution + why-it-works coaching
Setup·Key insight·Why it works·Common pitfall·Connection
What happens if a recursive function has no base case? For example: FUNCTION forever(n): RETURN forever(n+1).Without a base case, calls stack up forever until stack overflow
Example 3
medium
Trace `gcd(a,b) = b == 0 ? a : gcd(b, a mod b)`. Compute `gcd(48, 18)`.Call stack for gcd(48,18)=6 via Euclidean algorithm
Example 4
medium
`mult(a,0) = 0`, `mult(a,b) = a + mult(a, b-1)`. Compute `mult(4, 5)` and explain why this is multiplication by repeated addition.
Example 5
medium
What is the maximum depth of the call stack when computing `factorial(100)` with the standard `factorial(n) = n*factorial(n-1)` definition?
Why is `T(n) = 2T(n/2) + n` (merge sort) more efficient than `T(n) = T(n-1) + n` (insertion-style)?
Example 8
challenge
Prove (informally) that the recursive definition `sum(n) = n + sum(n-1)`, `sum(0) = 0` returns 2n(n+1) for all n≥0.
Practice Problems
Try each one, then open the solution to compare your method.
Example 1
hard
Write a recursive function `sum(n)` that returns the sum 1 + 2 + ... + n. Trace sum(5).Call stack for sum(5); base case at sum(1)
Example 2
hard
Trace `countdown(3)` for `FUNCTION countdown(n): OUTPUT n. IF n > 0 THEN countdown(n-1)`. What is printed, and what is the base case?Call stack for countdown(3); prints top-to-bottom then unwinds
Example 3
easy
Every recursive function needs two parts. One is the recursive case. What is the other?
Example 4
easy
`factorial(0) = 1`, `factorial(n) = n * factorial(n-1)`. What is `factorial(3)`?Call stack for factorial(3)
Example 5
easy
What error occurs if a recursive function never reaches its base case?Recursion without a base case causes a stack overflow
Example 6
easy
`countdown(0)` prints nothing; `countdown(n)` prints n then calls `countdown(n-1)`. What does `countdown(3)` print?countdown(3) prints 3, 2, 1 then stops at base case n
Example 7
easy
In `sum(n) = n + sum(n-1)` with `sum(0) = 0`, which call returns without recursing?
Example 8
easy
Recursion is often compared to what nested physical object?
Example 9
easy
For recursion to terminate, the recursive case must do what to the input?
Example 10
easy
`factorial(1)` with base `factorial(0)=1` and `factorial(n)=n*factorial(n-1)`. What does it return?
Example 11
medium
Fibonacci: `fib(0)=0`, `fib(1)=1`, `fib(n)=fib(n-1)+fib(n-2)`. What is `fib(5)`?Recursive call tree for fib(5) = 5; base cases fib(0) and fib(1) shown in green
Example 12
medium
`factorial(4)` with the standard definition. What is the result?Call stack for factorial(4)
Example 13
medium
How many times is `fib` CALLED total to compute `fib(3)` using naive recursion (count all calls including the top)?Call tree for fib(3): 5 nodes total (1 + 2 + 1 + 1)
Example 14
medium
`power(b, 0) = 1`, `power(b, e) = b * power(b, e-1)`. What is `power(2, 4)`?Call stack for power(2,4) = 16; base case at power(2,0)
Example 15
medium
A recursive function on a list of length n removes one element per call until empty. How deep does the recursion go?
Example 16
medium
Why might `fib(50)` via naive recursion be impractically slow?
Example 17
medium
Recursion vs iteration: a loop and a recursive function both sum 1..n. Which uses extra call-stack memory proportional to n?
Example 18
challenge
`mystery(n)`: if n == 1 return 1; if n even return mystery(n/2); else return mystery(3n+1). Trace `mystery(6)` until it returns. What does it return?Collatz-style call stack for mystery(6); path reaches base case mystery(1)
Example 19
challenge
A recursive `reverse(s)` returns `reverse(s[1:]) + s[0]`. What is the base case it MUST have to avoid infinite recursion?
Example 20
challenge
Tower of Hanoi with n disks needs `T(n) = 2*T(n-1) + 1` moves, `T(1) = 1`. How many moves for 4 disks?Recursion tree for T(4) = 2T(3)+1; T(4)
Example 21
medium
`sum(n) = n + sum(n-1)`, `sum(0) = 0`. What is `sum(4)`?Call stack for sum(4) = 10; base case at sum(0)
Example 22
medium
`countup(n)`: if n > 3 return; else print n then countup(n+1). Starting `countup(1)`, what prints?Call stack for countup(1); base case is n>3 (countup(4) stops immediately)
Example 23
easy
Name the two required parts of any correct recursive function.
Example 24
easy
Given `factorial(n) = n * factorial(n-1)` with `factorial(0) = 1`, what is `factorial(5)`?Call stack for factorial(5)
Example 25
easy
`sum(0) = 0`, `sum(n) = n + sum(n-1)`. What is `sum(6)`?
Example 26
easy
`power(b,0)=1`, `power(b,e)=b*power(b,e-1)`. Compute `power(3,3)`.Call stack for power(3,3) = 27; base case power(3,0)
Example 27
easy
`length([]) = 0`, `length([h, ...t]) = 1 + length(t)`. What is `length([a,b,c,d])`?
Example 28
medium
`fib(0)=0, fib(1)=1, fib(n)=fib(n-1)+fib(n-2)`. What is `fib(7)`?
Example 29
medium
A recursive `reverse([h, ...t]) = reverse(t) + [h]`, `reverse([]) = []`. What is `reverse([1,2,3])`?
Example 30
medium
A recursive `count_down(n)` prints n then calls `count_down(n-2)` with base `n <= 0` (no print). What does `count_down(7)` print?
Example 31
medium
How many recursive calls (excluding the original) does `factorial(6)` make using `factorial(n) = n*factorial(n-1)`, base `factorial(0)=1`?factorial(6) generates 6 recursive calls (not counting the original)
Example 32
medium
`is_even(0) = true`, `is_even(n) = is_odd(n-1)`, `is_odd(0)=false`, `is_odd(n)=is_even(n-1)`. What does `is_even(5)` return?
Example 33
medium
What is wrong with this base case: `FUNCTION f(n): IF n == 0 RETURN 1 ELSE RETURN n * f(n+1)`?f(n+1) moves away from base case n=0; stack overflows
Example 34
hard
Tower of Hanoi with 6 disks needs `T(n) = 2T(n-1) + 1` moves with `T(1)=1`. How many moves total?
Example 35
hard
Naive `fib(6)` using `fib(n)=fib(n-1)+fib(n-2)`, `fib(0)=0`, `fib(1)=1`, counts each invocation as a call. How many total calls are made?Partial call tree for fib(6); naive recursion makes 25 total calls due to repeated subproblems
Example 36
hard
Recursive `is_palindrome(s)`: if `len(s) <= 1` true; else `s[0]==s[-1] and is_palindrome(s[1:-1])`. Is 'racecar' a palindrome by this definition?
Example 37
hard
Recursive `count_paths(m, n)`: number of monotonic lattice paths from (0,0) to (m,n). `count_paths(0,n)=count_paths(m,0)=1`, else `count_paths(m,n)=count_paths(m-1,n)+count_paths(m,n-1)`. What is `count_paths(2,3)`?
Core idea:Every recursion needs a base case (when to stop) and a recursive case (how to continue).
Common stuck point:Without a base case, recursion never ends—the program crashes with a stack overflow error.
Ask yourself:Does a function call itself on a smaller input, with a base case that stops the calls?
Concept recap
A technique where a function calls itself to solve progressively smaller instances of the same problem. Every recursive solution has two parts: a base case that stops the recursion, and a recursive case that breaks the problem into a smaller version of itself.
Looking up a word can be recursive: if the definition uses a word you do not know, you look that word up first, then come back to where you were. You stop at a definition made only of words you know, the base case. A dictionary that defines 'big' as 'large' and 'large' as 'big' is infinite recursion: the lookups never end.