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 computations and slowed down our code.

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 the logic looks like 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

For the first time ever, we are assigning values to variables. To understand the line a, b := 0, 1, let’s start with the basics. The basic syntax for declaring a variable is:

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. We will explore them in the next chapters. By writing for _ in 1 ..= n { we are running the code inside the for loop n times.

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) = Θ (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.