Fibonacci fibonacci

I was typing stuff into node.js today, and I was curious to know what would happen if I fed the Fibonacci function into itself. Feeling lazy, I first implemented the function the easy way, which takes an exponential time to compute:

fib = function(n) { return n < 2 ? n : fib(n-2) + fib(n-1); }

But when I ran it on numbers from 1 to 10, it hung after 9:

1 1
2 1
3 1
4 2
5 5
6 21
7 233
8 10946
9 5702887

So I decided to do it properly, using the non-recursive way of computing the Fibonacci sequence:

function fib(n) {
   var a, b = 1, c = 1;
   while (--n) {
      a = b;
      b = c;
      c = a + b;
   }
   return b;
}

This time everything computed immediately. Here are the first 11 results of fib(fib(n)):

1  1
2  1
3  1
4  2
5  5
6  21
7  233
8  10946
9  5702887
10  139583862445
11  1779979416004714000

After that it totally blows up. fib(fib(12)) is about 1030, fib(fib(16)) is about 10206, and from 17 onward the result is so huge that node.js just returns Infinity.

Now I know. 🙂

Leave a Reply

Your email address will not be published. Required fields are marked *