当前位置:主页 > python教程 > Python进阶之尾递归的用法实例

Python中尾递归用法实例详解

发布:2020-03-05 18:58:34 165


给网友朋友们带来一篇Python相关的编程文章,网友国木兰根据主题投稿了本篇教程内容,涉及到Python、尾递归、Python进阶之尾递归的用法实例相关内容,已被795网友关注,涉猎到的知识点内容可以在下方电子书获得。

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编写局域网内聊天功能的聊天室

    发布:2019-06-17

    这篇文章主要为大家详细介绍了python编写简易聊天室实现局域网内聊天功能,具有一定的参考价值,感兴趣的小伙伴们可以参考一下


  • python字典添加元素的实例方法

    发布:2019-09-17

    python字典是另一种可变容器模型,且可存储任意类型对象。向python字典添加新内容的方法是增加新的键/值对。


  • 精选Python开发工程师面试题

    发布:2019-11-06

    你知道吗?实际上Python早在20世纪90年代初就已经诞生,可是火爆时间却并不长,就小编本人来说,也是前几年才了解到它。据统计,目前Python开发人员的薪资待遇为10K以上,这样的诱惑很难让人拒


  • Python实现人生重开模拟器小游戏讲解

    发布:2023-03-09

    这篇文章主要介绍了Python实现人生重开模拟器小游戏,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习吧


  • python2.7安装opencv-python很慢且总是失败问题

    发布:2023-03-28

    这篇文章主要介绍了python2.7安装opencv-python很慢且总是失败问题,具有很好的参考价值,希望对大家有所帮助。如有错误或未考虑完全的地方,望不吝赐教


  • Python+OpenCV实现黑白老照片上色功能

    发布:2023-04-10

    我们都知道,有很多经典的老照片,受限于那个时代的技术,只能以黑白的形式传世。尽管黑白照片别有一番风味,但是彩色照片有时候能给人更强的代入感。本文就来用Python和OpenCV实现老照片上色功能,需要的可以参考一下


  • 如何使用python代理工具mitmproxy

    发布:2020-01-08

    这篇文章主要介绍了python mitmproxy 使用指南,mitmproxy 可以用来拦截、修改、保存 HTTP/HTTPS 请求。以命令行终端形式呈现,类似于 Chrome 浏览器开发者模式的可视化工具,需要的朋友可以参考下


  • python中pip的使用和修改下载源的实例操作方法

    发布:2019-11-20

    这篇文章主要介绍了python中pip的使用和修改下载源的方法,小编觉得挺不错的,现在分享给大家,也给大家做个参考。一起跟随小编过来看看吧


网友讨论