Python中尾递归用法实例详解

  • 时间:
  • 6001人关注

本篇文章主要介绍了Python进阶之尾递归的用法实例,小编觉得挺不错的,现在分享给大家,也给大家做个参考。一起跟随小编过来看看吧,另外这篇文章主要知识点是关于Python、尾递归、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)

一下子就充满了逼格,还高效了许多,何乐而不为呢!

总结

可以看出,在每次递归调用的时候,都会产生一个临时变量,导致进程内存占用量增大一些。这样执行一些递归层数比较深的代码时,除了无谓的内存浪费,还有可能导致著名的堆栈溢出错误。

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持码农之家。


上一篇:基于循环神经网络(RNN)的古诗生成详细写法代码

下一篇:分享如何使用python编写简单的小程序编译成exe跑在win10上

相关内容

  • Python如何限制输出日志的大小

    这篇文章主要介绍了Python 限制输出日志的大小方式,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧

    05-06Python限制日志大小

    阅读更多
  • python实现可视化的MD5、sha256哈希加密小工具

    这篇文章主要介绍了详解python实现可视化的MD5、sha256哈希加密小工具,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧

    04-07python MD5、sha256哈希加密

    阅读更多
  • Python gevent协程切换实现方法

    这篇文章主要介绍了Python gevent协程切换实现详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下

    04-07Python gevent协程切换

    阅读更多
  • python/golang实现循环链表的代码

    这篇文章主要介绍了python/golang如何实现循环链表,帮助大家更好的理解和学习循环链表的实现方法,感兴趣的朋友可以了解下

    04-07python/golang 循环链表

    阅读更多
  • 2020版Python学习路线图(附学习资料)

    这篇文章主要介绍了Python学习路线图(2020最新版),小编觉得挺不错的,现在分享给大家,也给大家做个参考。一起跟随小编过来看看吧

    04-07Python学习路线图

    阅读更多
  • Python基础教程(第3版)

    Python基础教程(第3版)

    本书是一本Python3.5编程从入门到实践书籍,Python入门佳作,包括Python程序设计的方方面面,既能为初学者夯实基础,又能帮助程序员提升技能

    大小:10.1 MBpython

    点击下载
  • 零起点Python机器学习快速入门

    零起点Python机器学习快速入门

    这本书采用独创的黑箱模式,MBA案例教学机制,结合一线实战案例,介绍Sklearn人工智能模块库和常用的机器学习算法,读完本书内容和配套的教学代码,就能够编写简单的机器学习函数

    大小:85.1 MB机器学习

    点击下载
  • 教孩子学编程:Python语言版

    教孩子学编程:Python语言版

    这是一本教孩子使用Python进行基础程序设计和解决问题的入门图书,针对变量、循环、函数等编程基础概念的介绍,可以帮助年轻的程序员构建所需的技能,适合任何想要通过Python学习编程的读

    大小:45.4MB儿童编程

    点击下载
  • Python数据科学入门

    Python数据科学入门

    这本书讲述了Python语言的数据科学基础知识,涵盖数据采集、清洗、存储、检索、转换、可视化、高级数据分析等方面,欢迎下载

    大小:13.9 MBPython数据处理

    点击下载
  • 全国计算机等级考试二级教程:Python语言程序设计

    全国计算机等级考试二级教程:Python语言程序设计

    这里整理了全国计算机等级考试二级教程-Python语言程序设计2018版,根据教育部考试中心制订的,介绍程序设计的基本方法、Python语言基本语法元素和基本数据类型、程序的控制结构等内容

    大小:7.9 MB计算机等级考试

    点击下载
  • Python数据科学手册

    Python数据科学手册

    这本书是以数据深度需求为中心的科学、研究以及针对计算和统计方法的参考书,讲述了个Python数据科学中的重点工具包、Matplotlib、NumPy等对象

    大小:12.4 MBPython

    点击下载
  • Python自然语言处理

    Python自然语言处理

    Python自然语言理解层面的权威性之作 迅速掌握某些定义及基础原理的必看 出示丰富多彩英语语料库和编码,便捷训练 从电脑输入法想到提醒(predictivetext)、email过虑到全自动文字归纳、翻译

    大小:5.3 MBPython

    点击下载

学习笔记