# Fibonacci in Ruby

Fibonacci is a common interview question and here let me share some solutions to save you time to do the research.

The obvious solution is recursion from the definition:

```def fib(n)
return 1 if n <= 1

fib(n-1) + fib(n-2)
end
```

This quickly stops working for `fib(40)`. But we can introduce cache:

```Cache = {}
def fib(n)
Cache[n] ||= begin
return 1 if n <= 1

fib(n-1) + fib(n-2)
end
end
```

But this solution does not work for `fib(10000)`. `SystemStackError: stack level too deep`...There is a limit of how many method calls can be pushed on the stack.

But we could rewrite the recursion into iterator.

```def fib(n)
a, b = 0, 1
n.times do
a, b = b, a + b
end
a
end
```

But this stops working when we hit `fib(1000000)`. Then we can use a solution called Matrix Exponentiation.

```require "matrix"

def fib(n)
matrix = Matrix[[1,1], [1,0]]
(matrix ** n)[0, 0]
end
```

But this solution does not work for `fib(100000000)`. There is a technique called fast doubling:

```def fib(n)
_fib(n)[0]
end

def _fib(n)
return [0, 1] if n == 0

a, b = _fib(n / 2)
c = a * (b * 2 - a)
d = a * a + b * b

if n % 2 == 0
[c, d]
else
[d, c+d]
end
end
```

`fib(100000000)` takes about 1.565 seconds.

But `fib(10000000000)` stops working.....