Start with the recap, study the fully worked examples, then use the practice problems to
check your understanding of Recursion.
This page combines explanation, solved examples, and follow-up practice so you can move
from recognition to confident problem-solving in CS Thinking.
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.
Russian dolls—open one, find a smaller one inside. Repeat until you reach the smallest.
Read the first worked example with the solution open so the structure is clear.
Try the practice problems before revealing each solution.
Use the related concepts and background knowledge badges if you feel stuck.
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.
Sense of Study hint:When writing a recursive function, first define the base case—the simplest version of the problem that can be answered directly. Then define the recursive case—how to reduce the current problem to a smaller version. Always verify that each recursive call moves closer to the base case.
Common Mistakes to Watch For
Before you work through the examples, skim the mistake guide so you know which shortcuts and
sign errors to avoid.
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)
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 these problems on your own first, 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) = 6
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=0
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) = 24
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)=1
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)=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)=15 total moves
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)=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) = 120
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)=1
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)`?