Specify a base case
In this example Fibonacci is defined on nonnegative integers with F(0) = 0 and F(1) = 1. Each call first checks whether its argument is smaller than two. A base case gives a direct answer and prevents another call.
Expand one call
For n = 4 the two subproblems are F(3) and F(2). F(3) needs F(2) and F(1), while each F(2) needs F(1) and F(0). Work back up the tree to get 2 + 1 = 3. Each invocation has its own parameter value.
Count work as well as depth
F(2) is evaluated twice in that small tree. Repeated subproblems make this recursive implementation expensive as n grows. An iterative version can carry the two most recent values in mutable bindings and advance one position per pass.
Choose a safe input
The interpreter has both a step budget and a maximum of 64 simultaneous calls. Keep practice inputs small. A native build also uses finite machine resources. Large Fibonacci numbers eventually exceed the checked i64 range regardless of the algorithm.
Try the program
Expected output
Fibonacci(10): 55
Practice
Print Fibonacci at position seven, with a matching label.
Hint
The function name also occurs in the label. Edit the label and the call.
Worked solution
Building the sequence from zero gives 0, 1, 1, 2, 3, 5, 8, 13. Position seven is 13.
Find
"Fibonacci(10):"Replace with
"Fibonacci(7):"Find
fibonacci(10)Replace with
fibonacci(7)Output after the change
Fibonacci(7): 13