Coding Challenges: Recursion and Problem-Solving Patterns

Recursion is a function that calls itself to solve a smaller version of the same problem, until it reaches a simple base case it can answer directly. It is a favorite interview topic precisely because it reveals whether a candidate can reason about a problem in terms of smaller sub-problems rather than just writing loops.

The Two Essential Parts of Every Recursive Function

Forgetting the base case is the single most common recursion bug — without one, the function calls itself forever, eventually crashing with a RecursionError once Python's call stack limit is reached.

Classic Example: Factorial

def factorial(n):
    if n == 0 or n == 1:    # base case
        return 1
    return n * factorial(n - 1)   # recursive case

print(factorial(5))   # 5 * 4 * 3 * 2 * 1 = 120

Tracing through factorial(5): it calls factorial(4), which calls factorial(3), and so on down to factorial(1), which returns 1 — then each call multiplies its own n by the result coming back up the chain.

Classic Example: Fibonacci Sequence

def fibonacci(n):
    if n <= 1:              # base case
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)   # recursive case

for i in range(8):
    print(fibonacci(i), end=" ")
# 0 1 1 2 3 5 8 13

This naive recursive Fibonacci is extremely inefficient — it recalculates the same values repeatedly, giving it O(2^n) time complexity. Being asked to optimize it (using memoization or an iterative approach) is an extremely common interview follow-up.

Optimizing Fibonacci With Memoization

def fibonacci_memo(n, cache={}):
    if n in cache:
        return cache[n]
    if n <= 1:
        return n
    cache[n] = fibonacci_memo(n - 1, cache) + fibonacci_memo(n - 2, cache)
    return cache[n]

print(fibonacci_memo(30))   # instant, versus a very noticeable delay without caching

Memoization stores already-computed results so the function never solves the same sub-problem twice — turning O(2^n) into O(n).

Recursion on Lists: Sum of a List

def list_sum(numbers):
    if not numbers:              # base case — empty list
        return 0
    return numbers[0] + list_sum(numbers[1:])   # first item + sum of the rest

print(list_sum([1, 2, 3, 4, 5]))   # 15

Recursion for Searching: Binary Search

def binary_search(sorted_list, target, low=0, high=None):
    if high is None:
        high = len(sorted_list) - 1
    if low > high:
        return -1   # base case — not found

    mid = (low + high) // 2
    if sorted_list[mid] == target:
        return mid
    elif sorted_list[mid] < target:
        return binary_search(sorted_list, target, mid + 1, high)
    else:
        return binary_search(sorted_list, target, low, mid - 1)

numbers = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
print(binary_search(numbers, 23))   # 5 — the index where 23 is found

Binary search repeatedly halves the search range — this is why it runs in O(log n) time, drastically faster than scanning a list one element at a time (O(n)) once the list gets large.

Recursion vs Iteration — When to Choose Which

Interview tip: "Can every recursive function be rewritten as a loop?" — Yes, always, at least in principle. Interviewers ask this specifically to see if you understand that recursion is a stylistic and structural choice, not a fundamentally different category of computation, and that the right tool depends on which version is clearer for the specific problem at hand.