Structure and Interpretation of Computer Programs

The arrow is showing what the computer is doing to find fib(n) while using recursion. That is when the computer wants to find fib(5) the first thing it does is split it into fib(4) + fib(3), then it takes the first function and tries to calculate that, splitting that into fib(3) + fib(2), then tries to calculate fib(3)....

So you see the program will first run fib(5), then fib(4) then fib(3), then fib(2), then fib(1) finally resolving that as 1. Only then will it take the other branches, the fib(n-2) cases. In this case we go up one layer and find we need to resolve fib(0), which we can, 0.

The arrow is indicating how the program will calculate fib(5), in order it will calculate those functions all the way to the base cases, that is the cases we know how to solve, in this case fib(0)=0 and fib(1)=1.

The point is we end up calculating fib(0) 3 times, fib(1) 5 times, fib(2) 3 time, and fib (3) twice. Clearly this isn't the most efficient way of doing this. Worse, as it explains later in the chapter, as n gets bigger the worse this gets, it's O(n^2). You see when we double n, from 5 to 10, the number of steps needed is much more then doubled. If you were to draw out the tree for fib(10) you would see it there are many more nodes to calculate.

Then they go into the golden ratio part. The important thing at first, isn't the golden ratio but for now just assume that function is correct. That means you can calculate fib(5) using a formula and the closest integer will be fib(n). So instead of going though all that work with the tree and the recursive algorithm we could write a program preform function instead! This means no matter how big n is we have we can find fib(n) in the same amount of time - O(1), because now we just calculate a formula, instead of a recursive algorithm.

Now, I'm still not sure how to prove this function is correct though.... that is problem 1.13. I'm getting hung up on the fact that it is the closest integer.... I'm not how to use that with induction, or any proof... any help here would be welcomed.

I would certainly like to see that when I go over it later.

I think this fib function is a good application for the lazy evaluation of Haskell.