CSci 101 Part II
Okay, so yesterday we saw one
way to generate the "nth" fibonacci number using recursion. The
recursion that we used is also called "tree recursion",
the reason for this being that we made two recursive calls inside the
function. If you were to draw a diagram of the function calls, the diagram
would take on the shape of a tree, because every node would have two
branches, like this:
If you tried to use this function to find the 35th fibonacci
number, you probably realized that it can take quite a bit of time. The
reason for this is that we are computing the same value many times over.
Consider what happens when you call Fibo(4). The function is going to add
Fibo(3) + Fibo(2). Fibo(3) will, in turn, call Fibo(2) + Fibo(1). So
you can see that we are calling Fibo(2) twice, which is a waste. Its
not a big deal for only the 4th fibonacci number, but when you put in 50, the
extra work can definitely start to make a difference.
See if you can come up with a way to speed up the function,
and I'll post my ideas tomorrow, along with a performance comparison of a
few different functions. Thanks for reading!