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:
src="http://dotnetjunkies.com/WebLog/images/dotnetjunkies_com/barblog/2293/r_fibo.GIF"
width=640 border=0>
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!
Anonymous said,
Wrote on January 20, 2005 @ 3:29 am
The first thing I would try is to make an array of size n when fibo(n) is called. Then if the value was in the array, return it, else calculate it recursively (which will also do the lookup).
That way it should be on the O(n), right? I always get my big-O notation whacked.
Anonymous said,
Wrote on January 20, 2005 @ 4:16 am
Darrell, you keep ruining my fun!!
Yes, you’re right on about the array, thanks for reading!
Anonymous said,
Wrote on January 20, 2005 @ 6:33 am
Sorry. I won’t answer next time!
Anonymous said,
Wrote on January 20, 2005 @ 9:29 am
I thought about the array, but decided I’d rather try and use tail calls, so that I wouldn’t have to create a data structure:
int fibofact(int ordinal, int* pfactor)
{
if (ordinal == 1)
{
*pfactor = 0; return 0;
}
if (ordinal == 2)
{
*pfactor = 0; return 1;
}
int myfactor = 0;
*pfactor = fibofact(ordinal-1, &myfactor);
return *pfactor + myfactor;
}
int fibo(int ordinal)
{
if (ordinal == 1)
return 0;
if (ordinal == 2)
return 1;
int myfactor = 0;
return fibofact(ordinal-1, &myfactor)+myfactor;
}
Anonymous said,
Wrote on January 20, 2005 @ 9:37 am
alright, we got some c++ out there, now we’re really getting academic
I like the use of the pointers, good stuff!