-
fibonnaci question...
ok so i have to do a fibonnaci algorithm. not to terrible to write. however it wasnt working so i set break points all the place to see why it might be failing.
and heres what i discovered its doing and why im confused by it.
Code:
int recurvsiveFibonacci(int n)
{
//there is a breakpoint on each of the lines of code
if (n == 1 || n == 0)
{
return n;
}
else{
return (recurvsiveFibonacci(n-1) + recurvsiveFibonacci(n-2));}
}
what happens is it goes through the if statement find the first two times(im reading numbers from a file and just passing the counter in as n(ya im not sure if that part of my program is being done right but can deal with that next wont do me any good if the recursion wont work properly)
so the first two numbers i pass through are 0 and 1. it goes to the if checks it and returns it as it should. then it passes in 2 and from here on out it goes up to 9 or 10. and now anytime from passing 2 and above in as the variable n what happens is it seems to go nuts. it goes back to the if statement when it drops to 1. then goes to the return n statement and just skips over it. then goes back to the if statement where n is now 0. passes it. goes to return n and again just goes to it without returning n. then n ends up changing to some random number like 4 or maybe 7 not really sure the order of it other than my output is the same every time.
also it might even goto the if statement as n. goto the return statement and do nothing about it. then n might change from 1 to 3.
i seriously have no clue how or why n is changing values at seemingly random(though not random as i get the same output every time)
if anybody can drop a hint or two or outright explain this crazyness i love that. it would be much appreciated.
-
But does it produce the right answer?
If the compiler has performed "tail recursion optimization" on the code, then you won't see nice recursive calls, only weird jumps and other effects.
-
Works perfectly for me, maybe you're doing something weird instead of printing the function's output.
Code:
#include <iostream>
int recurvsiveFibonacci(int n)
{
//there is a breakpoint on each of the lines of code
if (n == 1 || n == 0)
{
return n;
}
else
{
return (recurvsiveFibonacci(n-1) + recurvsiveFibonacci(n-2));
}
}
int main()
{
for (int i = 0; i != 10; ++i)
std::cout << recurvsiveFibonacci(i) << ' ';
std::cout << std::endl;
return 0;
}
Output:
Code:
0 1 1 2 3 5 8 13 21 34
-
oh well i was under the impression since it jumped around all the time it was messing up. is there a reason it does this? how does that optimize it?
lol i guess i just didnt know those were the right answers. i guess i assumed it was wrong because n was jumping all over the place. oh well would of been nice if the teacher explained hey your compiler might jump all over the place doing recursion functions.
-
That's why it's better to just build a project without optimization when debugging.