Iteration¶

Our previous code to generate the Fibonacci numbers starts at n and then recursively calls smaller values of n until we reach base cases (n = 0 or n = 1). This lead to a lot of repeated calculations.

How about we do the reverse? Start with the base cases and build up higher and higher Fibonacci numbers?

Let's say we want to calculate F(5). This works as follows:

• Start with F(0) = 0 and F(1) = 1.
• Calculate F(2) = F(1) + F(2) = 0 + 1 = 1.
• Calculate F(3) = F(2) + F(1) = 1 + 1 = 2. (Use F(2) from previous calculation.)
• Calculate F(4) = F(3) + F(2) = 2 + 1 = 3.
• Calculate F(5) = F(4) + F(3) = 3 + 2 = 5.

This time our algorithm is just a sequence of steps.

flowchart LR;
a["F(0)"];
b["F(1)"];
c["F(2)"];
d["F(3)"];
e["F(4)"];
f["F(5)"];

a --> c;
b --> c;

c --> d;
b --> d;

d --> e;
c --> e;

e --> f;
d --> f;

f --> out([Output = 5]);

style out stroke-width:0;

Simple. This is how we calculate Fibonacci numbers on paper. Translating this logic into Odin:

fibonacci_iterative :: proc(n: int) -> int {
    a, b := 0, 1

    for _ in 1 ..= n {
        a, b = b, a + b
    }

    return a
}

Storing Values in Variables¶

To understand the line a, b := 0, 1, let's start with the basics. To declare a variable just write:

a: int = 2

The compiler can infer the type of 2 to be an int. So you can skip writing int:

a := 2

You can also assign multiple values at once.

a, b: int = 0, 1
a, b, c: int = 0, 1, 2

a, b := 0, 1
a, b, c := 0, 1, 2

For Loop¶

Though Odin also supports C like for loops, I prefer for i in .. as it is easy to reason about and prevents off by one errors. 0..<n is an exclusive range. It goes from 0, 1, 2, …, until n - 1. If you want to include n, you can write 0..=n. For example:

for i in 0 ..< 5 {
    fmt.println(i)
}

prints

0
1
2
3
4

break and continue work similar to other languages. By writing for _ in 1 ..= n { we are running the code inside the for loop n times. _ is a discarded variable.

Mutating Variables¶

Say you declared a variable x with a value of 25.

x := 25

You can change its value with =. This is called mutation or reassignment.

x = 5

At the start of the program a stores F(0) and b contains F(1). To get the next value of b (F(2)), we just have to add a and b. The next value of a is F(1) (the current value of b).

Therefore, until we reach F(n), at each step we have to: - update the value of a to b - update the value of b to a + b

So then why didn't we simply write the following?

// oops doesn't work
a = b
b = a + b

This doesn't work because the value of a changes but we need the old value of a to update b. We can create a temporary variable to store the old value of a and then update a.

old_a := a // save the old value of a
a = b
b = old_a + b

Or we can update both at the same time!

a, b = b, a + b

Analysis¶

Easy. We have a single for loop going from 1 to n. We do n steps in total and a constant amount of work in each step. So it a linear algorithm and way faster than our previous implementation.

For memory requirements, fibonacci_iterative store a and b and _ (the for loop index). Memory usage is constant.

Exercise¶

Modify the above procedure to return the sum of n Fibonacci numbers. For example, S(10) = F(0) + F(1) + ... + F(10) = 143.