详解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
结果如下：
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度。
这一次，感觉自己好有耐心，一直就在那里等着程序出结果，可以看到三者的时间对比状况，很明显的：直接递归的时间增长的极快，而循环的性能还要优于尾递归，这就告诉我们尽量减少递归的使用，使用循环的方式代替递归无疑是一种提高程序运行效率的方式。
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。
相关推荐
-
如何使用Python实现斐波那契数列
斐波那契数列(Fibonacci)最早由印度数学家Gopala提出,而第一个真正研究斐波那契数列的是意大利数学家 Leonardo Fibonacci,斐波那契数列的定义很简单,用数学函数可表示为: 数列从0和1开始,之后的数由前两个数相加而得出,例如斐波那契数列的前10个数是:0, 1, 1, 2, 3, 5, 8, 13, 21, 34. 用 Python 实现斐波那契数列常见的写法有三种,各算法的执行效率也有很大差别,在面试中也会偶尔会被问到,通常面试的时候不是让你简单的用递归写写就完了,
-
python实现斐波那契数列的方法示例
介绍 斐波那契数列,又称黄金分割数列,指的是这样一个数列:0.1.1.2.3.5.8.13.21.--在数学上,斐波纳契数列以如下递归的方法定义: F(0)=0,F(1)=1,F(n)=F(n-1)+F(n-2)(n≥2,n∈N*) . 1. 元组实现 fibs = [0, 1] for i in range(8): fibs.append(fibs[-2] + fibs[-1]) 这能得到一个在指定范围内的斐波那契数列的列表. 2. 迭代器实现 class Fibs: def __init__
-
Python实现求数列和的方法示例
本文实例讲述了Python实现求数列和的方法.分享给大家供大家参考,具体如下: 问题: 输入 输入数据有多组,每组占一行,由两个整数n(n<10000)和m(m<1000)组成,n和m的含义如前所述. 输出 对于每组输入数据,输出该数列的和,每个测试实例占一行,要求精度保留2位小数. 样例输入 81 4 2 2 样例输出 94.73 3.41 实现代码: import math while 1: x = raw_input() x = list(x.split(" "))
-
Python基于递归算法实现的汉诺塔与Fibonacci数列示例
本文实例讲述了Python基于递归算法实现的汉诺塔与Fibonacci数列.分享给大家供大家参考,具体如下: 这里我们通过2个例子,学习python中递归的使用. 1. 找出Fibonacci数列中,下标为 n 的数(下标从0计数) Fibonacci数列的形式是这样的:0,1,1,2,3,5,8,13-- ① 使用while循环,python2代码如下: def fib(n): a,b=0,1 count=0 while count<n: a,b=b,a+b count=count+1 pri
-
详解python使用递归、尾递归、循环三种方式实现斐波那契数列
在最开始的时候所有的斐波那契代码都是使用递归的方式来写的,递归有很多的缺点,执行效率低下,浪费资源,还有可能会造成栈溢出,而递归的程序的优点也是很明显的,就是结构层次很清晰,易于理解 可以使用循环的方式来取代递归,当然也可以使用尾递归的方式来实现. 尾递归就是从最后开始计算, 每递归一次就算出相应的结果, 也就是说, 函数调用出现在调用者函数的尾部, 因为是尾部, 所以根本没有必要去保存任何局部变量. 直接让被调用的函数返回时越过调用者, 返回到调用者的调用者去.尾递归就是把当前的运算结果(或路
-
详解Spring Boot 访问Redis的三种方式
目录 前言 开始准备 RedisTemplate JPA Repository Cache 总结 前言 最近在极客时间上面学习丁雪丰老师的<玩转 Spring 全家桶>,其中讲到访问Redis的方式,我专门把他们抽出来,在一起对比下,体验一下三种方式开发上面的不同, 分别是这三种方式 RedisTemplate JPA Repository Cache 开始准备 开始之前我们需要有Redis安装,我们采用本机Docker运行Redis, 主要命令如下 docker pull redis doc
-
详解JS异步加载的三种方式
一:同步加载 我们平时使用的最多的一种方式. <script src="http://yourdomain.com/script.js"></script> <script src="http://yourdomain.com/script.js"></script> 同步模式,又称阻塞模式,会阻止浏览器的后续处理,停止后续的解析,只有当当前加载完成,才能进行下一步操作.所以默认同步执行才是安全的.但这样如果js中有输
-
详解Nginx 虚拟主机配置的三种方式(基于IP)
Nginx配置虚拟主机支持3种方式:基于IP的虚拟主机配置,基于端口的虚拟主机配置,基于域名的虚拟主机配置. 详解Nginx 虚拟主机配置的三种方式(基于端口) https://www.jb51.net/article/14977.htm 详解Nginx 虚拟主机配置的三种方式(基于域名) https://www.jb51.net/article/14978.htm 1.基于IP的虚拟主机配置 如果同一台服务器有多个IP,可以使用基于IP的虚机主机配置,将不同的服务绑定在不同的IP上. 1.1
-
详解Nginx 虚拟主机配置的三种方式(基于端口)
Nginx配置虚拟主机支持3种方式:基于IP的虚拟主机配置,基于端口的虚拟主机配置,基于域名的虚拟主机配置. 详解Nginx 虚拟主机配置的三种方式(基于IP) https://www.jb51.net/article/14974.htm 详解Nginx 虚拟主机配置的三种方式(基于域名) https://www.jb51.net/article/14978.htm 2.Nginx基于端口的虚拟主机配置 如一台服务器只有一个IP或需要通过不同的端口访问不同的虚拟主机,可以使用基于端口的虚拟主机配
-
详解Golang开启http服务的三种方式
前言 都说go标准库实用,Api设计简洁.这次就用go 标准库中的net/http包实现一个简洁的http web服务器,包括三种版本. v1最简单版 直接使用http.HandleFunc(partern,function(http.ResponseWriter,*http.Request){}) HandleFunc接受两个参数,第一个为路由地址,第二个为处理方法. //v1 func main() { http.HandleFunc("/", func(w http.Respon
-
详解使用scrapy进行模拟登陆三种方式
scrapy有三种方法模拟登陆方式: - 直接携带cookies - 找url地址,发送post请求存储cookie - 找到对应的form表单,自动解析input标签,自动解析post请求的url地址,自动带上数据,自动发送请求 1.携带cookies登陆github import scrapy import re class Login1Spider(scrapy.Spider): name = 'login1' allowed_domains = ['github.com'] start_
-
详解Redis实现限流的三种方式
面对越来越多的高并发场景,限流显示的尤为重要. 当然,限流有许多种实现的方式,Redis具有很强大的功能,我用Redis实践了三种的实现方式,可以较为简单的实现其方式.Redis不仅仅是可以做限流,还可以做数据统计,附近的人等功能,这些可能会后续写到. 第一种:基于Redis的setnx的操作 我们在使用Redis的分布式锁的时候,大家都知道是依靠了setnx的指令,在CAS(Compare and swap)的操作的时候,同时给指定的key设置了过期实践(expire),我们在限流的主要目的就
-
详解Redis集群搭建的三种方式
一.单节点实例 单节点实例还是比较简单的,平时做个测试,写个小程序如果需要用到缓存的话,启动一个 Redis 还是很轻松的,做为一个 key/value 数据库也是可以胜任的 二.主从模式(master/slaver) redis 主从模式配置 主从模式: redis 的主从模式,使用异步复制,slave 节点异步从 master 节点复制数据,master 节点提供读写服务,slave 节点只提供读服务(这个是默认配置,可以通过修改配置文件 slave-read-only 控制).master
-
详解SpringBoot静态方法获取bean的三种方式
目录 方式一 注解@PostConstruct 方式二 启动类ApplicationContext 方式三 手动注入ApplicationContext 方式一 注解@PostConstruct import com.example.javautilsproject.service.AutoMethodDemoService; import org.springframework.beans.factory.annotation.Autowired; import org.springfr