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).