The Fibonacci sequence is a sequence Fn of natural numbers defined recursively:
F0 = 0 F1 = 1 Fn = Fn-1 + Fn-2, if n>1
Write a function to generate the nth Fibonacci number. Solutions can be iterative or recursive (though recursive solutions are generally considered too slow and are mostly used as an exercise in recursion).
The sequence is sometimes extended into negative numbers by using a straightforward inverse of the positive definition:
Fn = Fn+2 - Fn+1, if n<0
Support for negative n in the solution is optional.
Using unsigned int, this version only works up to 48 before fib overflows.
This version does not have an upper bound.
Version using transform:
Far-fetched version using adjacent_difference:
Version which computes at compile time with metaprogramming:
The following version is based on fast exponentiation:
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181
Content is available under GNU Free Documentation License 1.2.