python递归求斐波那契数列(python递归斐波那契数列代码)
Python实现斐波那契数列的方法以及优化
斐波那契数列 （ 意大利语 ：Successione di Fibonacci） 的定义 ：
斐波那契数列由0和1开始，之后的每个斐波那契数就是由之前的两数相加而得出。具体数值如下：
0，1， 1， 2， 3， 5， 8， 13， 21， 34， 55， 89， 144， 233， 377， 610,..............
特别注意 ：F(0)代表的是第一个数值，数列下标由0开始。
代码如上，用了迭代的算法计算每个数值，每个N值最大运行N-1次循环，算法比递归要高效很多。递归代码如下：
Python实现斐波那契数列
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。
n=39
????????见到题目很自然联想到用递归或是用数组将前面的结果全部存储起来（这个想法其实和递归没区别），写起来最简单。但实际写出来发现不现实，运行效率太低，提交答案的时候果然提示超出要求时间，程序太过复杂。查阅答案的时候才发现一个很巧妙的方法（主要还是自己太笨了脑筋不会拐弯=.=||），其实F(n)=F(n-1)+F(n-2)，也就是说整个运算过程其实只用保存两个数值即可计算出所需结果，并不需要保存前面的全部结果。2个数值，就应该联想到通过模2来存取数值（写到这里愈发觉得自己是个猪头），这样大大提高了效率，降低了存储空间。
? ? ? ? 其次是在实现过程中要注意一个小问题，最开始本猪写的是 for i in range(2,n) ，后来发现答案全错了，原来是因为n=2时， range(2,2) 为0，并不会运算下面的值，所以需要多算一位。
# -*- coding:utf-8 -*-
class Solution:
? ? def __init__(self):
? ? ? ? self.temp_Array = [0,1]
? ? def Fibonacci(self, n):
? ? ? ? if type(n) != int or n = 0:
? ? ? ? ? ? return False
? ? ? ? elif n == 1:
? ? ? ? ? ? return 1
? ? ? ? else:
? ? ? ? ? ? for i in range(2,n+1):
? ? ? ? ? ? ? ? self.temp_Array[i%2] = self.temp_Array[0]+self.temp_Array[1]
? ? ? ? ? ? return self.temp_Array[n%2]
python中解 斐波那契数递推公式不能理解？
第一张图
def f(n):
if n==1 or n==2:
return 1
else:
return f(n-1)+f(n-2)
b=f(6)
print(b)
源代码(注意源代码的缩进)
第一张图是斐波那契数列的递归程序,其过程是
f(6)=f(5)+f(4)=f(4)+f(3)+f(3)+f(2)=f(3)+f(2)+f(2)+f(1)+f(2)+f(1)+f(2)
=f(2)+f(1)+f(2)+f(2)+f(1)+f(2)+f(1)+f(2)
因为f(2)=f(1)=1所以上式=1+1+1+1+1+1+1+1=8
第二张图
def fact(n):
if n==0:
return 1
else:
return n*fact(n-1)
b=fact(5)
print(b)
源代码(注意源代码的缩进)
第二张图是阶乘的递归程序,其过程是
fact(5)=5*fact(4)=5*4*fact(3)=5*4*3*fact(2)=5*4*3*2*fact(1)=5*4*3*2*1*fact(0)
因为fact(0)=1,所以上式=5*4*3*2*1*1=120
详细解释,
因为n等于5所以执行else语句返回5*fact(4)
n等于4所以执行else语句返回4*fact(3)
n等于3所以执行else语句返回3*fact(2)
n等于2所以执行else语句返回2*fact(1)
n等于1所以执行else语句返回1*fact(0)
n等于0所以执行if语句返回1
然后反向回归
fact(1)=1*1
fact(2)=2*1*1
fact(3)=3*2*1*1
fact(4)=4*3*2*1*1
fact(5)=5*4*3*2*1*1=120
python递归求斐波那契数列前10项
你好，很高兴为你解答。根据斐波那契数列F(n)=F(n-1)+F(n-2),当n=1和n=2时，F(n)=1，可以利用函数+if分支结构编写递归程序，求出斐波那契数列前10项。具体代码如下：
求斐波那契数列前10项