37 lines
1.6 KiB
Text
37 lines
1.6 KiB
Text
The '''Fibonacci sequence''' is a sequence <big> F<sub>n</sub> </big> 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 <big> n<sup>th</sup> </big> 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:
|
|
* [[Fibonacci n-step number sequences]]
|
|
* [[Leonardo numbers]]
|
|
|
|
|
|
;References:
|
|
* [[wp:Fibonacci number|Wikipedia, Fibonacci number]]
|
|
* [[wp:Lucas number|Wikipedia, Lucas number]]
|
|
* [http://mathworld.wolfram.com/FibonacciNumber.html MathWorld, Fibonacci Number]
|
|
* [http://www.math-cs.ucmo.edu/~curtisc/articles/howardcooper/genfib4.pdf Some identities for r-Fibonacci numbers]
|
|
* [[oeis:A000045|OEIS Fibonacci numbers]]
|
|
* [[oeis:A000032|OEIS Lucas numbers]]
|
|
<br><br>
|
|
|