遞歸的方法定義：? F0=0，

? ? ? ? ? ? ? ? ? ? ? ? ? F1=1，

? ? ? ? ? ? ? ? ? ? ? ? ? Fn=F(n-1)+F(n-2)（n>=2，n∈N*）

1、1、2、3、5、8、13、21、……

所謂Fibonacci數(shù)列是指這樣一種數(shù)列，它的前兩項均為1，從第三項開始各項均為前兩項之和。用數(shù)學(xué)公式表示出來就是：
?????????? 1 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? (n=1,2)
? ? ? ? ? ?fib(n)=?fib(n-1)+fib(n-2) ? ? ? (n > 2 )

1.遞歸法
這種方法的優(yōu)點是簡潔和容易理解，缺點是時間復(fù)雜度太大，隨著n的增大，運算時間將會急劇增加。因此在很多場合這種方法是不可取的。
使用這種方法的關(guān)鍵代碼是：

int fib(int n)

{

? ? if(n == 1|| n== 2)
? ? {
? ? ? ? ?return 1;
? ? }
? ? else
? ? {
? ? ? ? ?return fib(n - 1) + fib(n - 2);
? ? }

}

?

2.迭代法
這種方法相對于遞歸法來說在時間復(fù)雜度上減小了不少，但代碼相對就要復(fù)雜些了。它的思想是這樣的，假設(shè)開始時f0=1,f1=1,

currentFib表示當前斐波那契數(shù)，則：

int fib(int n)

{

? ? for(i = 1;i < n;i++)
? ? {
? ? ? ? ?currentFib = f0 + f1;
? ? ? ? ?f0 = f1;
? ? ? ? ?f1 = currentFib;
? ? }

? ? return?currentFib;

}
這樣迭代結(jié)束和currentFib就是fib(n)了。

3.總結(jié)

遞歸法有很多重復(fù)運算，而迭代法由于每次都保存了前兩個數(shù)的值，不存在重復(fù)運算，所以效率高！

轉(zhuǎn)載于:https://www.cnblogs.com/wufengv5/archive/2013/06/11/3131810.html

總結(jié)

以上是生活随笔為你收集整理的斐波纳契数列递归和非递归算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。