Fibonacci recursive alg help

[newbiepcuser]

I'm noob at programming.

Yes, this is for homework and got the code down. I know Fib recursive is not good way to do this but its part of the assignment.


When I input a large number such as 64, it still chugging along.
Its been several hours. How long should it take? Did I implement it wrong? If anybody can help, I would appreaciate it.

Thanks

 

[MSCoder610]

The point of implementing Fibonacci recursively like that is probably to, in fact, show you how long it takes for large numbers. (The main reason is the two recursive calls in the function, instead of just 1). If you draw a tree of the recursive calls you can see how quickly it will branch out (exponentially).

 

[newbiepcuser]

Originally posted by: MSCoder610
The point of implementing Fibonacci recursively like that is probably to, in fact, show you how long it takes for large numbers. (The main reason is the two recursive calls in the function, instead of just 1). If you draw a tree of the recursive calls you can see how quickly it will branch out (exponentially).

So in others words, it is taking long as expected. Left it over night and its still chugging.

 

[notfred]

Recursive fibonacci numbers aren't that slow if you do it right. By "right" I mean you make only one recursive call in your function and not 2.

Example perl script:

sub calc{
my $num = $_[0];
if($num == 1){
return (0, 1);
}

my @last2 = calc($num - 1);
my $thisnum = $last2[0] + $last2[1];
print "$thisnum, ";
return ($last2[1], $thisnum);
}


Realyl though, it makes more sense not to do this recursively.

 

[Kyteland]

The number of function calls for a recursive fibonacci function increases twice as fast as the actual fibonacci sequence. So if you are calculating f(N) then you must make (approximately) 2*f(N) function calls in order to calculate it. Since f(64) = 1.90392E+14 then you must call your function 3.80785E+14 times to calculate the number. Thats a lot of function calls.

The reason that it increses twice as fast is because you call f(N) once and then you call f(N-1) and f(N-2). If you define F(N) to be the number of function calls to calculate f(N), then F(N) = 1+F(N-1)+F(N-2) which increses twice as fast as f(N).

 

[duragezic]

You can speed it up a little bit by saving one of the values as an int so it doesn't need to be calculated again for the next call. Or just don't test it with such large values. Your instructor probably just wants to make a point.

 

[DidlySquat]

Here's a non recursive version which is way faster

float fib3(float n)
{
float s0 = 0;
float s1 = 1;
float s2 = s0 + s1;
float c;

for (c = 0; c<n; c++)
{
s0 = s1;
s1 = s2;
s2 += s0;
}

return s0;
}


[pwned]

 

[Crusty]

Originally posted by: DidlySquat
Here's a non recursive version which is way faster

float fib3(float n)
{
float s0 = 0;
float s1 = 1;
float s2 = s0 + s1;
float c;

for (c = 0; c<n; c++)
{
s0 = s1;
s1 = s2;
s2 += s0;
}

return s0;
}


[pwned]

Wow... the whole point of the assignment was to write it recusively.... way to be an asshole.

 

[DidlySquat]

Wow...the whole point of the assignment was to write it in the most inefficient way possible......way to be a stupid moron

 

[Kyteland]

Originally posted by: DidlySquat
Wow...the whole point of the assignment was to write it in the most inefficient way possible......way to be a stupid moron

Hey moron, if your point was to be efficient you missed your mark by O(N).

double fib3(double n)
{
double phi1 = (1+sqrt(5.0))/2;
double phi2 = (1-sqrt(5.0))/2;
return (pow(phi1,n)-pow(phi2,n))/sqrt(5.0);
}

O(1). Way to be an asshole. :roll:

 

[newbiepcuser]

Originally posted by: Kyteland

Originally posted by: DidlySquat
Wow...the whole point of the assignment was to write it in the most inefficient way possible......way to be a stupid moron

Hey moron, if your point was to be efficient you missed your mark by O(N).

double fib3(double n)
{
double phi1 = (1+sqrt(5.0))/2;
double phi2 = (1-sqrt(5.0))/2;
return (pow(phi1,n)-pow(phi2,n))/sqrt(5.0);
}

O(1). Way to be an asshole. :roll:

Binet's formula 🙂

DidlySquat I was assigned that recursive algorithm. Yes I'm aware of more faster ways but its was the professor's choice so I could anaylze it along with Binet's formula.

Thanks everybody for the help. :thumbsup:

 

[DidlySquat]

Well I never said my solution was the most efficient, just that it was better than the recursive solution. bottom line is that professors should stop using stupid assignments which make no sense. There is no shortage of real problems where recursion would be a good choice....

[prof pwned]

 

[AnthraX101]

FYI:

You have an O(2^N) solution there. For 64, you have about 1.84467441*10^19 steps.

No, it's not going to finish. 🙂

For extra credit: There is an O(N) recursive solution, if you are allowed to modify the function prototype. 🙂

AnthraX101

 

[statik213]

Originally posted by: Kyteland

Originally posted by: DidlySquat
Wow...the whole point of the assignment was to write it in the most inefficient way possible......way to be a stupid moron

Hey moron, if your point was to be efficient you missed your mark by O(N).

double fib3(double n)
{
double phi1 = (1+sqrt(5.0))/2;
double phi2 = (1-sqrt(5.0))/2;
return (pow(phi1,n)-pow(phi2,n))/sqrt(5.0);
}

O(1). Way to be an asshole. :roll:

lol

 

[Kyteland]

Originally posted by: AnthraX101
FYI:

You have an O(2^N) solution there. For 64, you have about 1.84467441*10^19 steps.

No, it's not going to finish. 🙂

For extra credit: There is an O(N) recursive solution, if you are allowed to modify the function prototype. 🙂

AnthraX101

O(phi^n) where phi = (1+sqrt(5))/2 to be exact. 😀

 

[xtknight]

bleh...what is meant exactly by O(n), O(2^N), etc?

 

[Kilrsat]

Big O notation, Used for analyzing algorithms.

http://en.wikipedia.org/wiki/Big_O_notation#Common_orders_of_functions