用尾递归和普通递归实现n!算法，二者比较

时间：2021-12-28 05:24:02

尾递归 - Tail Recursion
尾递归是针对传统的递归算法而言的, 传统的递归算法在很多时候被视为洪水猛兽。 它的名声狼籍, 好像永远和低效联系在一起.
尾递归就是从最后开始计算, 每递归一次就算出相应的结果, 也就是说, 函数调用出现在调用者函数的尾部, 因为是尾部, 所以根本没有必要去保存任何局部变量. 直接让被调用的函数返回时越过调用者, 返回到调用者的调用者去.
以n!为例介绍，后面例子n=5.

代码
线性递归

int Rescuvie(int n)

{

  return(n == ) ?  : n * Rescuvie(n - );

}

尾递归

int TailRescuvie(int n, int a)

{

  return(n == ) ? a : TailRescuvie(n - , a * n);

}      

int TailRescuvie(long n)   //封装用的

{

  return(n == ) ?  : TailRescuvie(n, );

}

过程

线性递归

Rescuvie(5)  
{5 * Rescuvie(4)}
{5 * {4 * Rescuvie(3)}}
{5 * {4 * {3 * Rescuvie(2)}}}
{5 * {4 * {3 * {2 * Rescuvie(1)}}}}
{5 * {4 * {3 * {2 * 1}}}}
{5 * {4 * {3 * 2}}}
{5 * {4 * 6}}
{5 * 24}
120

尾递归
TailRescuvie(5)
TailRescuvie(5, 1)
TailRescuvie(4, 5)
TailRescuvie(3, 20)
TailRescuvie(2, 60)
TailRescuvie(1, 120)
120

结论
普通的线性递归比尾递归更加消耗资源, 在实现上说， 每次重复的过程调用都使得调用链条不断加长，系统不得不使用栈进行数据保存和恢复。而尾递归就不存在这样的问题， 因为他的状态完全由n和a保存。

深入

编译器是怎样优化尾递归的？
我们知道递归调用是通过栈来实现的，每调用一次函数，系统都将函数当前的变量、返回地址等信息保存为一个栈帧压入到栈中，那么一旦要处理的运算很大或者数据很多，有可能会导致很多函数调用或者很大的栈帧，这样不断的压栈，很容易导致栈的溢出。

我们回过头看一下尾递归的特性，函数在递归调用之前已经把所有的计算任务已经完毕了，他只要把得到的结果全交给子函数就可以了，无需保存什么，子函数其实可以不需要再去创建一个栈帧，直接把就着当前栈帧，把原先的数据覆盖即可。相对的，如果是普通的递归，函数在递归调用之前并没有完成全部计算，还需要调用递归函数完成后才能完成运算任务，比如return n * fact(n - 1);这句话，这个fact(n)在算完fact（n-1）之后才能得到n * fact(n - 1)的运算结果然后才能返回。

综上所述，编译器对尾递归的优化实际上就是当他发现你丫在做尾递归的时候，就不会去不断创建新的栈帧，而是就着当前的栈帧不断的去覆盖，一来防止栈溢出，二来节省了调用函数时创建栈帧的开销。

优化工作交给编译器还是交给自己？
据网上查阅，java，C#和python都不支持编译环境自动优化尾递归，这种情况下，当然是别用递归效率最高。但是对于C语言来说，编译器白提供的服务，用了也不差，毕竟递归代码会好理解一点，但换句话说，如果写到尾递归这份上了，变成非递归已经很好实现了，完全可以用循环来搞定（尾部递归一般都可转化为循环语句。）。所以这个时候，就看个人喜好了。

参考：http://site.douban.com/196781/widget/notes/12161495/note/262014367/

相关文章