Actually the recursion depth is linear. I think your computer froze. Your code has exponential time complexity and this means that you will probably be unable to handle inputs bigger than, say 40 or smth like that. I am afraid to sound pompous, but this is not so hard to see. I looked-up in google for the exact time complexity and it is Θ(𝜙 ^ n). Now, this is not obvious to me.
Anyway, there is a linear solution (one that can handle 10000 with no effort). There is somewhat harder to understand, but still quite manageable logarithmic solution (one that can handle astronomical inputs if you have the right arithmetic support underneath).
Regards
P.S. It just occurred to me, that actually no matter what solution you use, you will be unable to compute fib(10000) without support for arbitrarily large integers.
You ALWAYS rerturn, whethert he IF statement is true or not. This function is being called infinitely, clover loaf was right.
The function is recursive, meaning that it calls itself. It has guards to stop it from calling itself infinitely and the guards do look fine. This in borne out by calling it with a small number, it returns with the correct result.
The problem is that this algorithm explodes into a very long runtime very quickly.
A minor modification to the code will show this:
Thanks for the help! I randomly assumed that since 10000 was an int, all would be well. However, I was wrong.
10000 points to Grey Wolf for the help!!!
A note to everyone reading this now that didn't post above: DON'T RUN MY CODE!!!!! DANGER WILL ROBINSON!!!!!
A note to those people who don't understand basic recursion: Since the function is calling itself with lower and lower numbers, there's no problem; it eventually ends.
You should in most cases use a loop instead of recursion; recursion though a nice algorithm, is very memory and time wasteful. And here you are calling fib twice for every call, making this call approx. 2^n times, producing n call frames.
It's better to use a loop that builds the number upward:
1 2 3 4 5 6 7 8 9 10
int fib(int n){
int a=0,b=1,i=1;
while(i<n){
int s=a+b;
a=b;
b=s;
i++;
}
return b;
}
This code runs through the loop n-1 times, and takes only a small, constant amount of memory.
The operating system doesn't affect it that much. It can slow it down by at the most, I'd estimate only a few seconds, depending on how well the OS is coded, and the features implemented in it, It shouldn't lead to a freeze. It's more likely that your code was the problem. Try adding a pause** somewhere in there so it doesn't put as much strain on your hardware. Also, if the problem persists, try getting a better processor and/or more RAM.
**
1 2 3 4 5 6 7
fib(int num)
{
Pause(#ofMillimeconds) // make sure this is BEFORE THE RECURSION CALL or it won't be effective. I've learned this from experience. (I blue screened DX)
if (num == 1 || num == 2)
return 1;
return fib(num-1) + fib(num-2)
}
JoR means that the scheduler is responsible to prevent a single program from freezing the entire system. Windows is quite good at letting that happen. I have always wondered why is that possible? Aren't there better scheduling algorithms?
It's more likely that your code was the problem. Try adding a pause** somewhere in there so it doesn't put as much strain on your hardware. Also, if the problem persists, try getting a better processor and/or more RAM.
This is very odd, if the hardware can't keep up its a software problem? I have known PCs to flake out under load, usually because of clogged up heat sinks and fans any the solution was never to use more inefficient software.
It would be nice if the OP specified what he meant by "KILLED MY COMPUTER".