BlyxDocumentation
Browse chapters
Documentation / Language essentials

Recursion and the cost of a call

Trace Fibonacci by hand, identify the base case, and decide when iteration is cheaper.

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

Output Ready
Expected output
Fibonacci(10):
55
Open in the full playground →

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