当前位置:首页 > 编程教程 > Python技术文章 > Python进阶之尾递归的用法实例

Python中尾递归用法实例详解

  • 发布时间:
  • 作者:码农之家
  • 点击:165

这篇文章主要知识点是关于Python、尾递归、的内容,如果大家想对相关知识点有系统深入的学习,可以参阅以下电子书

Python+Spark2.0+Hadoop机器学习与大数据实战
  • 类型:Hadoop大小:109 MB格式:PDF作者:林大贵
立即下载

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)

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

总结

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

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

以上就是本次给大家分享的关于java的全部知识点内容总结,大家还可以在下方相关文章里找到相关文章进一步学习,感谢大家的阅读和支持。

Python 相关电子书
学习笔记
网友NO.494075

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

在最开始的时候所有的斐波那契代码都是使用递归的方式来写的,递归有很多的缺点,执行效率低下,浪费资源,还有可能会造成栈溢出,而递归的程序的优点也是很明显的,就是结构层次很清晰,易于理解 可以使用循环的方式来取代递归,当然也可以使用尾递归的方式来实现。 尾递归就是从最后开始计算, 每递归一次就算出相应的结果, 也就是说, 函数调用出现在调用者函数的尾部, 因为是尾部, 所以根本没有必要去保存任何局部变量. 直接让被调用的函数返回时越过调用者, 返回到调用者的调用者去。尾递归就是把当前的运算结果(或路径)放在参数里传给下层函数,深层函数所面对的不是越来越简单的问题,而是越来越复杂的问题,因为参数里带有前面若干步的运算路径。尾递归是极其重要的,不用尾递归,函数的堆栈耗用难以估量,需要保存很……

<
1
>

Copyright 2018-2020 www.xz577.com 码农之家

版权投诉 / 书籍推广 / 赞助:520161757@qq.com

idea注册码