Python进阶之尾递归的用法实例
作者是一名沉迷于Python无法自拔的蛇友,为提高水平,把Python的重点和有趣的实例发在简书上。 尾递归 如果一个函数中所有递归形式的调用都出现在函数的末尾,我们称这个递归函数是尾递归的。当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时,这个递归调用就是尾递归。尾递归函数的特点是在回归过程中不用做任何操作,这个特性很重要,因为大多数现代的编译器会利用这种特点自动生成优化的代码。 (来源于不说人话的某度) 下面是笔者的个人理解:把计算出的值存在函数内部(当然不止尾递归)是其计算方法,从而不用在栈中去创建一个新的,这样就大大节省了空间。函数调用中最后返回的结果是单纯的递归函数调用(或返回结果)就是尾递归。 实例 实例还是和笔者的上一篇文章相同,建议读者阅读 Python ―― 递归 1、阶乘 常规递归阶乘: def factorial(n): if n == 0: return 1 return factorial(n - 1) * n 我们来看一下执行过程:
但是如果把上面的函数写成如下形式: def factorial(n,acc=1): if n == 0: return acc return factorial(n - 1,n * acc) 我们再看下执行过程:
很直观的就可以看出,这次的 factorial 函数在递归调用的时候不会产生一系列逐渐增多的中间变量了,而是将状态保存在 acc 这个变量中。而这种形式的递归,就叫做尾递归。 2、斐波那契数列 常规递斐波那契数列: def fib(n): if n < 2: return n else: return fib(n - 1) + fib(n - 2) 而尾递归: def fib_tail(n,r,t): if n == 1: return r else: return fib_tail(n - 1,t,r + t) 一下子就充满了逼格,还高效了许多,何乐而不为呢! 总结 可以看出,在每次递归调用的时候,都会产生一个临时变量,导致进程内存占用量增大一些。这样执行一些递归层数比较深的代码时,除了无谓的内存浪费,还有可能导致著名的堆栈溢出错误。 以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持编程小技巧。 您可能感兴趣的文章:
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |
- python – NumPy:源代码中的’arange`和`array`函数定义在
- python – 根据内部列表元素的比较从列表列表中删除重复项
- Python 3 UnicodeEncodeError:’ascii’编解码器无法编码字
- python – 为什么即使我设置了随机种子,我也无法在Keras中获
- python – datetime和timedelta
- Python:将数据类型从整数更改为float时出现内存错误
- 如何使用Python在文件夹中搜索与正则表达式匹配的文件名?
- 利用Python中SocketServer 实现客户端与服务器间非阻塞通信
- 如何(有意)跳过使用Django syncdb的应用程序
- 有没有办法使用伪随机序列或散列函数模拟队列的python rand