尾部递归使用的详细说明

这几天看了几篇关于尾部递归的文章，但是之前对尾部递归没有太多的了解，所以回去研究尾部递归。尾部递归的概念尾部递归的概念是递归概念的子集。对于普通递归，因为递归的调用栈必须被记住，所以导致的消耗是不可估量的。比如下面php部分的第一个例子，用php写了一个阶乘函数，就是递归导致堆栈溢出的错误。递归的目的是消除递归堆栈耗尽的缺点。从代码层面，尾部递归可以用一句话说清楚：函数的最后一个操作是递归调用php的递归实现比如‘斐波那契’序列：复制代码如下：fibonacci.php？php函数Fibonacci($ n){ if($ n ^ 2){ return $ n；}返回斐波那契($n - 1)斐波那契($ n-2)；} var_dump(斐波那契(30))；这是一个递归函数，但不是尾部递归，因为斐波那契的最后一个运算是加法运算。转换为尾部递归：复制代码如下：函数斐波那契2 ($ n，$ acc1，$ acc2){ if($ n==0){ return $ acc1；}返回fibonacci2($n-1，$acc2，$ acc1 $ acc2)；} fibonacci2是尾部递归，它将两个累加器acc1和acc2相加，并给出初始值。记住：把递归转化为尾部递归的思路一定是增加累加器，减少递归运算。尾递归在不同语言中的应用也不同。最常用的是函数式编程Erlang，几乎所有的递归函数都修改成尾部递归。我们来谈谈尾部递归在几种不同语言中的表达和应用。php中的尾部递归。让我们做一个实验。普通递归：复制代码如下：php函数阶乘($ n){ if($ n==0){ return 1；}返回阶乘($ n-1)* $ n；} var_dump(阶乘(100000000))；结束递归：复制代码如下：phpfunction阶乘($n，$ ACC){ if($ n==0){ return $ ACC；}返回阶乘($n-1，$ ACC * $ n)；}var_dump(阶乘(100000000，1))；实验结果：

事实上，尾部递归在php中没有优化效果！C语言中的尾部递归C语言中尾部递归的优化是由gcc编译器完成的。在gcc编译期间添加-O2将优化尾部递归。我们可以直接看生成的汇编代码：(使用gdb，gcc -O2阶乘. c -O阶乘；不含-O2生成的程序集：

用O2优化编译：。

不要太大，我只是在看汇编，但是这段代码很简单，在网上搜索命令就可以大致了解：复制的代码如下：函数阶乘(n，sum) {while (n！=0){ sum=n * sum n=n-1 } return sum } gcc真正做到了智能优化。如果还感兴趣，可以用-O3来优化尾部递归，并检查汇编指令-O3的优化是直接将循环展开总结的一般线性递归修改为尾部递归。最大的好处是减少了递归调用栈的开销。从php的例子中，我们可以清楚地看到递归开销对程序的影响。然而，并不是所有的语言都支持尾部递归。即使是支持尾部递归的语言，一般也会在编译阶段优化尾部递归，比如上面例子中的C语言。当使用尾部递归优化代码时，我们必须首先了解语言对尾部递归的支持。