Writing Recursive Functions

Writing recursive functions stops feeling mysterious once you follow a simple 3-step recipe:

1. Define what the function returns for a given input.
2. Find the base case — what is the simplest input, and what does the function return for it?
3. Find the recursive case — how do you reduce the problem to a smaller version, and how do you combine the result with the work at the current level?

Apply these three steps to any recursive problem and you will be able to write it.

The 3 Steps in Detail

Step 1: Define what the function returns.

Be specific. Write it as a comment before any code. "This function takes an array and returns the sum of all its elements." Or: "This function takes a string and returns it reversed."

Step 2: Find the base case.

What is the smallest valid input? For an array: empty array. For a number: 0 or 1. For a string: empty string or single character. What should the function return for that input?

Step 3: Find the recursive case.

How do you make the problem smaller? Process the first element and recurse on the rest. Then combine the recursive result with your current-level work.

Problem 1: Sum of an Array

Step 1: sumArray(arr) returns the sum of all elements.

Step 2: Base case: empty array → return 0.

Step 3: Recursive case: first element + sum of the rest.

function sumArray(arr):
    if arr is empty:                         // base case
        return 0
    return arr[0] + sumArray(arr[1..end])    // recursive case

Trace for sumArray([3, 1, 4, 2]):

sumArray([3, 1, 4, 2])
  = 3 + sumArray([1, 4, 2])
  = 3 + (1 + sumArray([4, 2]))
  = 3 + (1 + (4 + sumArray([2])))
  = 3 + (1 + (4 + (2 + sumArray([]))))
  = 3 + (1 + (4 + (2 + 0)))     <- base case
  = 10

Problem 2: Reverse a String

Step 1: reverseStr(s) returns the characters of s in reverse order.

Step 2: Base case: empty string or single character → return s.

Step 3: Recursive case: reverse of the rest, then append the first character at the end.

function reverseStr(s):
    if length(s) <= 1:                          // base case
        return s
    return reverseStr(s[1..end]) + s[0]         // recursive case

Trace for reverseStr("hello"):

reverseStr("hello")
  = reverseStr("ello") + "h"
  = (reverseStr("llo") + "e") + "h"
  = ((reverseStr("lo") + "l") + "e") + "h"
  = (((reverseStr("o") + "l") + "l") + "e") + "h"
  = ((("o" + "l") + "l") + "e") + "h"   <- base case
  = "olleh"

Problem 3: Fibonacci

Step 1: fib(n) returns the nth Fibonacci number.

Step 2: Base cases: fib(0) = 0, fib(1) = 1. (Two base cases — you need both.)

Step 3: Recursive case: fib(n) = fib(n-1) + fib(n-2). This splits into TWO smaller problems.

function fib(n):
    if n == 0: return 0        // base case 1
    if n == 1: return 1        // base case 2
    return fib(n-1) + fib(n-2)

Trace for fib(5):

fib(5) = fib(4) + fib(3)
       = (fib(3) + fib(2)) + (fib(2) + fib(1))
       = 3 + 2 = 5

Warning: This naive version is very slow for large n — it recalculates the same values many times. For example, fib(3) gets computed twice above. We will fix this with memoization in a later lesson.

Problem 4: Power

Step 1: power(base, exp) returns base raised to the power exp.

Step 2: Base case: exp == 0 → return 1 (anything to the power of 0 is 1).

Step 3: Recursive case — simple version:

function power(base, exp):
    if exp == 0: return 1
    return base * power(base, exp - 1)
​
power(2, 4) = 2 * power(2, 3)
            = 2 * 2 * power(2, 2)
            = 2 * 2 * 2 * power(2, 1)
            = 2 * 2 * 2 * 2 * power(2, 0)
            = 2 * 2 * 2 * 2 * 1 = 16

Common Patterns

Most recursive problems fall into one of three shapes:

Pattern 1 — Process one, recurse on the rest:

f([a, b, c, d]) = do_something(a) + f([b, c, d])

Examples: sumArray, reverseStr, factorial.

Pattern 2 — Split in half, recurse on both halves:

f([a, b, c, d]) = combine(f([a, b]), f([c, d]))

Examples: merge sort, binary search.

Pattern 3 — Make two or more recursive calls:

f(n) = f(n-1) + f(n-2)

Examples: fibonacci, counting paths in a grid. Warning: often slow without memoization.

Applying the Recipe: Find the Maximum

Step 1: maxArr(arr) returns the largest element.

Step 2: Base case: array has one element → return it.

Step 3: Max of the array = larger of (first element, max of the rest).

function maxArr(arr):
    if length(arr) == 1:              // base case
        return arr[0]
    restMax = maxArr(arr[1..end])
    if arr[0] > restMax:
        return arr[0]
    else:
        return restMax

Trace for maxArr([3, 7, 2, 9]):

maxArr([3,7,2,9]) -> compare 3 with maxArr([7,2,9])
maxArr([7,2,9])   -> compare 7 with maxArr([2,9])
maxArr([2,9])     -> compare 2 with maxArr([9])
maxArr([9])       -> base case: return 9
  max(2, 9) = 9
  max(7, 9) = 9
  max(3, 9) = 9
Result: 9