以前在阮一峰的ECMAScript函数的扩展一章节中了解到了有关尾递归优化的问题，当时没有深入的去思考，今天看算法导论的时候和同学做了下实验才恍然大悟.
如果一个函数中所有递归形式的调用都出现在函数的末尾，我们称这个递归函数是尾递归的。当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时，这个递归调用就是尾递归。尾递归函数的特点是在回归过程中不用做任何操作，这个特性很重要，因为大多数现代的编译器会利用这种特点自动生成优化的代码。
首先我们来看一个递归函数:
int func(int n)
{
if (n <= 1) return 1;
return (n * func(n - 1));
}很显然，这是一个普通的求阶乘的函数，在不考虑精度的情况下，我们对此函数进行如下调用:
#include "iostream"
using namespace std;
int func(int n)
{
if (n <= 1) return 1;
return (n * func(n - 1));
}
int main()
{
int k = func(INT_MAX);
cout << k << endl;
return 0;
}其中INT_MAX是有符号整型的最大值，在VS2017中编译运行:
0x01391042 处有未经处理的异常(在 Algorithm.exe 中): 0xC00000FD: Stack overflow (参数: 0x00000001, 0x00402FFC)。
该程序的栈的深度达到的INT_MAX，很显然编译器并没有给该程序这么大的栈空间.
那么，如何来解决这一问题呢？最简单的方法当然就是将这个递归函数改成循环结构的函数，这一点非常简单，不予赘述.另外一种方法则是采用尾递归:
int tail_func(int n, int res)
{
if (n <= 1) return res;
return tail_func(n - 1, n * res);
}
int main()
{
int k = tail_func(INT_MAX,1);
cout << k << endl;
return 0;
}在VS2017中编译运行后，我们可以发现栈并没有溢出，其原因是:当编译器检测到一个函数调用是尾递归的时候，它就覆盖当前的活动记录而不是在栈中去创建一个新的。编译器可以做到这点，因为递归调用是当前活跃期内最后一条待执行的语句，于是当这个调用返回时栈帧中并没有其他事情可做，因此也就没有保存栈帧的必要了。通过覆盖当前的栈帧而不是在其之上重新添加一个，这样所使用的栈空间就大大缩减了，这使得实际的运行效率会变得更高。
真的是这样吗？我们对上面的两个函数进行反汇编，查看这两个函数的汇编代码:
009B102F int 3
--- c:\users\pouee\source\repos\algorithm\algorithm\tailrecursion.cpp ----------
if (n <= 1) return res;
009B1030 cmp ecx,1
009B1033 jle tail_func+0Eh (09B103Eh)
return tail_func(n - 1, n * res);
009B1035 imul edx,ecx
009B1038 dec ecx
009B1039 cmp ecx,1
009B103C jg tail_func+5h (09B1035h)
}
009B103E mov eax,edx
009B1040 ret 注意到上面尾递归的版本确实把递归优化成了循环.再看没有尾递归的版本:
int func(int n)
{
00B31030 push esi
00B31031 mov esi,ecx
if (n <= 1) return 1;
00B31033 cmp esi,1
00B31036 jg func+0Fh (0B3103Fh)
00B31038 mov eax,1
00B3103D pop esi
}
00B3103E ret
return (n * func(n - 1));
00B3103F lea ecx,[esi-1]
00B31042 call func (0B31030h)
00B31047 imul eax,esi
00B3104A pop esi
}上面的call 表明该函数是递归调用
部分资料来源:https://baike.baidu.com/item/%E5%B0%BE%E9%80%92%E5%BD%92/554682?fr=aladdin
