The '''Fibonacci sequence''' is a sequence &nbsp; <big> F<sub>n</sub> </big> &nbsp;  of natural numbers defined recursively: 

      <big><big> F<sub>0</sub> = 0 </big></big>
      <big><big> F<sub>1</sub> = 1 </big></big>
      <big><big> F<sub>n</sub> = F<sub>n-1</sub> + F<sub>n-2</sub> , if n > 1 </big></big>


;Task:
Write a function to generate the &nbsp; <big> n<sup>th</sup> </big> &nbsp; Fibonacci number. 

Solutions can be iterative, recursive (though recursive solutions are generally considered too slow and are mostly used as an exercise in recursion), or use [https://en.wikipedia.org/wiki/Fibonacci_sequence#Binet's_formula Binet's algebraic formula].

The sequence is sometimes extended for negative numbers by using an alternating inverse of the positive values. Rewriting the definition as

      <big><big> F<sub>n</sub> = F<sub>n+2</sub> - F<sub>n+1</sub> , if n < 0 </big></big>

leads to

      <big><big> F<sub>-n</sub> = (-1)<sup>n+1</sup> F<sub>n</sub> </big></big>.

Support for negative <big> n </big> in the solution is optional.


;Related tasks:
* &nbsp; [[Fibonacci n-step number sequences]]
* &nbsp; [[Leonardo numbers]]


;References:
* &nbsp; [[wp:Fibonacci number|Wikipedia, Fibonacci number]]
* &nbsp; [[wp:Lucas number|Wikipedia, Lucas number]]
* &nbsp; [http://mathworld.wolfram.com/FibonacciNumber.html MathWorld, Fibonacci Number]
* &nbsp; [http://www.math-cs.ucmo.edu/~curtisc/articles/howardcooper/genfib4.pdf Some identities for r-Fibonacci numbers]
* &nbsp; [[oeis:A000045|OEIS Fibonacci numbers]]
* &nbsp; [[oeis:A000032|OEIS Lucas numbers]]
<br><br>