Tree recursion

The recursive functions in the last lesson made one recursive call each. A function that makes two or more calls is tree recursive: drawn out, its calls branch like a tree.

Fibonacci, again

The Fibonacci numbers are defined in terms of the two before them, so the most direct recursive definition makes two calls:

func fib(_ n: Int) -> Int {
    if n < 2 {
        return n
    }
    return fib(n - 2) + fib(n - 1)
}
print(fib(10))   // 55

Here is the tree of calls for fib(4):

                    fib(4)
            ┌─────────┴──────────┐
         fib(2)                fib(3)
       ┌───┴───┐          ┌──────┴──────┐
    fib(0)  fib(1)     fib(1)        fib(2)
                                   ┌───┴───┐
                                fib(0)  fib(1)

fib(2) is computed twice, and the repetition gets much worse as n grows. We can count the calls with a global variable:

var calls = 0
func fib(_ n: Int) -> Int {
    calls += 1
    return n < 2 ? n : fib(n - 2) + fib(n - 1)
}
_ = fib(5)
print(calls)

For fib(20) the count is 21,891. The iterative version from Lesson 3 needs only 19 trips through its loop. Tree recursion is often the clearest way to describe a computation, and later, in the lesson on efficiency, we will see how to keep that clarity without the repeated work.

Counting partitions

Tree recursion shines when a problem splits into cases. CS61A’s favorite: in how many ways can a positive integer n be written as a sum of positive parts, each at most m, in increasing order? For n = 6, m = 4 there are 9:

2 + 4    1 + 1 + 4    3 + 3    1 + 2 + 3    1 + 1 + 1 + 3
2 + 2 + 2    1 + 1 + 2 + 2    1 + 1 + 1 + 1 + 2    1 + 1 + 1 + 1 + 1 + 1

The key insight is to split every partition into two groups: those that use at least one m, and those that use no m.

• A partition that uses m is m plus a partition of n - m with parts up to m.
• A partition that does not use m is a partition of n with parts up to m - 1.

Both groups are smaller instances of the same problem.

func countPartitions(_ n: Int, _ m: Int) -> Int {
    if n == 0 {
        return 1
    } else if n < 0 || m == 0 {
        return 0
    }
    return countPartitions(n - m, m) + countPartitions(n, m - 1)
}
print(countPartitions(6, 4))   // 9

The base cases need care. n == 0 means we have exactly used up the number, which is one successful partition. n < 0 means we overshot, and m == 0 means there are no parts left to use; both count zero.

func countPartitions(_ n: Int, _ m: Int) -> Int {
    if n == 0 {
        return 1
    } else if n < 0 || m == 0 {
        return 0
    }
    return countPartitions(n - m, m) + countPartitions(n, m - 1)
}
print(countPartitions(5, 3))

func countPartitions(_ n: Int, _ m: Int) -> Int {
    if n == 0 {
        return 1
    } else if n < 0 || m == 0 {
        return 0
    }
    return countPartitions(n - m, m) + countPartitions(n, m - 1)
}
print(countPartitions(6, 4))

Printing a whole tree

A tree-recursive function can do work at every node, not just combine answers. The Towers of Hanoi moves a stack of n disks from one peg to another, one disk at a time, never putting a larger disk on a smaller one. To move n disks, move n - 1 out of the way, move the largest, then move the n - 1 back on top:

func hanoi(_ n: Int, from start: Int, to end: Int) {
    if n == 0 {
        return
    }
    let spare = 6 - start - end   // the third peg, since 1 + 2 + 3 == 6
    hanoi(n - 1, from: start, to: spare)
    print("Move disk \(n) from \(start) to \(end)")
    hanoi(n - 1, from: spare, to: end)
}
hanoi(3, from: 1, to: 3)

func hanoi(_ n: Int, from start: Int, to end: Int) {
    if n == 0 {
        return
    }
    let spare = 6 - start - end
    hanoi(n - 1, from: start, to: spare)
    print(n, start, end)
    hanoi(n - 1, from: spare, to: end)
}
hanoi(2, from: 1, to: 3)

Lab 7: Tree recursion

Q1: Climbing stairs

You can climb a staircase one or two steps at a time. Write countStairWays(n), the number of different ways to climb n steps.

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

func countStairWays(_ n: Int) -> Int {
    if n <= 1 {
        return 1
    }
    return countStairWays(n - 1) + countStairWays(n - 2)
}

assert(countStairWays(1) == 1)
assert(countStairWays(2) == 2)   // 1 + 1, or 2
assert(countStairWays(4) == 5)
assert(countStairWays(10) == 89)

Q2: Making change

Count the ways to make total cents from quarters (25), dimes (10), nickels (5), and pennies (1). nextSmallerCoin is given; it returns 0 after pennies. Order does not matter: 5 + 10 and 10 + 5 are the same way.

func nextSmallerCoin(_ coin: Int) -> Int {
    switch coin {
    case 25: return 10
    case 10: return 5
    case 5: return 1
    default: return 0
    }
}

func countCoins(_ total: Int) -> Int {
    // your code here, probably with a helper
}

func nextSmallerCoin(_ coin: Int) -> Int {
    switch coin {
    case 25: return 10
    case 10: return 5
    case 5: return 1
    default: return 0
    }
}

func countCoins(_ total: Int) -> Int {
    func count(_ total: Int, _ largest: Int) -> Int {
        if total == 0 {
            return 1
        } else if total < 0 || largest == 0 {
            return 0
        }
        let usingLargest = count(total - largest, largest)
        let withoutLargest = count(total, nextSmallerCoin(largest))
        return usingLargest + withoutLargest
    }
    return count(total, 25)
}

assert(countCoins(15) == 6)
assert(countCoins(10) == 4)
assert(countCoins(20) == 9)
assert(countCoins(100) == 242)

Q3: Grid paths

An insect starts in the bottom-left corner of an m by n grid and wants to reach the top-right corner, moving only up or right. Write paths(m, n), the number of different routes.

func paths(_ m: Int, _ n: Int) -> Int {
    // your code here
}

func paths(_ m: Int, _ n: Int) -> Int {
    if m == 1 || n == 1 {
        return 1
    }
    return paths(m - 1, n) + paths(m, n - 1)
}

assert(paths(2, 2) == 2)
assert(paths(5, 7) == 210)
assert(paths(117, 1) == 1)
assert(paths(1, 157) == 1)

What’s next

That ends Unit 1. Unit 2 turns from functions to data, starting with sequences: arrays, ranges, and strings.