Classic Recursion Problems

Jr Codex DSA Notes

Level: Intermediate Prerequisites: Chapter 2 Time to complete: ~25 minutes

Factorial (Revisited)
Sum of Digits
Power Function
Fast Exponentiation — A Cleverer Recursive Case
Reversing a String Recursively
Reversing a List Recursively
Summary & Next Steps

1. Factorial (Revisited)

Already covered in Chapter 1 — included here for completeness as the canonical first example:

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)
    # Time: O(n), Space: O(n)

2. Sum of Digits

def sum_of_digits(n):
    if n < 10:                          # base case: single digit
        return n
    return n % 10 + sum_of_digits(n // 10)
    # n % 10  → last digit
    # n // 10 → the rest of the number, one digit shorter
 
print(sum_of_digits(1234))   # 1 + 2 + 3 + 4 = 10

Each call strips one digit off the number, so the recursion depth equals the number of digits — O(log₁₀ n) calls, since the number of digits in n is roughly log₁₀ n.

3. Power Function

def power(base, exponent):
    if exponent == 0:                   # base case: anything^0 = 1
        return 1
    return base * power(base, exponent - 1)
    # Time: O(exponent), Space: O(exponent)

This works, but it does exponent multiplications one at a time — the next section shows a faster recursive structure for the same problem.

4. Fast Exponentiation — A Cleverer Recursive Case

Instead of reducing the exponent by 1 each call, halve it — this changes the recursion from O(n) calls to O(log n) calls, the same halving idea from Module 1 Chapter 2's Big O intuition:

def power_fast(base, exponent):
    if exponent == 0:
        return 1
    half = power_fast(base, exponent // 2)
    if exponent % 2 == 0:
        return half * half              # even exponent: base^n = (base^(n/2))²
    else:
        return half * half * base       # odd exponent: one extra factor of base
 
print(power_fast(2, 10))    # 1024, computed in ~4 recursive calls instead of 10

Same problem, same base case shape — but choosing how to shrink the problem (halving instead of decrementing) is the difference between O(n) and O(log n). This is a preview of a recurring theme: the recursive case you choose determines the complexity, not just whether recursion is used at all.

5. Reversing a String Recursively

def reverse_string(s):
    if len(s) <= 1:                     # base case: empty or single character
        return s
    return reverse_string(s[1:]) + s[0]
    # reverse everything after the first character, then append the first character
 
print(reverse_string("hello"))   # "olleh"

A hidden cost, as flagged in Module 1 Chapter 6: s[1:] creates a new string at every call, and string concatenation (+) creates another new string. This makes the true complexity O(n²), not O(n) — the same slicing trap you already learned to spot.

6. Reversing a List Recursively

The index-based fix from Module 1 Chapter 6 applies here too — pass indices instead of slicing, and swap in place:

def reverse_list(items, left=0, right=None):
    if right is None:
        right = len(items) - 1
    if left >= right:                   # base case: pointers have met or crossed
        return items
    items[left], items[right] = items[right], items[left]
    return reverse_list(items, left + 1, right - 1)
    # Time: O(n) — n/2 swaps, no copying
    # Space: O(n) — n/2 stack frames (an iterative two-pointer version, covered
    #                in Module 2, would do this in O(1) space instead)

7. Summary & Next Steps

Key Takeaways

The shape of the recursive case matters as much as having one — halving the problem (fast exponentiation) is O(log n), decrementing by one (naive power) is O(n).
Slicing (s[1:], items[1:]) inside recursive string/list problems silently turns O(n) into O(n²) — pass indices instead when you need to avoid this.
Recursive solutions to problems that array-based two-pointer techniques (Module 2) also solve will usually cost more stack space — recursion isn't always the most space-efficient choice, even when it's the clearest one to write.

Concept Check

Why is power_fast O(log n) while power is O(n), given that both are recursive?
What's wrong with reverse_string's complexity, and how would you rewrite it to avoid the problem?
When would you prefer the iterative two-pointer approach to reverse_list over the recursive one?

Next Chapter

→ Chapter 4: Backtracking Fundamentals

Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index