MY CODE KILLED MY COMPUTER!!!!!

[appnerd]

I wrote a recursive function to solve for a number in the Fibonacci sequence:

fib(int num)
{
if (num == 1 || num == 2)
    return 1;
return fib(num-1) + fib(num-2)
}

I called it with 10000.

It killed my computer.

Why?

[Luc Lieber]

If it killed the computer how are you posting :-\ Maybe it just knocked it out for a little while :P

That might have overflowed your stack. Recursion is notorious for that.

[simeonz]

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.

[clover leaf]

this:
return fib(num-1) + fib(num-2)
It's requesting for itself, therefore creating an infinitive loop.

[Zhuge]

@clover leaf: It's not an infinite loop. It's recursion.

[pcannons]

You are using int which is 4bytes.

The limits of int are:
signed: -2147483648 to 2147483647
unsigned: 0 to 4294967295

With a signed integer you are able to compute 46 digits of the Fibonacci sequence before it goes over the int limit.

Fibonacci sequence
46 : 1836311903
47 : 2971215073

[Jaso333]

You ALWAYS rerturn, whethert he IF statement is true or not. This function is being called infinitely, clover loaf was right.

[Jaso333]

@pcannons: going over the INT limit does not freeze your computer, the processor simply truncates the value.

[Grey Wolf]

Assuming the syntax errors are just typos.

Jaso333 wrote:

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:

int fib(int num)
{
    if (num == 1 || num == 2)
    {
        std::cout << ".";
        return 1;
    }
    return fib(num-1) + fib(num-2);
}
...

std::cout << "fib(5) = " << fib(5) << std::endl;
std::cout << "fib(10) = " << fib(10) << std::endl;
std::cout << "fib(15) = " << fib(15) << std::endl;

.....fib(5) = 5
.......................................................fib(10) = 55
..................................................................................................................................
..................................................................................................................................
..................................................................................................................................
..................................................................................................................................
..........................................................................................fib(15) = 610

As you get to very large numbers the run time will seem like the program has crashed.

Even if and when it does finish you will not get the correct answer because, as pcannons said, an int can't hold a number that big.

#include <iostream>
#include <deque>
#include <numeric>

double Fibonacci(unsigned int num)
{
    std::deque<double> q(2, 0);

    q[0] = 1.0;

    for(unsigned int i = 1; i < num; ++i)
    {
        q.push_front( accumulate( q.begin(), q.end(), 0.0 ) );

        q.pop_back();
    }
    return q[0];
}

void Fibonacci_sequence(unsigned int num)
{
    std::deque<double> q(2, 0);

    q[0] = 1.0;

    for(unsigned int i = 1; i < num; ++i)
    {
        std::cout << q[0] << " ";
        q.push_front( accumulate( q.begin(), q.end(), 0.0 ) );

        q.pop_back();
    }
    std::cout << std::endl;
}

int main()
{
    Fibonacci_sequence(25);

    std::cout << "Fibonacci(10)  = " << Fibonacci(10) << std::endl;
    std::cout << "Fibonacci(50)  = " << Fibonacci(50) << std::endl;
    std::cout << "Fibonacci(100) = " << Fibonacci(100) << std::endl;
    std::cout << "Fibonacci(500) = " << Fibonacci(500) << std::endl;

    return (0);
}

1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368
Fibonacci(10)  = 55
Fibonacci(50)  = 1.25863e+010
Fibonacci(100) = 3.54225e+020
Fibonacci(500) = 1.39423e+104

[appnerd]

Oh.

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.

[rocketboy9000]

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:

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.

[JoR]

If it freezes the computer, your OS really sucks!

[pwnedu46]

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.

**

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)
}

[simeonz]

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?

Regards

[Grey Wolf]

pwnedu46 wrote:

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".

[rocketboy9000]

His code doesn't kill my computer, but mine is linux.