利用递归函数求斐波那契值python版

首先我们要了解一下什么是递归。

递归法，递归法就是利用上一个或者上几个状态来求取当前状态的值（个人看法）。也可以说成函数自己调用自己的一种解决问题的策略。因此递归法通常是依托函数来实现的，递归函数总是会有一个出口，我们在解决递归问题时，只需要找出递归的关系式以及递归函数的出口（这两个可以说是递归函数的核心了）。下面我将在这里举求斐波那契值的例子带领着大家具体的实践一下递归法。

很显然递归函数的递推式是：fib(n) = fib(n-1)+fib(n-2)。

递归函数的出口是当n为1时返回1，当n为0时返回0。

最后递归函数的核心代码就可以写出了：

然后总的代码就是：

具体思路如下：

语句 return fib(n-1)+fib(n-2)的意思就是向前求斐波那契值，直到n-1=1，n-2=0

因为只有第1个和第0个斐波那契值是确定的

例：

当n=3时

第一次调用函数fib会执行第三条语句（因为n>1)这样求回返回fib（2）+fib（1）

第二次调用函数时，因为2>1所有会返回fib（1）+fib（0）；因为1不大于1，所以调用函数时

会执行第二条语句返回1值。

第三次调用函数，会执行第一和第二条语句，依次返回0和1从而求得fib（2）

fib（3）=fib（2）+fib（1）

fib（2）=fib（1）+fib（0）

即fib（3）=fib（1）+fib（0）+fib（1）=2fib（1）+fib（0）

你看看你递归代码的复杂度 是O(2^n) 而第二个的复杂度是O(n) 运行效率当然不同COUNTER = 0
def fibn(n):
global COUNTER
COUNTER += 1
if n == 0:
return 1
elif n == 1:
return 1
else:
return fibn(n-1) + fibn(n-2)
statistics = []
for i in range(35):
COUNTER = 0
fibn(i + 1)
statisticsappend(((i + 1), COUNTER))
print statistics[(1, 1), (2, 3), (3, 5), (4, 9), (5, 15), (6, 25), (7, 41), (8, 67), (9, 109), (10, 177), (11, 287), (12, 465), (13, 753), (14, 1219), (15, 1973), (16, 3193), (17, 5167), (18, 8361), (19, 13529), (20, 21891), (21, 35421), (22, 57313), (23, 92735), (24, 150049), (25, 242785), (26, 392835), (27, 635621), (28, 1028457), (29, 1664079), (30, 2692537), (31, 4356617), (32, 7049155), (33, 11405773), (34, 18454929), (35, 29860703)]做了一个简单的proflieimport cProfile
import pstats
def fibn(n):
if n == 0:
return 1
elif n == 1:
return 1
else:
return fibn(n-1) + fibn(n-2)
print ' i, calls, time'
for i in range(50):
pr = cProfileProfile()
prenable()
fibn(i)
prdisable()
stats = pstatsStats(pr)
statsstrip_dirs()
st = statsstats[('test1py', 3, 'fibn')]
print '%3d, %10d, %8f' % (i, st[1], st[3])
i, calls, time 0, 1, 0000000 1, 1, 0000001 2, 3, 0000003 3, 5, 0000005 4, 9, 0000008 5, 15, 0000012 6, 25, 0000020 7, 41, 0000033 8, 67, 0000165 9, 109, 0000088 10, 177, 0000141 11, 287, 0000228 12, 465, 0000450 13, 753, 0000601 14, 1219, 0001016 15, 1973, 0003561 16, 3193, 0002593 17, 5167, 0004372 18, 8361, 0007097 19, 13529, 0011073 20, 21891, 0018552 21, 35421, 0032467 22, 57313, 0051762 23, 92735, 0095383 24, 150049, 0133490 25, 242785, 0212390 26, 392835, 0352861 27, 635621, 0578204 28, 1028457, 0987839 29, 1664079, 1506812 30, 2692537, 2682802 31, 4356617, 3998936 32, 7049155, 8089419 33, 11405773, 13058235 34, 18454929, 23930004 35, 29860703, 36503880目测fibn(50)要算出来需要两周

我举个例子：
①斐波那契数列：1，1，2，3，5，8，13，21，34
迭代：int Fib[N];
Fib[0]=1;Fib[1]=1;
for(i=2;i<N;i++)
Fib[i]=Fib[i-1]+Fib[i-2];
}
递归：int Fib(int n)
{ if(n==0||n==1)return 1;
else return (Fib(n-1)+Fib(n-2));
}

#include <stdioh>

int Fibonacci(int n)

{

if( n == 1 || n == 2) // 递归结束的条件，求前两项

return 1;

else

return Fibonacci(n-1)+Fibonacci(n-2); // 如果是求其它项，先要求出它前面两项，然后做和。

}

int main()

{

int n;

printf("please input n: ");

scanf("%d",&n);

printf("Result: %d\n",Fibonacci(n));

return 0;

}

在数学上，斐波纳契数列以如下被以递推的方法定义：F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n>=3，n∈N）在现代物理、准晶体结构、化学等领域，斐波纳契数列都有直接的应用。

扩展资料：

一个完全是自然数的数列，通项公式却是用无理数来表达的。而且当n趋向于无穷大时，前一项与后一项的比值越来越逼近黄金分割0618（或者说后一项与前一项的比值小数部分越来越逼近0618）。

从第二项开始，每个偶数项的平方都比前后两项之积少1，每个奇数项的平方都比前后两项之积多1。

如：第二项1的平方比它的前一项1和它的后一项2的积2少1，第三项2的平方比它的前一项1和它的后一项3的积3多1。

注：奇数项和偶数项是指项数的奇偶，而并不是指数列的数字本身的奇偶，比如从数列第二项1开始数，第4项5是奇数，但它是偶数项，如果认为5是奇数项，那就误解题意，怎么都说不通。

参考资料来源：百度百科--斐波那契数列

递归结束条件为：
fib(0)＝1
fib(1)＝1
递归函数值的计算为：
fib(2)＝fib(0)+fib(1)＝2
fib(3)＝fib(1)+fib(2)＝3
fib(4)＝fib(2)+fib(3)＝5
fib(5)＝fib(3)+fib(4)＝8
fib(6)＝fib(4)+fib(5)＝13
fib(7)＝fib(5)+fib(6)＝21

python根本就没有尾递归，scheme却有，所以scheme更有效率
尾递归的优势，是可以迭代，程序消耗的内存基本是恒定的
据我所知，尾递归不是大部分语言拥有的特性，C语言和lisp都用，连C++都没有，遑论其他语言了
chezscheme有很多优化选项，没开的话哪有优势？
尾递归，就是scheme相比python的一个绝对优势

---