详解python使用递归、尾递归、循环三种方式实现斐波那契数列
作者:Together_CZ 发布时间:2022-06-22 13:44:49
在最开始的时候所有的斐波那契代码都是使用递归的方式来写的,递归有很多的缺点,执行效率低下,浪费资源,还有可能会造成栈溢出,而递归的程序的优点也是很明显的,就是结构层次很清晰,易于理解
可以使用循环的方式来取代递归,当然也可以使用尾递归的方式来实现。
尾递归就是从最后开始计算, 每递归一次就算出相应的结果, 也就是说, 函数调用出现在调用者函数的尾部, 因为是尾部, 所以根本没有必要去保存任何局部变量. 直接让被调用的函数返回时越过调用者, 返回到调用者的调用者去。尾递归就是把当前的运算结果(或路径)放在参数里传给下层函数,深层函数所面对的不是越来越简单的问题,而是越来越复杂的问题,因为参数里带有前面若干步的运算路径。尾递归是极其重要的,不用尾递归,函数的堆栈耗用难以估量,需要保存很多中间函数的堆栈。直接递归的程序中需要保存之前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
结果如下:
5
5
5
正在求解的斐波那契数字下标为5
直接递归耗时为 : 6.38961791992e-05
尾递归调用耗时为: 2.31266021729e-05
直接使用循环耗时为: 1.97887420654e-05
55
55
55
正在求解的斐波那契数字下标为10
直接递归耗时为 : 6.60419464111e-05
尾递归调用耗时为: 3.31401824951e-05
直接使用循环耗时为: 1.8835067749e-05
6765
6765
6765
正在求解的斐波那契数字下标为20
直接递归耗时为 : 0.00564002990723
尾递归调用耗时为: 3.09944152832e-05
直接使用循环耗时为: 2.09808349609e-05
832040
832040
832040
正在求解的斐波那契数字下标为30
直接递归耗时为 : 0.39971113205
尾递归调用耗时为: 1.69277191162e-05
直接使用循环耗时为: 1.19209289551e-05
102334155
102334155
102334155
正在求解的斐波那契数字下标为40
直接递归耗时为 : 39.0365440845
尾递归调用耗时为: 2.19345092773e-05
直接使用循环耗时为: 1.78813934326e-05
12586269025
12586269025
12586269025
正在求解的斐波那契数字下标为50
直接递归耗时为 : 4915.68643498
尾递归调用耗时为: 2.19345092773e-05
直接使用循环耗时为: 2.09808349609e-05
画图图表更加清晰地可以看到差距:
因为差距太大,导致尾递归和循环的两种方式的时间增长几乎是水平线,而直接递归的时间增长接近90度。
这一次,感觉自己好有耐心,一直就在那里等着程序出结果,可以看到三者的时间对比状况,很明显的:直接递归的时间增长的极快,而循环的性能还要优于尾递归,这就告诉我们尽量减少递归的使用,使用循环的方式代替递归无疑是一种提高程序运行效率的方式。
来源:http://blog.csdn.net/Together_CZ/article/details/76216239
猜你喜欢
- 最近学了一点点python爬虫的知识,面向百度编程爬了一本小说之后感觉有点不满足,于是突发奇想尝试爬一本漫画下来看看。一、效果展示首先是我们
- 在pyplot模块中可以使用xlabel()和ylabel()函数设置x轴y轴的标签。这两个函数的使用方法非常相似。使用xlabel()设置
- json和dictpython中的dict类型要转换为json格式的数据需要用到json库:import json <json>
- ORCLE数据库备份策略 1.通过使用exp和imp命令实现数据库导出和导入。 有三种模式: a. 用户模式: 导出(导入)用户所有对象以及
- 看了下传统的方法,觉得不好,太麻烦。自己重写了个,思路比较新。这个函数的优点是html代码可以很简洁,使用图片也可以很少,只需要两张图片。事
- 有这么一个题目,说bt其实也不bt,为了重点突出其中的意图,特意加上了括号:var a = (++Math.P
- Cookies,有些人喜欢它们,有些人憎恨它们。但是,很少有人真正知道如何使用它们。现在你可以成为少数人中的成员-可以自傲的Cookie 大
- 前言支持向量机 (Support Vector Machine, SVM) 是一种监督学习技术,它通过根据指定的类对训练数据进行最佳分离,从
- 本文实例讲述了CentOS环境下安装Redis3.0及phpredis扩展测试。分享给大家供大家参考,具体如下:线上的统一聊天及推送系统re
- 实例如下:/** * 将数值四舍五入后格式化. * * @pa
- 键盘事件废话不多说直接上包from selenium.webdriver.common.keys import Keys1、删除键 BACK
- blankzheng的blog:http://www.planabc.net/margin在中文中我们翻译成外边距或者外补白(本文中引用外边
- 本文实例为大家分享了python绘制直方图的具体代码,供大家参考,具体内容如下运行结果如下代码如下from matplotlib impor
- 前言:👉对于新手来说,库的安装是遇到的第一个挑战,我也入了很多坑,所以想出一期安装库的步骤,由于博主水平限制,博客难免会有错误和不准之处,我
- 首先看一下这三个函数:rtrim() ltrim() trim();rtrim()定义以及用法: rtrim() 函数移除字符串右侧的空白字
- 前言在本文中,您将学习如何使用 OpenCV 进行人脸识别。文章分三部分介绍:第一,将首先执行人脸检测,使用深度学习从每个人脸中提取人脸量化
- 情感分析(sentiment analysis)是2018年公布的计算机科学技术名词。它可以根据文本内容判断出所代表的含义是积极的还是负面的
- 最近,小明为了达成小姐姐的愿望,在某宝买到心仪的宝贝,再加上又迷上了python,就通过python轻而易举地实现了(个人声明:对Java来
- 以下的文章主要是介绍SQL Server数据转换服务的4妙用之执行一些自动化的操作。在SQL Server数据库的实际操作管理中,数据库管理
- 测试方法首先使用implode, serialize, json_encode, msgpack_pack创建四个文本文件,用于测试。创建代