33 lines
1.4 KiB
Plaintext
33 lines
1.4 KiB
Plaintext
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 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:
|
||
|
||
<big><big> F<sub>n</sub> = F<sub>n+2</sub> - F<sub>n+1</sub>, if n<0 </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>
|