递归和尾递归的区别和实现
基本上在大多数C的入门教材中，都是求阶乘n等简单的递归！ 经典本科入门书cxdpkq的《C语言程序设计》，后来读了《代码大全2》这本书。 根据一本关于高级和编码规范的书，这些计算机教材用愚蠢例子的阶乘和斐波那契数列来解释阶乘。 递归是一个强大的工具，但使用阶乘计算阶乘是不明智的。 不仅速度慢，而且运行中的内存使用情况也无法预测。 另外，递归这本书说的这些点，确实是递归的弊端之一，但有时递归的思想很好，二叉树的很多遍历问题，或者说排序算法用递归实现很方便。 递归代码相对简单，但必须谨慎使用，尽管如上所述存在一些缺点，但递归思想解决了可重复的问题。
1 .递归排序解释(百度百科的) :
程序调用自己的编程技巧称为递归(recursion )。 递归作为一种算法在编程语言中被广泛使用。 过程或函数可以在其定义或说明中直接或间接调用自身。 通常，将大而复杂的问题变换为与原问题相似的小规模问题进行求解。 递归策略可以用很少的程序描述求解问题过程所需的迭代计算，大大减少了程序的代码量。 递归的能力在于用有限的语句定义对象的无限集合。 通常，递归需要边界条件、递归前进段和递归返回段。 如果不满足边界条件，则递归前进； 当满足边界条件时，递归返回。
定义如下。
递归是在执行过程中调用自己。
配置递归所需的条件：
1 .子问题与原问题是一回事，而且必须更简单；
2 .不能无限制地调用本身。 需要出口。 简化为非递归情况处理。
要递归实现阶乘函数：
intfact(intn ) if ) n0 ) return 0； ELSEif(n==0||n==1)返回1； Elsereturnn*fact(n-1； }
例如，如果求出二叉树的高度，则为1max{height(root-light )，height (root-right ) }，从而产生了递归算法的求解构想。
递归实现的代码如下：
intheight(btree*p ) inthi=0，lh=0，rh=0； if(p==null ) hi=0； else{if(p-lchild==null ) lh=0； ELSELH=Height(p-Lchild )； //递归求解左子树高度if(p-rchild==null ) rh=0的ELSERH=Height(p-Rchild )； //递归求解右部分树的高度hi=lhrh？ (lh 1 ) 3360 ) RH1 )； (} return hi； }
递归的结构如下所示。
首先，我们来看看内存中C程序的组织方式。 http://blog.csdn.net/ZC yzsy/article/details/6978884
(我这篇博文写得很详细，这里不再复述) :
BSS段、数据段、代码段、堆(heap )、堆栈)；
堆栈也称为堆栈，用于存储程序的局部变量。 不包含静态局部变量，静态变量中存在静态区域。 此外，调用函数时，栈用于传递参数和返回值。 由于堆栈的后进先出特点，堆栈对于保存/恢复调用现场特别有用。 在这种意义上，可以将堆栈视为存储和交换临时数据的内存区域。
当在c程序中调用函数时，栈将分配空间以存储有关该调用的信息，并且每个调用都被视为活动的。 堆栈上的存储区域称为活动记录或堆栈帧
堆栈框架由五个区域组成：输入参数、返回空间、用于计算表达式的临时存储、调用函数时保存的状态信息和输出参数。
堆栈是存储函数调用信息的好方法，但堆栈有一些缺点。
栈维护每个函数调用的信息，以便在函数返回后释放。 这需要相当大的空间，特别是在程序中使用大量递归调用时。 此外，由于存在大量需要保存和恢复的信息，因此生成和销毁活动记录需要时间。 我们有必要考虑采用迭代的方案。
简单来说，递归堆栈和出堆栈占用大量时间和空间。
2 .尾部递归幸运地采用了一种特殊的递归方式，称为尾部递归，可以避免前述缺点。
递归顺序解释(来自百科)。 为了理解) :
如果一个函数中所有递归形式的调用都出现在函数的末尾，我们称这个递归函数是尾递归的。当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时，这个递归调用就是尾递归。尾递归函数的特点是在回归过程中不用做任何操作，这个特性很重要，因为大多数现代的编译器会利用这种特点自动生成优化的代码。
尾递归的原理：
当编译器检测到一个函数调用是尾递归的时候，它就覆盖当前的活动记录而不是在栈中去创建一个新的。编译器可以做到这点，因为递归调用是当前活跃期内最后一条待执行的语句，于是当这个调用返回时栈帧中并没有其他事情可做，因此也就没有保存栈帧的必要了。通过覆盖当前的栈帧而不是在其之上重新添加一个，这样所使用的栈空间就大大缩减了，这使得实际的运行效率会变得更高。
以尾递归方式实现阶乘函数的实现：
int facttail(int n, int res){ if (n < 0) return 0; else if(n == 0) return 1; else if(n == 1) return res; else return facttail(n - 1, n *res);}
那么尾递归是如何工作的，我们先用递归来计算阶乘，通过对比，看看前面所定义的递归为何不是尾递归。
代码1：在每次函数调用计算n倍的(n－1)!的值，让n=n－1并持续这个过程直到n=1为止。这种定义不是尾递归的，因为每次函数调用的返回值都依赖于用n乘以下一次函数调用的返回值，因此每次调用产生的栈帧将不得不保存在栈上直到下一个子调用的返回值确定。
代码2：函数比代码1多个参数res，除此之外并没有太大区别。res（初始化为1）维护递归层次的深度。这就让我们避免了每次还需要将返回值再乘以n。然而，在每次递归调用中，令res=n*res并且n=n－1。继续递归调用，直到n=1，这满足结束条件，此时直接返回res即可。
可以仔细看看两个函数的具体实现，看看递归和尾递归的不同！
示例中的函数是尾递归的，因为对facttail的单次递归调用是函数返回前最后执行的一条语句。换句话说，在递归调用之后还可以有其他的语句执行，只是它们只能在递归调用没有执行时才可以执行。
尾递归是极其重要的，不用尾递归，函数的堆栈耗用难以估量，需要保存很多中间函数的堆栈。比如sum(n) = f(n) = f(n-1) + value(n) ;会保存n个函数调用堆栈，而使用尾递归f(n, sum) = f(n-1, sum+value(n)); 这样则只保留后一个函数堆栈即可，之前的可优化删去。
关于尾递归，解释下，其实一开始接触尾递归是实习期间，用erlang函数式编程语言写项目程序，erlang中没有循环，只能通过递归和列表解析来实现循环的功能。但众所周知递归是代码好看但效率极低的，于是我看到了erlang的编程之美-尾递归。当时带我的大哥只给了一句，不压栈的递归，放心用，我也实际测了时间，效率之高令人惊艳。在erlang里很好的体验了一波尾递归的强大，多变，实用，灵活。当时没去想C的尾递归，现在觉得要总结一波，C中当然也有高效的尾递归啦。
下面贴一段以前写erlang时的递归和尾递归代码：
% 递归loop(0)-> 1;loop(N)-> N * loop(N - 1). % 尾递归tail_loop(N)-> tail_loop(N, 1). tail_loop(0,R)-> R;tail_loop(N,R) ->tail_loop(N - 1, N*R).
贴几段：%%尾递归实现循环和判断，列表解析实现列表元素的遍历，%%短小精悍，其实是查找列表中是否有连续3个相同的数（和传的参相同）get_aj([],H)->false;get_aj([H|[H|[H|D]]],H)->true;get_aj([_|D],H)->get_aj(D,H).
注意哦，这里尾递归其实还用了一个重载，然后尾递归调用，其实最精髓就是 通过参数传递结果，达到不压栈的目的。C中玩好了尾递归，代码可以很秀。尾递归是一种高效解决问题的思想，C和erlang中的尾递归都是一样的。原理相同，效果相同。