详解python使用递归、尾递归、循环三种方式实现斐波那契数列_使用递归斐波那契数列

145 浏览量更新于2023-05-11 评论收藏 77KB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源评论

资源推荐

详解详解python使用递归、尾递归、循环三种方式实现斐波那契数使用递归、尾递归、循环三种方式实现斐波那契数

列列

本篇文章主要介绍了python使用递归、尾递归、循环三种方式实现斐波那契数列，非常具有实用价值，需要的

朋友可以参考下

在最开始的时候所有的斐波那契代码都是使用递归的方式来写的，递归有很多的缺点，执行效率低下，浪费资源，还有可能会

造成栈溢出，而递归的程序的优点也是很明显的，就是结构层次很清晰，易于理解

可以使用循环的方式来取代递归，当然也可以使用尾递归的方式来实现。

尾递归就是从最后开始计算, 每递归一次就算出相应的结果, 也就是说, 函数调用出现在调用者函数的尾部, 因为是尾部, 所以根

本没有必要去保存任何局部变量. 直接让被调用的函数返回时越过调用者, 返回到调用者的调用者去。尾递归就是把当前的运算

结果（或路径）放在参数里传给下层函数，深层函数所面对的不是越来越简单的问题，而是越来越复杂的问题，因为参数里带

有前面若干步的运算路径。尾递归是极其重要的，不用尾递归，函数的堆栈耗用难以估量，需要保存很多中间函数的堆栈。直

接递归的程序中需要保存之前n步操作的所有状态极其耗费资源，而尾递归不需要，尾部递归是一种编程技巧。如果在递归函

数中，递归调用返回的结果总被直接返回，则称为尾部递归。尾部递归的函数有助将算法转化成函数编程语言，而且从编译器

角度来说，亦容易优化成为普通循环。这是因为从电脑的基本面来说，所有的循环都是利用重复移跳到代码的开头来实现的。

如果有尾部归递，就只需要叠套一个堆栈，因为电脑只需要将函数的参数改变再重新调用一次

为了加深对尾递归、递归和循环的对比，这里以斐波那契数列的实现举例：

#!usr/bin/env python

#encoding:utf-8

'''''''

__Author__:沂水寒城

功能：尾递归

'''

import time

def Fib_recursion(num):

'''''

直接使用递归法求解斐波那契数量的第num个数字

'''

if num<2:

return num

return Fib_recursion(num-1)+Fib_recursion(num-2)

def Fib_tail_recursion(num,res,temp):

'''''

使用尾递归法求解斐波那契数量的第num个数字

'''

if num==0:

return res

else:

return Fib_tail_recursion(num-1, temp, res+temp)

def Fib_circle(num):

'''''

直接使用循环来求解

'''

a=0

b=1

for i in range(1,num):

c=a+b

a=b

b=c

return c

if __name__ == '__main__':

num_list=[5,10,20,30,40,50]

for num in num_list:

start_time=time.time()

print Fib_recursion(num)

end_time=time.time()

print Fib_tail_recursion(num,0,1)

end_time2=time.time()

print Fib_circle(num)

end_time3=time.time()

print '正在求解的斐波那契数字下标为%s' %num

print '直接递归耗时为：', end_time-start_time

print '尾递归调用耗时为：', end_time2-end_time

print '直接使用循环耗时为：', end_time3-end_time2

结果如下：

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余1页未读，立即下载

weixin_38720762

粉丝: 5
资源: 943

会员权益专享

详解python使用递归、尾递归、循环三种方式实现斐波那契数列

评论0

会员权益专享

最新资源

详解python使用递归、尾递归、循环三种方式实现斐波那契数列

评论0

Labview实现递归：斐波那契数列

用循环算法求解斐波那契数列

python基础编程：详解python使用递归、尾递归、循环三种方式实现斐波那契数列

Python使用递归方法计算斐波那契数列详解

用python的递归数列实现斐波那契数列

python递归方法实现斐波那契数列

python递归数列斐波那契数列

斐波那契数列Python编程递归实现

斐波那契数列 python 递归

python 尾递归斐波那契数列

python斐波那契数列递归

python递归实现斐波那契数列

python尾递归计算斐波那契数列

python实现尾递归求解Fibonacci数列的方法

python编写递归函数和非递归函数、输出斐波那契数列_python 入门之斐波那契数列递归表达式算法和非递归算法...

python递归算法斐波那契数列

Python递归实现30项斐波那契数列

使用递归实现n个斐波那契数列。 使用递归实现n个斐波那契数列。 使用递归实现n个斐波那契数列。 使用递归实现n个斐波那契数列。 使用递归实现n个斐波那契数列。

使用python实现斐波那契数列

Python 使用递归斐波那契数列

会员权益专享

最新资源

使用递归实现n个斐波那契数列。使用递归实现n个斐波那契数列。使用递归实现n个斐波那契数列。使用递归实现n个斐波那契数列。使用递归实现n个斐波那契数列。