查看“斐波那契数列”的源代码

{{refimprove|time=2014-03-25T08:24:56+00:00}}
{{NoteTA|G1=Math
|1=zh-cn:程序; zh-tw:程式;}}[[File:34*21-FibonacciBlocks.png|thumb|400px|以斐波那契數為邊的正方形拼成的近似的[[黃金矩形]](1:1.618)]]

'''-{zh-hant:斐波那契數列;zh-hans:斐波那契数列}-'''（[[意大利语]]：Successione di Fibonacci），又譯為'''菲波拿契數列'''、'''菲波那西數列'''、'''斐氏數列'''、'''黃金分割數列'''。

在[[數學]]上，'''斐波那契數列'''是以[[遞歸]]的方法來定義：

*<math>F_0=0</math>
*<math>F_1=1</math>
*<math>F_n = F_{n-1}+ F_{n-2}</math>（n≧2）

用文字來說，就是斐波那契數列由0和1開始，之後的斐波那契系數就是由之前的兩數相加而得出。首幾個斐波那契系數是：

[[0]], [[1]], [[1]], [[2]], [[3]], [[5]], [[8]], [[13]], [[21]], [[34]], [[55]], [[89]], [[144]], [[233]]……{{OEIS|id=A000045}}

'''特別指出'''：[[0]]不是第一項，而是第零項。

==源起==
根據[[高德納]]（Donald Ervin Knuth）的《[[計算機程序設計藝術]]》（''The Art of Computer Programming''），1150年[[印度]][[數學家]][[Gopala]]和[[金月]]在研究[[箱子包裝問題|箱子包裝]]物件長宽剛好為1和2的可行方法數目時，首先描述這個數列。在西方，最先研究這個數列的人是[[比薩的李奧納多]]（義大利人斐波那契Leonardo Fibonacci），他描述[[兔子]]生長的數目時用上了這數列:
[[File:FibonacciRabbit.svg|thumb|300px|兔子对的数量就是斐波那契数列]]
*第一個月初有一對剛誕生的兔子
*第二個月之後（第三個月初）牠們可以生育
*每月每對可生育的兔子會誕生下一對新兔子
*兔子永不死去
假設在n月有兔子總共a對，n+1月總共有b對。在n+2月必定總共有a+b對：因為在n+2月的時候，前一月（n+1月）的b對兔子可以存留至第n+2月（在當月屬於新誕生的兔子尚不能生育）。而新生育出的兔子對數等於所有在n月就已存在的a對
[[File:PascalTriangleFibanacci.svg|thumb|300px|斐波纳契数是[[帕斯卡三角形]]的每一条红色对角线上数字的和。]]
斐波纳契数也是[[帕斯卡三角形]]的每一条红色对角线上数字的和。

==表達式==
為求得斐波那契數列的一般表達式，可以藉助線性代數的方法。高中的初等數學知識也能求出。
===初等代數解法===
已知
*<math>a_1=1</math>
*<math>a_2=1</math>
*<math>a_n = a_{n-1}+ a_{n-2}</math>

====首先構建等比數列====
設<math>a_n +\alpha a_{n-1}=\beta (a_{n-1}+\alpha  a_{n-2})</math><br />化簡得<br /><math>a_n=(\beta -\alpha) a_{n-1}+ \alpha\beta a_{n-2}</math><br />
比較係數可得：<br />
<math> \begin{cases}
\beta-\alpha=1 \\
\alpha\beta=1
\end{cases}</math>
<br />不妨設<math>\beta>0,  \alpha>0</math><br />
解得：<br />

<math> \begin{cases}
\alpha=\dfrac{\sqrt{5}-1}{2} \\
\beta=\dfrac{\sqrt{5}+1}{2}
\end{cases}</math>
<br />
又因为有<math>a_n +\alpha a_{n-1}=\beta (a_{n-1}+\alpha  a_{n-2})</math>，
即<math>\left\{a_n +\alpha a_{n-1}\right\}</math>為等比數列。

====求出數列{<math>a_n +\alpha a_{n-1}</math>}====
由以上可得：<br />
<math>\begin{align}a_{n+1} +\alpha a_{n} &=(a_2+\alpha a_1)\beta^{n-1}\\
& = (1+\alpha)\beta^{n-1}\\
& =\beta^n \\
\end{align}
</math><br />

變形得：
<math>\frac{a_{n+1}}{\beta^{n+1}}+\frac{\alpha}{\beta}\cdot\frac{a_{n}}{\beta^{n}}=\frac{1}{\beta}</math>。
令<math>b_n=\frac{a_n}{\beta^n}</math>

==== 求數列{<math>b_n</math>}進而得到{<math>a_n</math>}====
<math>b_{n+1}+\frac{\alpha}{\beta}b_{n}=\frac{1}{\beta}</math><br />
設<math>b_{n+1}+\lambda=-\frac{\alpha}{\beta} (b_{n}+\lambda)</math>，解得<math>\lambda=-\frac{1}{\alpha+\beta}</math>。
故數列<math>\left\{b_n+\lambda\right\}</math>為等比數列<br />
即<math>b_n+\lambda=\left(-\frac{\alpha}{\beta}\right)^{n-1}\left(b_1+\lambda\right)</math>。而<math>b_1=\frac{a_1}{\beta}=\frac{1}{\beta}</math>，
故有<math>b_n+\lambda=\left(-\frac{\alpha}{\beta}\right)^{n-1}\left(\frac{1}{\beta}+\lambda\right)</math><br />
又有<math> \begin{cases}
\alpha=\dfrac{\sqrt{5}-1}{2} \\
\beta=\dfrac{\sqrt{5}+1}{2}
\end{cases}</math>
和<math>b_n=\frac{a_n}{\beta^n}</math><br />
可得<math>a_{n}=\frac{\sqrt{5}}{5} \cdot \left[\left(\frac{1 + \sqrt{5}}{2}\right)^{n} - \left(\frac{1 - \sqrt{5}}{2}\right)^{n}\right]</math>

得出<math>{a_n}</math>表達式<br />

<math>a_{n}=\frac{\sqrt{5}}{5} \cdot \left[\left(\frac{1 + \sqrt{5}}{2}\right)^{n} - \left(\frac{1 - \sqrt{5}}{2}\right)^{n}\right]</math>

===線性代數解法===
<math>
\begin{pmatrix} F_{n+2} \\ F_{n+1} \end{pmatrix}
=
\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \cdot \begin{pmatrix} F_{n+1} \\ F_{n} \end{pmatrix}
</math>

<math>
\begin{pmatrix} F_{n+2} & F_{n+1} \\ F_{n+1} & F_{n} \end{pmatrix}
=
\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^{n + 1}
</math>
====構建一個矩陣方程====

設J<sub>n</sub>為第n個月有生育能力的兔子數量，A<sub>n</sub>為這一月份的兔子數量。

:<math>{J_{n+1}\choose A_{n+1}} = \begin{pmatrix}0&1\\1&1\end{pmatrix} \cdot {J_n\choose A_{n}},</math>

上式表達了兩個月之間，兔子數目之間的關係。而要求的是，A<sub>n+1</sub>的表達式。

====求矩陣的[[特徵值]]：<math> \lambda </math>====

行列式：<math>-\lambda(1-\lambda)-1\times1=\lambda^2-\lambda-1</math>

當行列式的值為0，解得<math> \lambda_1 </math>=<math>\frac{1}{2} (1 + \sqrt{5})</math>或<math> \lambda_2 </math>=<math>\frac{1}{2} (1 - \sqrt{5})</math>

====[[特徵向量]]====
將兩個特徵值代入

: <math>(\begin{pmatrix}0&1\\1&1\end{pmatrix}-\lambda \cdot E) \cdot\vec x = 0</math> 


求特徵向量<math>\vec x</math>得

<math>\vec x_1</math>=<math>\begin{pmatrix} 1\\\frac{1}{2} (1 + \sqrt{5})\end{pmatrix}</math>

<math>\vec x_2</math>=<math>\begin{pmatrix} 1\\\frac{1}{2} (1 - \sqrt{5})\end{pmatrix}</math>

====分解首向量====
第一個月的情況是兔子一對，新生0對。

:<math>{J_{1}\choose A_{1}} = \begin{pmatrix}0\\1\end{pmatrix}</math>

將它分解為用特徵向量表示。

:<math>\begin{pmatrix}0\\1\end{pmatrix}=\frac{1}{\sqrt{5}} \cdot \begin{pmatrix}1\\\frac{1}{2} (1 + \sqrt{5})\end{pmatrix}-\frac{1}{\sqrt{5}} \cdot \begin{pmatrix}1\\\frac{1}{2} (1 - \sqrt{5})\end{pmatrix}</math>  （4）

====用[[數學歸納法]]證明====

從
:<math>{J_{n+1}\choose A_{n+1}} = \begin{pmatrix}0&1\\1&1\end{pmatrix}

 \cdot {J_n\choose A_{n}}</math>=<math>\lambda \cdot {J_n\choose A_{n}}</math>

可得到

:<math>{J_{n+1}\choose A_{n+1}} = \begin{pmatrix}0&1\\1&1\end{pmatrix}^n \cdot {J_{1}\choose A_{1}} =\lambda^n \cdot {J_{1}\choose A_{1}}</math>  （5）

====化簡矩陣方程====

將（4） 代入 （5）

:<math>{J_{n+1}\choose A_{n+1}} = \lambda^n \cdot \left[\frac{1}{\sqrt{5}} \cdot \begin{pmatrix}1\\\frac{1}{2} (1 + \sqrt{5})\end{pmatrix}-\frac{1}{\sqrt{5}} \cdot \begin{pmatrix}1\\\frac{1}{2} (1 - \sqrt{5})\end{pmatrix}\right]</math>

根據3
:<math>{J_{n+1}\choose A_{n+1}} = \frac{1}{\sqrt{5}} \cdot \lambda_1^n \cdot \begin{pmatrix}1\\\frac{1}{2} (1 + \sqrt{5})\end{pmatrix}- \frac{1}{\sqrt{5}} \cdot  \lambda_2^n\cdot \begin{pmatrix}1\\\frac{1}{2} (1 - \sqrt{5})\end{pmatrix}</math>

====求A的表達式====
現在在6的基礎上，可以很快求出A<sub>n+1</sub>的表達式，將兩個特徵值代入6中

:<math>A_{n+1}=\frac{1}{\sqrt{5}} \cdot \lambda_1^{n+1} - \frac{1}{\sqrt{5}} \cdot \lambda_2^{n+1}</math>

:<math>A_{n+1}=\frac{1}{\sqrt{5}} \cdot (\lambda_1^{n+1} -  \lambda_2^{n+1})</math>

:<math>A_{n+1}=\frac{1}{\sqrt{5}} \cdot \left\{\left[\frac{1}{2} \left(1 + \sqrt{5}\right)\right]^{n+1} -  \left[\frac{1}{2} (1 - \sqrt{5})\right]^{n+1}\right\}</math>（7）

（7）即為A<sub>n+1</sub>的表達式

=== 數論解法 ===
實際上，如果將斐波那契數列的通項公式寫成<math>a_n-a_{n-1}-a_{n-2}=0</math>，即可利用解二階線性齊次遞迴關係式的方法，寫出其特徵多項式<math>\lambda^2-\lambda-1=0</math>（該式和表達斐波那契數列的矩陣的特徵多項式一致），然後解出<math> \lambda_1 </math>=<math>\frac{1}{2} (1 + \sqrt{5})</math>，<math> \lambda_2 </math>=<math>\frac{1}{2} (1 - \sqrt{5})</math>，即有<math>a_n=c_1\lambda_1^n+c_2\lambda_2^n</math>，其中<math>c_1,c_2</math>为常数。我们知道<math>a_0=0,a_1=1</math>，因此<math>    \begin{cases} c_1+c_2=0 \\ \frac{c_1(1+\sqrt{5})}{2} +\frac{c_2(1-\sqrt{5})} {2}=1\end{cases}</math>，解得<math>c_1=\frac{1}{\sqrt{5}},c_2=-\frac{1}{\sqrt{5}}</math>。

===組合數解法===
<math> F_n=\sum_{i=0}^{\infty} \binom {n-i}{i}</math><ref>{{cite web|url=http://www.cnki.com.cn/Article/CJFDTotal-ZXJI199110005.htm|title=斐波那契数列与组合数的一个关系及推广}}</ref>
: <math> F_{n-1}+F_n=\sum_{i=0}^{\infty} \binom {n-1-i}{i}+\sum_{i=0}^{\infty} \binom {n-i}{i}=1+\sum_{i=1}^{\infty} \binom {n-i}{i-1}+\sum_{i=1}^{\infty} \binom {n-i}{i}=1+\sum_{i=1}^{\infty} \binom {n+1-i}{i}=\sum_{i=0}^{\infty} \binom {n+1-i}{i}=F_{n+1}</math>

===近似值===
:<math>F_n \approx \frac{1}{\sqrt{5}} a^n = \frac{1}{\sqrt{5}} \cdot \left[ \frac{1}{2} \left(1 + \sqrt{5}\right) \right]^n \approx 0.4472135955 \cdot 1.618033988745^n </math>

===用計算機求解===
可通過編程觀察斐波那契數列。分為兩類問題，一種已知數列中的某一項，求序數。第二種是已知序數，求該項的值。

可通過[[遞歸]][[遞推]]的算法解決此兩個問題。
事實上當n相當巨大的時候，O（n）的遞推/遞歸非常慢……這時候要用到矩陣快速幂這一技巧，可以使遞迴加速到O(logn)。

==和黃金分割的關係==
[[開普勒]]發現數列前、後兩項之比1/2 ,2/3 , 3/5 ,5/8 ,8/13 ,13/21 ,21/34 ,...... ,也組成了一個數列，會趨近[[黃金分割]]：

:<math>\frac {f_{n+1}}{f_n} \approx a = \frac{1}{2} (1 + \sqrt{5}) = \varphi \approx 1{.}618{...}</math>

斐波那契數亦可以用[[連分數]]來表示：

<math>\frac{1}{1} = 1 \qquad \frac{2}{1} = 1+\frac{1}{1} \qquad \frac{3}{2} = 1+\frac{1}{1+ \frac{1}{1}} \qquad \frac{5}{3} = 1+\frac{1}{1+ \frac{1}{1+ \frac{1}{1}}} \qquad \frac{8}{5} = 1+\frac{1}{1+ \frac{1}{1+ \frac{1}{1+ \frac{1}{1}}}}</math>

<math>F_n = \frac{1}{\sqrt{5}} \left[ \left( \frac{1+\sqrt{5}}{2} \right)^n -  \left( \frac{1-\sqrt{5}}{2} \right)^n \right] = {\varphi^n \over \sqrt{5}} - {(1-\varphi)^n \over \sqrt{5}}</math>

而黃金分割數亦可以用無限連分數表示：
:<math>\varphi = 1+\frac{1}{1+ \frac{1}{1+ \frac{1}{1+ \frac{1}{1+ ...}}}}</math>
而黃金分割數也可以用無限多重根號表示：
:<math>\varphi=\sqrt{1+\sqrt{1+\sqrt{1+\sqrt{1+...}}}}</math>

==與平方數的關係==
斐波那契数列中，只有3個[[平方數]]：[[0]]、[[1]]、[[144]]。<ref>{{cite web|author=JOHN H. E. COHN|title=Square Fibonacci Numbers, Etc.|url=https://math.la.asu.edu/~checkman/SquareFibonacci.html|publisher=Bedford College, University of London, London, N.W.1.|archiveurl=https://archive.is/GZGI|archivedate=2012-06-30|quote=<u>Theorem 3.</u> If F<sub>n</sub> = x<sup>2</sup>, then n = 0, ±1, 2 or 12.}}</ref>

==和自然的關係==
{{citation needed|許多的[[生物]]構成都和斐波那契數列有[[正相關]]。例如[[人體]]從[[脚底]]至頭頂之[[距離]]和從[[肚臍]]至腳底之距[[趨近]]於<math>\lim_{n \to \infty}\frac{F_n}{F_{(n-1)}}</math>
,[[向日葵]]的[[種子]][[螺旋排列]]有99%是

==恆等式==
<small>資料來源：</small><ref name="性質整理">{{cite web|url=http://www.shs.edu.tw/works/essay/2014/03/2014032310331517.pdf|author=李晨滔、馮勁敏|title=費氏數列的性質整理|publisher=桃園縣立大園國際高中}}</ref>

證明以下的恆等式有很多方法。以下會用[[組合論述]]來證明。
* <math>F_n</math>可以表示用多個1和多個2相加令其和等於<math>n</math>的方法的數目。
[[不失一般性]]，我們假設<math>n\geq1</math>，<math>F_{n+1}</math>是計算了將1和2加到n的方法的數目。若第一個被加數是1，有<math>F_n</math>種方法來完成對<math>n-1</math>的計算；若第一個被加數是2，有<math>F_{n-1}</math>來完成對<math>n-2</math>的計算。因此，共有<math>F_n + F_{n-1}</math>種方法來計算n的值。
* <math>F_0 + F_1 + F_2 + F_3 + ... + F_n = F_{n+2} - 1 </math>
計算用多個1和多個2相加令其和等於<math>n+1</math>的方法的數目，同時至少一個加數是2的情況。

如前所述，當<math>n>0</math>，有<math>F_{n+2}</math>種這樣的方法。因為當中只有一種方法不用使用2，就即<math>1+1+...+1</math>　（<math>n+1</math>項），於是我們從<math>F_{n+2}</math>減去1。

#若第1個被加數是2，有<math>F_n</math>種方法來計算加至<math>n-1</math>的方法的數目；
#若第2個被加數是2、第1個被加數是1，有<math>F_{n-1}</math>種方法來計算加至<math>n-2</math>的方法的數目。
#重複以上動作。
#若第<math>n+1</math>個被加數為2，它之前的被加數均為1，就有<math>F_{0}</math>種方法來計算加至0的數目。

若該數式包含2為被加數，2的首次出現位置必然在第1和<math>n+1</math>的被加數之間。2在不同位置的情況都考慮到後，得出<math>F_n + F_{n-1} + ... + F_0</math>為要求的數目。

*<math>F_1 + 2 F_2 + 3 F_3 + ... + n F_n = n F_{n + 2} - F_{n + 3} + 2</math> 

*<math>F_1 + F_3 + F_5 + ... + F_{2n-1} = F_{2n}</math>
*<math>F_2 + F_4 + F_6 + ... + F_{2n} = F_{2n+1} - 1</math>
*<math>{F_1}^2 + {F_2}^2 + {F_3}^2 + ... + {F_n}^2 = F_n F_{n+1}</math>
*<math>F_{n-1} F_{n+1} - {F_n}^2 = (-1)^n</math>

==定理==
<small>資料來源：</small><ref name="性質整理"/>

:<math>\begin{align}
 {F_m}{F_n} + {F_{m-1}}{F_{n-1}} &= F_{m+n-1}\\
 F_{m} F_{n+1} + F_{m-1} F_n &= F_{m+n}
\end{align}</math>
特別地，當''m'' = ''n''時，
:<math>\begin{align}
 F_{2n-1} &= F_n^2 + F_{n-1}^2\\
 F_{2n}   &= (F_{n-1}+F_{n+1})F_n\\
          &= (2F_{n-1}+F_n)F_n
\end{align}</math>
*<math>F_n</math>整除<math>F_m</math>，若且唯若''n''整除''m''，其中''n''≧3。
*<math>\gcd(F_m,F_n)=F_{\gcd(m,n)}</math>
*任意連續三個菲波那契數兩兩[[互質]]，亦即，對於每一個''n''，
:[[最大公因數|gcd]](''F''<sub>''n''</sub>, ''F''<sub>''n''+1</sub>) = gcd(''F''<sub>''n''</sub>, ''F''<sub>''n''+2</sub>) = gcd(''F''<sub>''n''+1</sub>, ''F''<sub>''n''+2</sub>) = 1

==相關的數列==
費波那西數列是[[費波那西n步數列]]步數為2的特殊情況，也和[[盧卡斯數]]列有關。
===和盧卡斯數列的關係===
:<math>F_nL_n=F_{2n}</math>
===反費波那西數列===
反費波那西數列的遞歸公式如下：
:<math>G_{n+2} = G_{n} - G_{n+1}</math>

如果它以1,-1，之後的數是：1,-1,2,-3,5,-8, ...

即是<math>F_{2n+1} = G_{2n+1}, F_{2n} = - G_{2n}</math>。

反費波那西數列兩項之間的比會趨近<math>-\frac{1}{\varphi}=-0.618</math>。

===巴都萬數列===
費波那西數列可以用一個接一個的正方形來表現，[[巴都萬數列]]則是用一個接一個的等邊三角形來表現，它有<math>P_{n} = P_{n-2} + P_{n-3}</math>的關係。

===佩爾數列===

[[佩爾數列]]的遞歸公式為<math>P_{n} = 2P_{n-1} + P_{n-2}</math>，前幾項為0,1,2,5,12,29,70,169,408,...

==應用==
1970年，[[尤裏·馬季亞謝維奇]]指出了偶角標的斐波那契函數
:<math> y = F_{2x}</math>
正是滿足Julia Robison假設的[[丟番圖函數]]，因而證明了[[希爾伯特第十問題]]是不可解的。
==相關猜想==
斐波那契數列中是否存在無窮多個質數？

在斐波那契數列中，有質數：
2, 3, 5, 13, 89, 233, 1597, 28657, 514229, 433494437, 2971215073, 99194853094755497, 1066340417491710595814572169, 19134702400093278081449423917……
目前已知最大質數是第81839個斐波那契數，一共有17103位數。

==程式參考==
[[JavaScript]][[迭代]]版
<source lang="javascript">
function fib(n) {
    var fib_n = function(curr, next, n) {
        if (n == 0) {
            return curr;
        }
        else {
            return fib_n(next, curr+next, n-1);
        }
    }
    return fib_n(0, 1, n);
}
alert(fib(40));
</source>

[[C语言]][[通项公式]]版
<source lang="c">
#include <stdio.h>
#include <math.h>

int main()
{
    int n;
    double constant_a = (1 + sqrt(5)) / 2;
    double constant_b = (1 - sqrt(5)) / 2;
    double constant_c = sqrt(5) / 5;
    double value_1 = 0;
    int value_2 = 0;
    scanf("%d", &n);
    if(n > 0)
    {
        for (int i = 0; i < n; i++)
        {
             value_1 = constant_c * (pow(constant_a, i) - pow(constant_b, i));
             value_2 = (int)value_1;
             printf("%d\n", value_2);
        }
        return 0;
    }
    else
    {
        return -1;
    }
}
</source>

c++通项公式版<syntaxhighlight lang="c++">
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
    unsigned long long n;
    double ca = (1 + sqrt(5)) / 2;
    double cb = (1 - sqrt(5)) / 2;
    double cc = sqrt(5) / 5;
    double v1 = 0;
    double v2 = 0;
    cout <<" ";
    cin>>n;
    if(n > 0)
    {
        for (unsigned long long i = 0; i < n; i++)
    {
            v1 = cc * (pow(ca, i) - pow(cb, i));
        v2 = (int)v1;
        cout <<v2<<endl;
    }
    return 0;
    }
    else
    {
        return -1;
    }
        cout <<'/b';
}
</syntaxhighlight>[[Python语言]][[通项公式]]版<syntaxhighlight lang="python">
# Fibonacci numbers module

def fib(n):    # write Fibonacci series up to n
    a, b = 0, 1
    while b < n:
        print(b, end=' ')
        a, b = b, a+b
    print()

def fib2(n):   # return Fibonacci series up to n
    result = []
    a, b = 0, 1
    while b < n:
        result.append(b)
        a, b = b, a+b
    return result
</syntaxhighlight>
<source lang="Python">
fibs = [0, 1]
numZS = int(input('How many Fibonacci numbers do you want? '))
for i in range(numZS-2):
    fibs.append(fibs[-2] + fibs[-1])
print fibs
</source>

Common Lisp
<source lang="Lisp">
(defun fibs (x)
  (cond ((equal x 0) 1)
        ((equal x 1) 1)
        (t (+ (fibs (- x 1))
              (fibs (- x 2))))))

(defun fibs (x)
  (do ((n 0 (+ n 1))
       (i 1 j)
       (j 1 (+ i j)))
      ((equal n x) i)))
</source>

[[Go]]语言通项公式版：
<source lang="Go">
package main

import "fmt"

func fibonacci(n int) int {
	if n < 2 {
		return n
	}
	return fibonacci(n-2) + fibonacci(n-1)
}

func main() {
	var i int
	for i = 0; i < 10; i++ {
		fmt.Printf("%d\t", fibonacci(i))
	}
}
</source>

[[Java]]语言通项公式版：
<source lang="java">
public int fibonacci(int n){
    if(n<2){
     return n;
    }else {
      return fibonacci(n-1)+fibonacci(n-2);
    }
}
</source>

[[Java]]语言快捷版：
<source lang="java">
public int fibonacci(int n){
    if(n<2){
     return n;
    }else {
      int[] ans = new int[n];
          ans[0] = 1;
          ans[1] = 2;
          for(int i=2;i<n;i++) {
              ans[i]=ans[i-1]+ans[i-2];
          }
          return ans[n-1];
    }
}
</source>
[[C]]语言陣列版：
<source lang='C'>
#include <stdio.h>
#include <stdlib.h> 
int main()
{   
     int n,s,L;
     printf("輸入長度");
     scanf("%d",&L);
     while(L<0)
     {
     	printf("錯誤"); 
     	return 0;
	 }
     int a[L]; 
     int x=1,y=2;
     a[0]=x;
     a[1]=x;
     a[2]=y;
	 for(n=3;n<L;n++)
	 {  
		 a[n]=a[n-1]+a[n-2];  	
	 }
       for(n=0;n<L;n++)
     {
         printf("%d ",a[n]);
     }
     system("pause");
     return 0;
}
</source>

== 參考文獻 ==
* [[高德納|KNUTH, D. E.]] 1997. The Art of Computer ProgrammingArt of Computer Programming, Volume 1: Fundamental Algorithms, Third Edition. Addison-Wesley. Chapter 1.2.8.
* Arakelian, Hrant (2014). ''Mathematics and History of the Golden Section''. Logos, 404 p. ISBN 978-5-98704-663-0, (rus.)
* 克裏福德A皮科夫.數學之戀.湖南科技出版社.
<references/>

==參見==
*[[齊肯多夫定理]]

==外部連結==
*[http://www.hytc.cn/xsjl/szh/lec5.pdf 費波那契數，孫智宏（pdf）]

{{Template:級數}}

{{Authority control}}
[[Category:整數數列|Fibonacci]]