Python进阶之尾递归的用法实例
作者是一名沉迷于Python无法自拔的蛇友,为提高水平,把Python的重点和有趣的实例发在简书上。
尾递归
如果一个函数中所有递归形式的调用都出现在函数的末尾,我们称这个递归函数是尾递归的。当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时,这个递归调用就是尾递归。尾递归函数的特点是在回归过程中不用做任何操作,这个特性很重要,因为大多数现代的编译器会利用这种特点自动生成优化的代码。
(来源于不说人话的某度)
下面是笔者的个人理解:把计算出的值存在函数内部(当然不止尾递归)是其计算方法,从而不用在栈中去创建一个新的,这样就大大节省了空间。函数调用中最后返回的结果是单纯的递归函数调用(或返回结果)就是尾递归。
实例
实例还是和笔者的上一篇文章相同,建议读者阅读 Python —— 递归
1、阶乘
常规递归阶乘:
def factorial(n): if n == 0: return 1 return factorial(n - 1) * n
我们来看一下执行过程:
factorial(4)
factorial(3) * 4
factorial(2) * 3 * 4
factorial(1) * 2 * 3 * 4
factorial(0) * 1 * 2 * 3 * 4
1 * 1 * 2 * 3 * 4
1 * 2 * 3 * 4
2 * 3 * 4
6 * 4
24
但是如果把上面的函数写成如下形式:
def factorial(n, acc=1): if n == 0: return acc return factorial(n - 1, n * acc)
我们再看下执行过程:
factorial(4, 1)
factorial(3, 4)
factorial(2, 12)
factorial(1, 24)
factorial(0, 24)
24
很直观的就可以看出,这次的 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进阶之递归函数的用法及其示例
- 详解python使用递归、尾递归、循环三种方式实现斐波那契数列
- python 递归遍历文件夹,并打印满足条件的文件路径实例
- python递归打印某个目录的内容(实例讲解)
- Python实现的递归神经网络简单示例
- Python基于递归算法实现的走迷宫问题
- Python利用递归和walk()遍历目录文件的方法示例
- 详谈Python基础之内置函数和递归
- python非递归全排列实现方法
- 分析python动态规划的递归、非递归实现