递归和尾递归的区别和原理_erlang 尾递归原理

                             递归和尾递归的区别和实现

       

      基本上大多数C的入门教材里都会说简单的递归，例如求阶乘n!,经典的本科入门书籍谭浩强的《C语言程序设计》，但后来看了《代码大全2》这本书，关于进阶和编码规范的书中提到了，这些计算机教材用愚蠢的例子阶乘和斐波那契数列来讲解阶乘，因为递归是强有力的工具，但用阶乘去计算阶乘之类的，很不明智，除了速度慢，还无法预测运行期间内存的使用情况，而且递归比循环更难理解。该书说的这些点，的确是递归的一个弊病，但有些时候，递归的思想很不错，二叉树的很多遍历问题，或者排序算法，用递归实现起来很方便。递归的代码比较简洁，但使用起来要慎重，有如上所说的一些弊端，但递归的思想是解决一些可以迭代的问题的。

1. 递归 

 递归的名次解释(百度百科的)： 

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

 

定义如下：

递归，就是在运行的过程中调用自己。

构成递归需具备的条件：

1. 子问题须与原始问题为同样的事，且更为简单；

2. 不能无限制地调用本身，须有个出口，化简为非递归状况处理。

 

以递归方式实现阶乘函数的实现：

 

int fact(int n) {
    if (n < 0)
        return 0;
    else if(n == 0 || n == 1)
        return 1;
    else
        return n * fact(n - 1);
}

 

 

 

 

 

再比如求二叉树的高度就是1+max{height(root->light),height(root->right)}，从而有了递归算法的求解思路。

递归实现的代码如下：

 

int height(BTree *p)
{
    int hi = 0,lh = 0,rh = 0;
    if (p == NULL)
        hi = 0;
    else
    {
        if (p->lchild ==NULL)
            lh = 0;
        else
            lh = height(p->lchild);//递归求解左子树的高度
        if (p->rchild ==NULL)
            rh = 0;
        else
            rh = height(p->rchild);//递归求解右子树的高度
        hi = lh>rh ? (lh + 1) : (rh + 1);
    }
    return hi;
}

 

 

 

下面分析递归的工作原理：

先看看C程序在内存中的组织方式：  http://blog.csdn.net/zcyzsy/article/details/69788884

（我的这篇博文有详细写，这里不做复述）：

BSS段，数据段 ，代码段，堆（heap），栈(stack) ；

  而栈又称堆栈，存放程序的局部变量（不包括静态局部变量，static变量存在静态区）。除此以外，在函数被调用时，栈用来传递参数和返回值。由于栈的后进先出特点，所以栈特别方便用来保存/恢复调用现场。从这个意义上讲，我们可以把堆栈看成一个寄存、交换临时数据的内存区。

    当C程序中调用了一个函数时，栈中会分配一块空间来保存与这个调用相关的信息，每一个调用都被当作是活跃的。栈上的那块存储空间称为活跃记录或者栈帧

    栈帧由5个区域组成：输入参数、返回值空间、计算表达式时用到的临时存储空间、函数调用时保存的状态信息以及输出参数。

    栈是用来存储函数调用信息的绝好方案，然而栈也有一些缺点：

    栈维护了每个函数调用的信息直到函数返回后才释放，这需要占用相当大的空间，尤其是在程序中使用了许多的递归调用的情况下。除此之外，因为有大量的信息需要保存和恢复，因此生成和销毁活跃记录需要消耗一定的时间。我们需要考虑采用迭代的方案。

简而言之，递归过的压栈和出栈，时间和空间都有很大的消耗，

 

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中的尾递归都是一样的。原理相同，效果相同。