Fibonacci

recursion, base case, recursive call

Do not paste the complete program immediately. Create the file, type the first step, run vpp check, and then run the program when a complete entry point exists. Read the explanation before looking at the snippet. After each step, predict what the new code should do. This turns the page into a lesson rather than a code dump.

A recursive function needs a base case that stops recursion. Here n values of zero and one are already known, so the function returns n immediately.

For larger n, the function reduces the problem into two smaller Fibonacci problems. Each call creates more work until the base cases are reached.

After typing the snippet, identify the new names introduced by the step. Ask what each name represents, what type the compiler should infer or check, and what value should exist after the code runs.

fn fib(n: int) -> int {
    if n <= 1 {
        return n
    }
    return fib(n - 1) + fib(n - 2)
}

Calling fib with small values is useful for understanding the sequence. fib(10) and fib(15) also show that the compiler supports nested recursive calls and integer expression evaluation.

Before moving forward, explain how this step connects to the previous one. In particular, identify which values cross a function boundary, which values change, and which values are guaranteed by the type system.

fn main() -> int {
    print(fib(0))
    print(fib(1))
    print(fib(10))
    print(fib(15))
    return 0
}

The complete program should produce the following output when run with the command shown below. Exact formatting should follow the current V++ runtime.

0
1
55
610

Recursion needs a base case. Every recursive call should move toward that base case so evaluation can finish.

1. No base case
2. Recursive calls that do not approach the base case
3. Testing very large inputs before understanding the recursive cost

Trace fib(5) by hand. Then write a second recursive function that calculates factorial.

A strong learner should be able to explain the program without looking at the code, rebuild the core idea from memory, and make the practice change without copying a solution.