The Fibonacci sequence is a sequence    Fn    of natural numbers defined recursively:

      F0 = 0 
      F1 = 1 
      Fn = Fn-1 + Fn-2, if n>1 



Task

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.



Related tasks

   Fibonacci n-step number sequences‎
   Leonardo numbers


References

   Wikipedia, Fibonacci number
   Wikipedia, Lucas number
   MathWorld, Fibonacci Number
   Some identities for r-Fibonacci numbers
   OEIS Fibonacci numbers
   OEIS Lucas numbers


IT'S SHOWTIME
 
HEY CHRISTMAS TREE f1
YOU SET US UP @I LIED
TALK TO THE HAND f1
 
HEY CHRISTMAS TREE f2
YOU SET US UP @NO PROBLEMO
 
HEY CHRISTMAS TREE f3
YOU SET US UP @I LIED
 
STICK AROUND @NO PROBLEMO
 
GET TO THE CHOPPER f3
HERE IS MY INVITATION f1
GET UP f2
ENOUGH TALK
TALK TO THE HAND f3
 
GET TO THE CHOPPER f1
HERE IS MY INVITATION f2
ENOUGH TALK
 
GET TO THE CHOPPER f2
HERE IS MY INVITATION f3
ENOUGH TALK
 
CHILL
 
YOU HAVE BEEN TERMINATED