Recursion

A function is recursive when its body calls the function itself. That sounds circular, but it works as long as each call works on a smaller problem, and the smallest problems are answered directly.

The anatomy of a recursive function

Here is the sum of digits from Lab 2, written recursively:

func sumDigits(_ n: Int) -> Int {
    if n < 10 {
        return n                        // base case
    }
    return n % 10 + sumDigits(n / 10)   // recursive case
}

print(sumDigits(2026))   // 10

Every recursive function has the same parts:

1. Base cases: inputs small enough to answer without recursion. A one-digit number is its own digit sum.
2. Recursive cases: break the problem into a smaller version of itself, call the function on it, and use the result. The digit sum of 2026 is 6 plus the digit sum of 202.

The recursive leap of faith

How do you know sumDigits(202) is right while you are still writing sumDigits? CS61A’s answer: trust it. Check the base case, check that the recursive call is on a smaller input, and check that you use its result correctly assuming it is right. If all three hold, induction does the rest.

The same reasoning gives the recursive factorial. n! = n × (n − 1)!, and 0! = 1:

func factorial(_ n: Int) -> Int {
    n == 0 ? 1 : n * factorial(n - 1)
}
print(factorial(5))   // 120

func total(_ n: Int) -> Int {
    n == 0 ? 0 : n + total(n - 1)
}
print(total(4))

Without a base case the calls never stop. Each call takes a little memory on the call stack, and eventually it runs out.

func countdown(_ n: Int) -> Int {
    countdown(n - 1)
}
print(countdown(3))

Order of recursive calls

When a recursive call happens in the middle of a function body, the rest of the body waits until it returns. CS61A’s cascade shows this clearly:

func cascade(_ n: Int) {
    print(n)
    if n >= 10 {
        cascade(n / 10)
        print(n)
    }
}
cascade(123)

func cascade(_ n: Int) {
    print(n)
    if n >= 10 {
        cascade(n / 10)
        print(n)
    }
}
cascade(123)

Each call has its own frame with its own n. While cascade(1) runs, the frames for 12 and 123 are still waiting, each holding its own value.

Mutual recursion

Two functions can call each other. This pair decides whether a non-negative number is even or odd, using only subtraction:

func isEven(_ n: Int) -> Bool {
    n == 0 ? true : isOdd(n - 1)
}
func isOdd(_ n: Int) -> Bool {
    n == 0 ? false : isEven(n - 1)
}
print(isEven(10), isOdd(7), isEven(3))   // true true false

Top-level functions in a Swift file can refer to each other in any order, so isEven can call isOdd before isOdd is written.

func sumDigits(_ n: Int) -> Int {
    if n < 10 {
        return n
    }
    return n % 10 + sumDigits(n / 10)
}
print(sumDigits(2026))

Lab 6: Recursion

Solve these without loops.

Q1: Count the eights

Return the number of times the digit 8 appears in a non-negative integer.

func numEights(_ n: Int) -> Int {
    // your code here
}

func numEights(_ n: Int) -> Int {
    if n == 0 {
        return 0
    }
    let last = n % 10 == 8 ? 1 : 0
    return last + numEights(n / 10)
}

assert(numEights(3) == 0)
assert(numEights(8) == 1)
assert(numEights(88888888) == 8)
assert(numEights(2638) == 1)
assert(numEights(86380) == 2)
assert(numEights(12345) == 0)

Q2: Hailstone

Starting from a positive integer n: if it is even, divide it by 2; otherwise multiply by 3 and add 1. Repeat until you reach 1. Write hailstone(n), which prints every number in the sequence and returns how many numbers were printed.

func hailstone(_ n: Int) -> Int {
    // your code here
}

func hailstone(_ n: Int) -> Int {
    print(n)
    if n == 1 {
        return 1
    }
    let next = n % 2 == 0 ? n / 2 : 3 * n + 1
    return 1 + hailstone(next)
}

let steps = hailstone(10)   // prints 10 5 16 8 4 2 1, one per line
assert(steps == 7)
assert(hailstone(1) == 1)

Q3: Is it prime?

Write isPrime(n) using a helper function defined inside it, which checks candidate divisors starting from 2.

func isPrime(_ n: Int) -> Bool {
    // your code here
}

func isPrime(_ n: Int) -> Bool {
    func noDivisorFrom(_ k: Int) -> Bool {
        if k * k > n {
            return true
        }
        if n % k == 0 {
            return false
        }
        return noDivisorFrom(k + 1)
    }
    return n > 1 && noDivisorFrom(2)
}

assert(!isPrime(1))
assert(isPrime(2))
assert(isPrime(13))
assert(!isPrime(91))   // 7 * 13
assert((1...20).filter(isPrime) == [2, 3, 5, 7, 11, 13, 17, 19])

What’s next

Next lesson: tree recursion, where a function makes more than one recursive call.