Basic Recursion Questions
Eight warm-up problems. Every one of them is a straight application of the three-question recipe from the Thinking Recursively page: base case, recursive case, combine. The goal isn’t to memorize them — it’s to build muscle memory so the pattern feels natural.
Before reading each solution, try to answer the three questions yourself. “What’s the base case? What’s the recursive call? How do I combine?” If you can answer all three, you can write the code.
1. Sum of Natural Numbers (1 to n)
Base case: sum(1) = 1. Recursive case: sum(n) = n + sum(n-1). Combine: add.
Time: O(n) — one call per level. Space: O(n) — call stack depth.
2. Factorial
Base case: factorial(0) = 1. Recursive case: factorial(n) = n · factorial(n-1).
Factorial grows fast. 21! overflows a 64-bit integer. Use long long / long and watch the range — n <= 20 is the safe limit.
Time: O(n). Space: O(n).
3. Decimal to Binary
Print the binary digits of num in the correct (most-significant-first) order. The trick is head recursion — recurse first, then print, so digits emerge during the unwinding phase.
Base case: num == 0 — nothing to print. Recursive case: recurse on num / 2, then print num % 2.
Swap the order of the two statements and you’ll print the binary digits backward. That asymmetry is the entire personality of head vs tail recursion.
Time: O(log n) — we halve at each step. Space: O(log n).
4. Modulo via subtraction
Compute num mod den without using %. Just keep subtracting den until num < den.
Time: O(num / den) — proportional to how many subtractions we need. Space: O(num / den). Don’t use this for big numbers — there’s a much faster O(1) operator built in.
5. String Length (without strlen / len)
Base case: empty string → length 0. Recursive case: length of s = 1 + length of s[1:].
We pass an index instead of slicing — slicing a string allocates a new copy at every call, making the function O(n²) in time. Index-passing keeps it at O(n).
Time: O(n). Space: O(n).
6. Reverse a String
Print characters during the unwinding phase — head recursion again.
If you want the result as a new string instead of just printing it, build it during unwinding:
def reversed_str(s, i=0):
if i >= len(s):
return ""
return reversed_str(s, i + 1) + s[i]Time: O(n). Space: O(n).
7. Check Palindrome
Two pointers, but with recursion: compare the ends, recurse on the middle.
Base case: pointers cross → it’s a palindrome. Mismatch: not a palindrome. Otherwise recurse on the inner substring.
Time: O(n) — we check each character once. Space: O(n) for the stack.
8. Count Vowels in a String
Time: O(n). Space: O(n).
9. Sum the Nodes of a Linked List
The recursive case is the prettiest: sum(head) = head.data + sum(head.next). The base case is the null pointer.
Time: O(n). Space: O(n).
Quick visual
sum_to(5) is a single-branch recursion — one call per level, base case at the bottom, results bubble up:
Extra practice (try before peeking)
A few one-liners to keep the muscles warm.
Print numbers from 1 to n.
Print numbers from n down to 1.
GCD via Euclid’s algorithm — gcd(a, b) = gcd(b, a mod b), base case gcd(a, 0) = a.
Once these feel automatic, you’re ready for the harder stuff — Memoization is next.