Recursion Examples: 46 Problems with Answers

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).
Show solution

Answer

24

First step

1.
Step 1: factorial(4) = 4 * factorial(3).

See the full worked solution + why-it-works coaching

SetupKey insightWhy it worksCommon pitfallConnection

Free: full solutions on 3 topics a day. No card.

Every topic, every day: the Family plan

Example 2

hard
What happens if a recursive function has no base case? For example: FUNCTION forever(n): RETURN forever(n+1).

Example 3

medium
Trace `gcd(a,b) = b == 0 ? a : gcd(b, a mod b)`. Compute `gcd(48, 18)`.

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?

Example 6

hard
A recursive `sum_digits(n)`: if `n < 10` return n; else return `n % 10 + sum_digits(n / 10)` (integer divide). Compute `sum_digits(2487)`.

Example 7

hard
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 n(n+1)2 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).

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?

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)`?

Example 5

easy
What error occurs if a recursive function never reaches its base case?

Example 6

easy
`countdown(0)` prints nothing; `countdown(n)` prints n then calls `countdown(n-1)`. What does `countdown(3)` print?

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)`?

Example 12

medium
`factorial(4)` with the standard definition. What is the result?

Example 13

medium
How many times is `fib` CALLED total to compute `fib(3)` using naive recursion (count all calls including the top)?

Example 14

medium
`power(b, 0) = 1`, `power(b, e) = b * power(b, e-1)`. What is `power(2, 4)`?

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?

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?

Example 21

medium
`sum(n) = n + sum(n-1)`, `sum(0) = 0`. What is `sum(4)`?

Example 22

medium
`countup(n)`: if n > 3 return; else print n then countup(n+1). Starting `countup(1)`, what prints?

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)`?

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)`.

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`?

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)`?

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?

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)`?

Example 38

challenge
Ackermann: A(0,n)=n+1, A(m,0)=A(m−1,1), A(m,n)=A(m−1,A(m,n−1)). Compute A(2,2).

What to focus on

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.

Read the full lesson on Recursion

Common mistakes to watch for

Background knowledge

These ideas may be useful before you work through the harder examples.

functioniteration