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: i.e 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

And skip specifying the type just like before.

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

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 it's 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 i.e 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.

\[T(n) = \Theta(n)\]

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

Exercise

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