Why is it that My code cannot calculate above Fibonnaci 30 and above

Question

I am running this but numbers above Fibonnaci 30 going onwards just keep loading.

Here is my code:

<script type="text/javascript">
function fib(n) {

    if (n <= 1) {
        return 1;
    } else {
        return (fib(n - 1) + fib(n - 2) + fib(n - 3));
    }
}

function start() {
    document.getElementById("result").innerHTML = fib(30)
}

window.addEventListener("load", start, false)
</script>

step through it with the debugger. There's a good chance you're hitting some recursion. — TankorSmash, Jul 03 '15 at 15:28
Fib(N) is Fib(N-1) + Fib(N-2); adding Fib(N-3) will give the wrong answer. — Pointy, Jul 03 '15 at 15:29
@JamesThorpe. How should it be. I honestly know very little about javascript — John, Jul 03 '15 at 15:30
@Pointy :) Removed my link ([it's here](http://jsfiddle.net/c2f843uy/) should anyone want it again) as it does actually get very long running with larger numbers. JO John - you're just hitting a really long recursion limit in your browser. — James Thorpe, Jul 03 '15 at 15:32
The problem here isn't so much about javascript specifically, it's more about the Fibonacci algorithm itself. I suggest you research that, rather than JavaScript specifically. — James Thorpe, Jul 03 '15 at 15:34
@JamesThorpe What do you mean when you say its hitting a long recursion. — John, Jul 03 '15 at 15:35
I'm not sure _what_ that means, I was typing too fast. What's going on is that when you call `fib(3)` say, it internally calls `fib` again 6 more times. If you call `fib(4)`, it internally calls itself 12 times. `fib(5)` will make that 25 times. It exponentially gets more with each one. By the time you get to 30, it's calling itself 104551006 times ([yes really](http://jsfiddle.net/c2f843uy/1/)), which is starting to take a while. Larger numbers just make it worse. — James Thorpe, Jul 03 '15 at 15:41
It really depends on your pc when the recursion is going to take such a long time that it looks like it's hanging, on my is around ~40. — Alberto Zaccagni, Jul 03 '15 at 15:49
@AlbertoZaccagni yes i noticed that my processor was getting all used up and my RAM too — John, Jul 03 '15 at 15:52
Please change the title of your question! BE SPECIFIC! For example: Fibonacci recursive function. And than describe your problem! — , Jul 03 '15 at 16:12
@James Thorpe maybe somebody should write the answer. It's quite confusing to read comments giving answer. — user2736738, Jul 03 '15 at 16:17
@coderredoc Done. Got caught up in the discussion in the comments without realising I'd actually answered the Q. — James Thorpe, Jul 03 '15 at 16:23

score 3 · Answer 1 · edited May 23 '17 at 12:31

The issue here is that as you increase the initial number passed in, it's calling itself exponentially more times internally.

When you call fib(3), say, it internally calls fib again 6 more times. If you call fib(4), it internally calls itself 12 times. fib(5) will make that 25 times. It exponentially gets more with each one.

By the time you get to 30, it's calling itself 104551006 times (yes really), which is starting to take a while. Larger numbers just make it worse.

This is an alternative recursive fibonnacci calculator, adapted from this psuedocode answer:

function fib(term, val, prev)
{
    if (!val)
        val = 1;
    if (!prev)
        prev = 0;

    if(term == 0) return prev;
    if(term == 1) return val;
    return fib(term - 1, val+prev, val);
}

alert(fib(6)); //gives 8, the 6th number in the sequence

score 2 · Answer 2 · edited Jul 06 '15 at 06:53

A solid implementation is always the best route, so James Thorpe's implementation is what you should go for. However, another approach to reducing calls to recursive functions is memoization. Essentially, memoization caches the results of a call to a function with a particular set of arguments.

Original Code (modified to return an actual Fibonnaci sequence):

var call_count = 0;

function fib(n) {
  call_count++;
  if (n <= 1) {
    return 1;
  } else {
    return fib(n - 1) + fib(n - 2);
  }
}

alert('fib(15): ' + fib(15) + '; call_count: ' + call_count);

Memoized Code

var call_count = 0;

// See http://www.sitepoint.com/implementing-memoization-in-javascript/
function memoize(func) {
  var memo = {};
  var slice = Array.prototype.slice;

  return function() {
    var args = slice.call(arguments);  // Turn 'arguments' into a real array

    if (args in memo)
      return memo[args];
    else
      return (memo[args] = func.apply(this, args));

  }
}

function fib(n) {
  call_count++;
  if (n <= 1) {
    return 1;
  } else {
    return fib(n - 1) + fib(n - 2);
  }
}

// Replace fib with memoized version
fib = memoize(fib);

alert('fib(30): ' + fib(30) + '; call_count: ' + call_count);

Why is it that My code cannot calculate above Fibonnaci 30 and above

2 Answers2