Exercise: Fibonacci

The Fibonacci sequence begins with [0, 1]. For n > 1, the next number is the sum of the previous two.

Write a function fib(n) that calculates the nth Fibonacci number. When will this function panic?

fn fib(n: u32) -> u32 {
    if n < 2 {
        // The base case.
        return todo!("Implement this");
    } else {
        // The recursive case.
        return todo!("Implement this");
    }
}

fn main() {
    let n = 20;
    println!("fib({n}) = {}", fib(n));
}
This slide and its sub-slides should take about 15 minutes.
  • This exercise is a classic introduction to recursion.
  • Encourage students to think about the base cases and the recursive step.
  • The question “When will this function panic?” is a hint to think about integer overflow. The Fibonacci sequence grows quickly!
  • Students might come up with an iterative solution as well, which is a great opportunity to discuss the trade-offs between recursion and iteration (e.g., performance, stack overflow for deep recursion).