go语言尾递归优化尾递归优化 python

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

请问什么是尾递归？

如果一个函数中所有递归形式的调用都出现在函数的末尾，我们称这个递归函数是尾递归的。

当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时，这个递归调用就是尾递归。

尾递归函数的特点是在回归过程中不用做任何操作，这个特性很重要，因为大多数现代的编译器会利用这种特点自动生成优化的代码。

尾递归在普通尾调用的基础上，多出了2个特征：

在尾部调用的是函数自身。

可通过优化，使得计算仅占用常量栈空间。

在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储，递归次数过多容易造成栈溢出。

这时候，就可以使用尾递归，即一个函数中所有递归形式的调用都出现在函数的末尾，对于尾递归来说，由于只存在一个调用记录，所以永远不会发生"栈溢出"错误。

以上内容参考百度百科-尾递归

相关问答

Q1: 尾递归和普通递归的区别

程序调用自身的编程技巧称为递归（ recursion）。递归做为一种算法在程序设计语言中广泛应用。一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。

如果一个函数中所有递归形式的调用都出现在函数的末尾，我们称这个递归函数是尾递归的。当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时，这个递归调用就是尾递归。尾递归函数的特点是在回归过程中不用做任何操作，这个特性很重要，因为大多数现代的编译器会利用这种特点自动生成优化的代码。

Q2: 为什么快速排序不能用尾递归来实现

递归过程中需要子过程计算返回结果的过程才必须要入栈。快速排序是先比较换位之后再把结果分发给两个子过程，在执行完最后一个子过程之后程序自动结束，所以是尾递归的。而归并排序需要最后一个子过程先排序，再逐级返回，继续归并，所以不是尾递归。写程序的时候能看出来，快速排序的递归调用都是在函数尾部，归并排序的递归调用都在函数头部。这才是尾递归和非尾递归的区别。

所有递归都可以写成迭代，但是尾递归可以写成真正的迭代，非尾递归依旧需要一个辅助结构来模拟或者说代替递归所用的栈结构。不过根据问题的不同和栈结构的实现技巧，很多非尾递归问题都是可以通过改写成迭代来提高性能（节约空间或者时间）的。最明显的例子就是斐波那契数列。斐波那契数列递归过程中一定要先入栈，直到压入f(0)和f(1)时才能开始出栈，所以不是尾递归的，但是通过一块内存暂存上一步的结果就可以直接从f(0)和f(1)开始计算得到f(n)的值，这样就省去了递归消耗的栈空间以及入栈出栈的时间开销，所以时间和内存占用都小得多。

另外虽然通常编译器自带的尾递归优化的效果我并没有测试过。不过从网上一些人的测试来看，一般C编译器的尾递归优化应该是和迭代效果相近，甚至我看到有人说测试结果中尾递归优化更快的。所以按理说只要编译器带有尾递归优化，写法满足优化要求，编译器应该会自动完成优化的。

Q3: 如何解决栈溢出

解决递归调用栈溢出的方法是通过尾递归优化，事实上尾递归和循环的效果是一样的，所以，把循环看成是一种特殊的尾递归函数也是可以的。

尾递归，在函数返回的时候，调用自身本身，并且，return语句不能包含表达式。这样，编译器或者解释器就可以把尾递归做优化，使递归本身无论调用多少次，都只占用一个栈帧，不会出现栈溢出的情况。

扩展资料

针对堆栈溢出可能造成的计算机安全问题，通常有以下这些防范措施：

1、强制按照正确的规则写代码。

2、通过操作系统使得缓冲区不可执行，从而阻止攻击者植入攻击代码。但由于攻击者并不一定要通过植入代码来实现攻击，同时linux在信号传递和GCC的在线重用都使用了可执行堆栈的属性，因此该方法依然有一定弱点。

3、利用编译器的边界检查来实现缓冲区的保护。该方法使得缓冲区溢出不可能出现，完全消除了缓冲区溢出的威胁，但代价较大，如性能速度变慢。

4、程序指针完整性检查，该方法能阻止绝大多数缓冲区溢出攻击。该方法就是说在程序使用指针之前，检查指针的内容是否发生了变化。

参考资料来源：百度百科-堆栈溢出

参考资料来源：百度百科-栈溢出