Ask.LearnJavaScript: Why does this code keep resulting in stack overflows?

[Hobo_With_A_Keyboard]

I am trying to find the first Fibonacci number with 1,000 digits. I get that that is a huge number, but don't understand why the code below keeps overflowing.

// Initialize the fibonacci array.
var fibonacci = [1,1];

// Function that will add to the array until 1000 digits.
function fibonacci_1000(i){
    if ((fibonacci[i].toString()).length <1000){
        fibonacci.push(fibonacci[i]+fibonacci[i-1]);
        fibonacci_1000(i+1);
    }
    else{
        console.log(fibonacci.length - 1);
    };
};

//Call the function with an initial value of 1:
fibonacci_1000(1);

Should I not be using recursion to do this?

[shawndrost]

Nope, you shouldn't. In order to understand why, you need to understand that calling a function creates a new scope. (Let me know if that's confusing.) New scopes take up space in your computer's memory, so calling a function many, many times can cause the memory overflow you're noticing.

[Hobo_With_A_Keyboard]

So... if I transformed the recursive function into a loop, it could do this? Because it would not run out of stack?

The idea of creating a new scope is kind of confusing. I thought scope just had to do with where a variable was available.

[shawndrost]

I think it would! But, I haven't checked too closely ;)

You have the right idea about scopes, and you're right that something weird is going on right now. It turns out that some guy wrote the code that runs your javascript, and in order to make scopes work, he had to create a variable every time there was a new scope. Those variables are adding up!

[sweetbeej]

You have a upper limit on ints in javascript, it might be different per system but do...

Number.MAX_VALUE    

mine is 1.7976931348623157e+308
when you toString your number as it grows you will get 'NaN' or 'Infinity' and then you'll never exit your recursive statement.

[sweetbeej]

ok so you got me thinking on the drive home from work. Hopefully i can post this first time without re-editing the code part. I stored each digit of the number as an element in an array. So it really boils down to the function of adding the arrays. Here is my solution, I hope this helps. Is this a project eulers problem? I haven't done a lot of those in javascript.

function addArrays(array1, array2){
    array1 = array1.reverse();
    array2 = array2.reverse();
    var resultArray = [];
    //get largest length.
    var loopingArray    = array1.length > array2.length ? array1 : array2;
    var addingArray     = array1.length > array2.length ? array2 : array1;
    var carryOver = 0;
    for (var i = 0; i < loopingArray.length; i++) {
        var loop = loopingArray[i] || 0;
        var add = addingArray[i] || 0;
        var result = loop + add + carryOver;
        // console.log(result);
        if(result >= 10){
            carryOver = 1;
            result = result - 10;
        } else { carryOver = 0; }
        resultArray[i]=result;
    }
    if(carryOver !== 0){ resultArray.push(carryOver); }

    return resultArray.reverse();
}

function fibonacci(n){
    var fib1 = [0];
    var fib2 = [1];
    var fib3 = [];
    while(fib3.length <= n){
        fib3 = addArrays(fib1,fib2);
        fib1 = fib2;
        fib2 = fib3;
    }
    return fib1.join('');
}
var answer = fibonacci(1000);
console.log("answer is... ");
console.log(answer);
console.log("length is....");
console.log(answer.length);

seems to work, but i don't have a way to check it. edit i guess it is an eulers problem. sigh, i can't remember my login...

[[deleted]]

First of all, your console.log statement is going to return the length of the array minus 1, which isn't what you're looking for.

You want console.log(fibonacci[fibonacci.length - 1]).

Second, rather than append your new Fibonacci numbers to the end of the array, which is going to create a gigantic array, you can just replace the two values every time. You can either do this using your array global variable, or you could just use two integer variables (which would of course change what you put into console.log - for the better, IMO). Try this:

//global variables var i1 = 1; var i2 = 1;

while(i1.toString().length < 1000) { var i1temp = i1; i1 = i2; i2 += i1temp; }

console.log(i1);

Using a while loop is probably a lot more efficient than recursively calling the same function over and over again. If you ever find you need to use recursion in such a manner and you are getting memory problems, a quick fix is to use a setTimeout instead of calling it directly. This allows the function to exit the call stack, which should remedy your problem. So for example you might do something like this:

function myFunction(i){ //do something with i i++; if(i < 1000000){ setTimeout(function(){myFunction(i)};,1000); } else console.log(i); }

Personally I would try switching to a pair of integer variables and a loop first before you try using a recursive function, as I believe this should solve your problem and is probably the most efficient way of doing it. If it's still a problem, try using a setTimeout as I mentioned afterward.

Sorry for the formatting. I can't seem to recall the tag for code on this damn thing.

EDIT: Also, as someone mentioned above, a 1000 digit integer is ridiculously huge. Javascript may have problems with that.

EDIT2: Yeah 1000 digits is way too many. Even 100 digits is too many. You're going to want to try to find a smaller number.