Practice: Factorial, Fibonacci, Tower of Hanoi

Compare three recursive shapes

Implement factorial, Fibonacci, and Tower of Hanoi, recording outputs and operation counts. They have different recurrences despite all being commonly introduced with recursion.

Copy codefun fibonacci(n: Int): Long {
    require(n in 0..92)
    if (n == 0) return 0
    var previous = 0L
    var current = 1L
    repeat(n - 1) {
        val next = previous + current
        previous = current
        current = next
    }
    return current
}

This computes F(0)=0, F(1)=1 in O(n) time and O(1) auxiliary space. The bound keeps results within signed Long. Naive branching recursion repeats subproblems; Hanoi must output 2ⁿ-1 moves, so its exponential output cannot be removed while listing every move.

Acceptance checks

Verify factorial at zero, one, and twenty; Fibonacci at zero, one, two, ten, and ninety-two; and Hanoi with one through four disks. Simulate each Hanoi move to confirm no larger disk is placed on a smaller one.

Check: reducing redundant computation helps Fibonacci, but does not shrink Hanoi's required move list.

Further reading: Recursion costs