# SICP Goodness - Fibonacci numbers

About fibonacci numbers and more

Do you think Computer Science

equalsbuilding websites and mobile apps?Are you feeling that you are doing

repetitiveandnot so intelligentwork?Are you feeling a bit

sickaboutreading manualsandcopy-pastingcode and keeppoking arounduntil it worksall day long?Do you want to understand the

soulofComputer Science?If yes,

read SICP!!!

Every programmer at some point has studied fibonacci numbers, mostly likely as an interview question. Just in case you forget it, let’s give the definition here:

fib(0) = 0

fib(1) = 1

fib(n) = fib(n - 2) + fib(n - 1)

0 1 1 2 3 5 8 13 21 34 55 …

In interviews, it is normally used to test the programmer’s knowledge about recursion. The easiest anwser would be:

```
(define (fib n)
(cond ((= n 0) 0)
((= n 1) 1)
(else
(+ (fib (- n 2)) (fib (- n 1))))))
```

This is a direct translation from the definition, so it is quite easy to get right even in interviews.

Then a question that might come immediately after this is to write an iterative version.

Try it yourself.

OK, if you can write it out like second nature, then close this page and spend more time with your family.

If you cannot solve it or it took you a very long time, then you can read on.

OK, I admit that though have looked up the anwser several times already, after a while I still have hard time writing it from scratch.

Until I read SICP.

Let’s say we have two variables, `current = 0`

, `next = 1`

.

The steps to compute `fib(n)`

iteratively is:

- If
`n = 0`

just return`current`

. - Do
`current <- next`

`next <- current + next`

*simultaneously*and`n--`

. - Go to step 1.

Think of `current`

as something that is concrete and can be returned, `next`

as something that is in the future and not yet reachable.

Let’s try to calculate `fib(3)`

as an example.

In order to calculate `fib(3)`

, we have to calculate from `fib(0)`

to `fib(3)`

.

At the beginning, we already have `current = 0`

, `next = 1`

.

```
next 1
-------------
current 0
```

This can be interpreted as:

If someone asks us what is the current fib number, which is `fib(0)`

, we can tell him 0. But note that we cannot use the `next`

directly now because it is *in the future*, so if he asks us what is `fib(1)`

, we have to tell him that we do not know yet.

Next we calculate `fib(1)`

.

Now we can bring the `next`

to the `current`

. And at the same time, we have to calculate a new next value by `next <- current + next`

. Notice all these happens simultaneously, there is no ordering. Or you can think of it as if we are using some temporary variable: `temp <- current, current <- next, next <- temp + next`

.

```
next 1 1
-----------------
current 0 1
```

At this point, we know `fib(1) = 1`

.

Next calculate `fib(2)`

.

Do `current <- next`

and `next <- current + next`

as before:

```
next 1 1 2
---------------------
current 0 1 1
```

So `fib(2) = 1`

.

The same for `fib(3)`

:

```
next 1 1 2 3
-------------------------
current 0 1 1 2
```

So `fib(3)`

is 2.

Now if you understand these, writing a iterative procedure becomes much easier:

```
(define (fib-iter current next n)
(if (= n 0)
current
(fib-iter next (+ current next) (- n 1))))
(define (fib n)
(fib-iter 0 1 n))
```

To test your understanding, solve this exercise in SICP:

*Exercise 1.11*

A function

fis defined by the rule thatf(n) = n if n < 3andf(n) = f(n-1) + 2f(n-2) + 3f(n-3)ifn>= 3. Write a procedure that computesfby means of a recursive process. Write a procedure that computesfby means of an iterative process.

# Answer

```
(define (f-recur n)
(cond ((< n 3) n)
(else
(+ (f-recur (- n 1)) (* 2 (f-recur (- n 2))) (* 3 (f-recur (- n 3)))))))
(define (iter a b c n)
(cond ((= n 0) c)
((= n 1) b)
((= n 2) a)
(else
(iter (+ a (* b 2) (* c 3)) a b (- n 1)))))
(define (f-iter n) (iter 2 1 0 n))
```

P.S. Chapter 3.5.2 of the book talks about

infinite streams. And the fibonacci number appears again. This time, the fib number is computed by adding two infinite streams of fib numbers. Since there are too many new things going on, I leave this to readers who want to explore more.

## Share this post

Twitter

Google+

Facebook

Reddit

LinkedIn

StumbleUpon

Email