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.
Showing a random 20 of 50 problems.
Example 1
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 2
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 3
easy
Recursion is often compared to what nested physical object?
Example 4
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 5
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 6
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 7
easy
Fill in the blank: a recursive call must always move the input ______ the base case.
Example 8
easy
Given `factorial(n) = n * factorial(n-1)` with `factorial(0) = 1`, what is `factorial(5)`?Call stack for factorial(5) = 120
Example 9
hard
Tower of Hanoi with 6 disks needs `T(n) = 2T(n-1) + 1` moves with `T(1)=1`. How many moves total?
Example 10
hard
Why is `T(n) = 2T(n/2) + n` (merge sort) more efficient than `T(n) = T(n-1) + n` (insertion-style)?
Example 11
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
`factorial(1)` with base `factorial(0)=1` and `factorial(n)=n*factorial(n-1)`. What does it return?
Example 14
easy
`length([]) = 0`, `length([h, ...t]) = 1 + length(t)`. What is `length([a,b,c,d])`?
Example 15
easy
Name the two required parts of any correct recursive function.
Example 16
easy
`sum(0) = 0`, `sum(n) = n + sum(n-1)`. What is `sum(6)`?
Example 17
challenge
Prove (informally) that the recursive definition `sum(n) = n + sum(n-1)`, `sum(0) = 0` returns 2n(n+1) for all n≥0.
Example 18
easy
For recursion to terminate, the recursive case must do what to the input?
Example 19
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 20
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)