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动态规划的递归、非递归实现
赞 (0)

相关推荐

  • Python实现的递归神经网络简单示例

    本文实例讲述了Python实现的递归神经网络.分享给大家供大家参考,具体如下: # Recurrent Neural Networks import copy, numpy as np np.random.seed(0) # compute sigmoid nonlinearity def sigmoid(x): output = 1/(1+np.exp(-x)) return output # convert output of sigmoid function to its derivati

  • Python进阶之递归函数的用法及其示例

    作者是一名沉迷于Python无法自拔的蛇友,为提高水平,把Python的重点和有趣的实例发在简书上. 一.递归 是指函数/过程/子程序在运行过程序中直接或间接调用自身而产生的重入现象.在计算机编程里,递归指的是一个过程:函数不断引用自身,直到引用的对象已知.使用递归解决问题,思路清晰,代码少.但是在主流高级语言中(如C语言.Pascal语言等)使用递归算法要耗用更多的栈空间,所以在堆栈尺寸受限制时(如嵌入式系统或者内核态编程),应避免采用.所有的递归算法都可以改写成与之等价的非递归算法. (来源

  • 详谈Python基础之内置函数和递归

    详谈Python基础之内置函数和递归

    一.内置函数 下面简单介绍几个: 1.abs() 求绝对值 2.all() 如果 iterable 的所有元素都为真(或者如果可迭代为空),则返回 True 3.any() 如果 iterable 的任何元素为真,则返回 True.如果iterable为空,则返回 False 4.callable() 如果 object 参数出现可调,则返回 True,否则返回 False 5.divmod() 以两个(非复数)数字作为参数,并在使用整数除法时返回由商和余数组成的一对数字.对于混合操作数类型,二

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

    在最开始的时候所有的斐波那契代码都是使用递归的方式来写的,递归有很多的缺点,执行效率低下,浪费资源,还有可能会造成栈溢出,而递归的程序的优点也是很明显的,就是结构层次很清晰,易于理解 可以使用循环的方式来取代递归,当然也可以使用尾递归的方式来实现. 尾递归就是从最后开始计算, 每递归一次就算出相应的结果, 也就是说, 函数调用出现在调用者函数的尾部, 因为是尾部, 所以根本没有必要去保存任何局部变量. 直接让被调用的函数返回时越过调用者, 返回到调用者的调用者去.尾递归就是把当前的运算结果(或路

  • python递归打印某个目录的内容(实例讲解)

    以下函数列出某个目录下(包括子目录)所有文件,本随笔重点不在于递归函数的实现,这是一个很简单的递归,重点在于熟悉Python 库os以及os.path一些函数的功能和用法. 1. os.listdir(path): 列出path下所有内容(包括文件和目录,不包括.和..) 2. os.path.join(path1,path2,path3...): 拼接目录,例如将'home','test'拼接成'home/test/' 3. os.path.isdir(path): 判断path是否为目录 代

  • python 递归遍历文件夹,并打印满足条件的文件路径实例

    题目:利用协程来遍历目录下,所有子文件及子文件夹下的文件是否含有某个字段值,并打印满足条件的文件的绝对路径. #!/user/bin/env python # -*- coding:utf-8 -*- #grep -rl "python" D:\devtools\workspace\python\aaa import os def init(func): def wrapper(*args,**kwargs): res=func(*args,**kwargs) res.send(Non

  • Python基于递归算法实现的走迷宫问题

    本文实例讲述了Python基于递归算法实现的走迷宫问题.分享给大家供大家参考,具体如下: 什么是递归? 简单地理解就是函数调用自身的过程就称之为递归. 什么时候用到递归? 如果一个问题可以表示为更小规模的迭代运算,就可以使用递归算法. 迷宫问题:一个由0或1构成的二维数组中,假设1是可以移动到的点,0是不能移动到的点,如何从数组中间一个值为1的点出发,每一只能朝上下左右四个方向移动一个单位,当移动到二维数组的边缘,即可得到问题的解,类似的问题都可以称为迷宫问题. 在python中可以使用list

  • 分析python动态规划的递归、非递归实现

    概要 本文只是简单的介绍动态规划递归.非递归算法实现 案例一 题目一:求数组非相邻最大和 [题目描述] 在一个数组arr中,找出一组不相邻的数字,使得最后的和最大. [示例输入] arr=1 2 4 1 7 8 3 [示例输出] 15 from functools import wraps def memoDeco(func): ''' memoDeco主要是缓存已遍历的节点,减少递归内存开销 ''' cashe={} @wraps(func) def wrapper(*args): if ar

  • python非递归全排列实现方法

    刚刚开始学习python,当前看到了函数这一节.结合数组操作,写了个非递归的全排列生成.原理是插入法,也就是在一个有n个元素的已有排列中,后加入的元素,依次在前,中,后的每一个位置插入,生成n+1个新的全排列.因为Python切割数组或者字符串,以及合并比较方便,所以,程序会节省很多代码. def getArrayInsertCharToStr(STR,CHAR): arr =[] s_len = len(STR) index =0 while index <= s_len: #分割字符串 ar

  • Python利用递归和walk()遍历目录文件的方法示例

    Python利用递归和walk()遍历目录文件的方法示例

    前言 经常需要检查一个"目录或文件夹"内部有没有我们想要的文件或者文件夹,就需要我们循环迭代出所有文件和子文件夹,Python中遍历指定目录下所有的文件和文件夹,包含多级目录,有两种方法,一种是通过递归思想去遍历,另一种是os模块的walk()函数下面话不多说,就来一起看看详细的介绍: 列出目录结构 一.递归方法 #coding:utf-8 import os allfile=[] def getallfile(path): allfilelist=os.listdir(path) f

随机推荐