## 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. 🙂