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 10^{30}, fib(fib(16)) is about 10^{206}, and from 17 onward the result is so huge that node.js just returns Infinity.

Now I know. ðŸ™‚