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

yipeiwu_com5年前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设计】。

相关文章

Django后台admin的使用详解

Django后台admin的使用详解

简述: Django的admin可以提供一个强大的后台管理功能,可以在web界面对数据库进行操作,我们需要修改admin.py将要操作的数据表注册到后台管理中 创建数据表: 为了便于演示...

python机器人运动范围问题的解答

机器人的运动范围Python实现: 问题:地上有个 m 行 n 列的方格。一个机器人从坐标(0,0)的格子开始移动,它每一次可以向左、右、上、下移动一格,但不能进入行坐标和列坐标的数位之...

python中的句柄操作的方法示例

python中的句柄操作的方法示例

通过窗口标题获取句柄 import win32gui hld = win32gui.FindWindow(None,u"Adobe Acrobat") #返回窗口标题为Adobe...

Python 加密与解密小结

阅读目录 前言 加密算法分类 Python加密库 DES加密 AES加密 RSA加密 前言 据记载,公元前400年,古希腊人发明了置换密码。1881年世界上的第一个电话保密专利出现。在第...

Python判断文件和字符串编码类型的实例

python判断文件和字符串编码类型可以用chardet工具包,可以识别大多数的编码类型。但是前几天在读取一个Windows记事本保存的txt文件时,GBK却被识别成了KOI8-R,无解...