精华内容
参与话题
问答
  • 详解什么是尾递归(通俗易懂,示例讲解)

    万次阅读 多人点赞 2018-11-26 21:52:54
    尾递归中,首先执行计算,然后执行递归调用,将当前步骤的结果传递给下一个递归步骤。这导致最后一个语句采用的形式(return (recursive-function params))。基本上,任何给定递归步骤的返回值与下一个递归调用的...

    传统的递归中,典型的模型是首先执行递归调用,然后获取递归调用的返回值并计算结果。以这种方式,在每次递归调用返回之前,您不会得到计算结果。传统地递归过程就是函数调用,涉及返回地址、函数参数、寄存器值等压栈(在x86-64上通常用寄存器保存函数参数),这样做的缺点有二:

    • 效率低,占内存
    • 如果递归链过长,可能会statck overflow

    若函数在尾位置调用自身(或是一个尾调用本身的其他函数等等),则称这种情况为尾递归。尾递归也是递归的一种特殊情形。尾递归是一种特殊的尾调用,即在尾部直接调用自身的递归函数。对尾递归的优化也是关注尾调用的主要原因。尾调用不一定是递归调用,但是尾递归特别有用,也比较容易实现。

    尾递归的原理:

         当编译器检测到一个函数调用是尾递归的时候,它就覆盖当前的活动记录而不是在栈中去创建一个新的。编译器可以做到这点,因为递归调用是当前活跃期内最后一条待执行的语句,于是当这个调用返回时栈帧中并没有其他事情可做,因此也就没有保存栈帧的必要了。通过覆盖当前的栈帧而不是在其之上重新添加一个,这样所使用的栈空间就大大缩减了,这使得实际的运行效率会变得更高。

    特点:

    尾递归在普通尾调用的基础上,多出了2个特征:

    • 在尾部调用的是函数自身 (Self-called);
    • 可通过优化,使得计算仅占用常量栈空间 (Stack Space)。

    说明:

    传统模式的编译器对于尾调用的处理方式就像处理其他普通函数调用一样,总会在调用时创建一个新的栈帧(stack frame)并将其推入调用栈顶部,用于表示该次函数调用。

    当一个函数调用发生时,电脑必须 “记住” 调用函数的位置 —— 返回位置,才可以在调用结束时带着返回值回到该位置,返回位置一般存在调用栈上。在尾调用这种特殊情形中,电脑理论上可以不需要记住尾调用的位置而从被调用的函数直接带着返回值返回调用函数的返回位置(相当于直接连续返回两次)。尾调用消除即是在不改变当前调用栈(也不添加新的返回位置)的情况下跳到新函数的一种优化(完全不改变调用栈是不可能的,还是需要校正调用栈上形式参数与局部变量的信息。)

    由于当前函数帧上包含局部变量等等大部分的东西都不需要了,当前的函数帧经过适当的更动以后可以直接当作被尾调用的函数的帧使用,然后程序即可以跳到被尾调用的函数。产生这种函数帧更动代码与 “jump”(而不是一般常规函数调用的代码)的过程称作尾调用消除(Tail Call Elimination)或尾调用优化(Tail Call Optimization, TCO)。尾调用优化让位于尾位置的函数调用跟 goto 语句性能一样高,也因此使得高效的结构编程成为现实。

    然而,对于 C++ 等语言来说,在函数最后 return g(x); 并不一定是尾递归——在返回之前很可能涉及到对象的析构函数,使得 g(x) 不是最后执行的那个。这可以通过返回值优化来解决。

    尾递归中,首先执行计算,然后执行递归调用,将当前步骤的结果传递给下一个递归步骤。这导致最后一个语句采用的形式(return (recursive-function params))基本上,任何给定递归步骤的返回值与下一个递归调用的返回值相同

    我们考虑一个最基本的关于N的求和函数,(例如sum(5) = 1 + 2 + 3 + 4 + 5 = 15)。

    这是一个使用JavaScript实现的递归函数:

    function recsum(x) {
        if (x===1) {
            return x;
        } else {
            return x + recsum(x-1);
        }
    }

    如果你调用recsum(5),JavaScript解释器将会按照下面的次序来计算:

    recsum(5)
    5 + recsum(4)
    5 + (4 + recsum(3))
    5 + (4 + (3 + recsum(2)))
    5 + (4 + (3 + (2 + recsum(1))))
    5 + (4 + (3 + (2 + 1)))
    15

    注意在JavaScript解释器计算recsum(5)之前,每个递归调用必须全部完成。

    这是同一函数的尾递归版本:

    function tailrecsum(x, running_total=0) {
        if (x===0) {
            return running_total;
        } else {
            return tailrecsum(x-1, running_total+x);
        }
    }

    下面是当你调用tailrecsum(5)的时候实际的事件调用顺序:

    tailrecsum(5, 0)
    tailrecsum(4, 5)
    tailrecsum(3, 9)
    tailrecsum(2, 12)
    tailrecsum(1, 14)
    tailrecsum(0, 15)
    15

    在尾递归的情况下,每次递归调用的时候,running_total都会更新。

    展开全文
  • 递归和尾递归的区别

    千次阅读 2019-02-28 20:51:30
    以递归方式实现阶乘函数的实现: int recsum(int n) { if (n < 0) return 0; else if(n == 0 || n == 1) return 1; else return n * fact(n - ...以尾递归方式实现阶乘函数的实现: int tailrecsum...

    以递归方式实现阶加函数的实现: 

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

    以尾递归方式实现阶加函数的实现:

    int tailrecsum(int n, int res=0)
    {
        if (n < 0)
            return 0;
        else if(n == 0)
            return res;
        else
            return tailrecsum(n - 1, n + res);
    }
    • 非尾递归,下一个函数结束以后此函数还有后续,所以必须保存本身的环境以供处理返回值。
    • 尾递归,进入下一个函数不再需要上一个函数的环境了,得出结果以后直接返回。

    递归(迭代):

    recsum(5)
    5 + recsum(4)
    5 + (4 + recsum(3))
    5 + (4 + (3 + recsum(2)))
    5 + (4 + (3 + (2 + recsum(1))))
    5 + (4 + (3 + (2 + 1)))
    5 + (4 + (3 + 3))
    5 + (4 + 6)
    5 + 10
    15
    
    

    尾递归:

    tailrecsum(5, 0)
    tailrecsum(4, 5)
    tailrecsum(3, 9)
    tailrecsum(2, 12)
    tailrecsum(1, 14)
    tailrecsum(0, 15)
    15

     

    尾递归的判断标准是函数运行最后一步是否调用自身,而不是是否在函数的最后一行调用自身。

    这是尾递归:

    function f(x) {
       if (x === 1) return 1;
       return f(x-1);
    }

    这不是尾递归:

    function f(x) {
       if (x === 1) return 1;
       return 1 + f(x-1);
    }

     

    在来看一个例子:

    计算斐波那契数列第n项

    //递归
    int fibonacci(int n)
    {
        if (n == 0) 
            return 0;
        else if (n == 1) 
            return 1;
        else 
            return fibonacci(n-1)+fibonacci(n-2);
    }
    //尾递归
    int fibonacci_tail(int n, int ret1, int ret2)
    {
        if (n == 0)
            return ret1;
        else 
            return fibonacci_tail(n-1, ret2, ret1 + ret2);
    }

    如果拿fib(6)=6+fib(5)作为例子的话,普通的递归算到最后,内存中需要储存6+5+4+3+2+fib(1),而尾递归则是20+fib(1)。前者耗费了大量内存。

    通常递归都是在栈上根据调用顺序依次申请空间进行运算,然后层层回调,这是基于上一层运算依赖于下一层的运算结果(或者说上一层的运算还没用做完,需要下一层返回的结果)。

    而尾递归的情况是下层计算结果对上层“无用”(上一层运算已经做完,不依赖后续的递归),为了效率,直接将下一层需要的空间覆盖在上一层上。

    所以,尾递归,比线性递归多一个参数,这个参数是上一次调用函数得到的结果;

    所以,关键点在于,尾递归每次调用都在收集结果,避免了线性递归不收集结果只能依次展开消耗内存的坏处。

    使用尾递归可以带来一个好处:因为进入最后一步后不再需要参考外层函数(caller)的信息,因此没必要保存外层函数的stack,递归需要用的stack只有目前这层函数的,因此避免了栈溢出风险。 

    展开全文
  • 递归和尾递归的区别和原理

    万次阅读 多人点赞 2017-08-14 00:08:07
    递归和尾递归的区别和实现    基本上大多数C的入门教材里都会说简单的递归,例如求阶乘n!,经典的本科入门书籍谭浩强的《C语言程序设计》,但后来看了《代码大全2》这本书,关于进阶和编码规范的书中提到了,这些...

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

           

          基本上大多数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中的尾递归都是一样的。原理相同,效果相同。

    展开全文
  • 今天在进行数据排序时候用到...如果一个函数中所有递归形式的调用都出现在函数的末尾,我们称这个递归函数是尾递归的。当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时,这个递归调用就是

    今天在进行数据排序时候用到递归,但是耗费内存太大,于是想找一找有没有既提升效率又节省内存的算法,然后发现尾递归确实不错,只可惜php并没有对此作优化支持.

    虽然如此,但还是学习了,下面总结一下:

    尾递归 --概念

    如果一个函数中所有递归形式的调用都出现在函数的末尾,我们称这个递归函数是尾递归的。当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时,这个递归调用就是尾递归。尾递归函数的特点是在回归过程中不用做任何操作,这个特性很重要,因为大多数现代的编译器会利用这种特点自动生成优化的代码。

    实例

    为了理解尾递归是如何工作的,让我们再次以递归的形式计算阶乘。首先,这可以很容易让我们理解为什么之前所定义的递归不是尾递归。回忆之前对计算n!的定义:在每个活跃期计算n倍的(n-1)!的值,让n=n-1并持续这个过程直到n=1为止。这种定义不是尾递归的,因为每个活跃期的返回值都依赖于用n乘以下一个活跃期的返回值,因此每次调用产生的栈帧将不得不保存在栈上直到下一个子调用的返回值确定。现在让我们考虑以尾递归的形式来定义计算n!的过程。
    这种定义还需要接受第二个参数a,除此之外并没有太大区别。a(初始化为1)维护递归层次的深度。这就让我们避免了每次还需要将返回值再乘以n。然而,在每次递归调用中,令a=na并且n=n-1。继续递归调用,直到n=1,这满足结束条件,此时直接返回a即可。
    代码实例3-2给出了一个C函数facttail,它接受一个整数n并以尾递归的形式计算n的阶乘。这个函数还接受一个参数a,a的初始值为1。facttail使用a来维护递归层次的深度,除此之外它和fact很相似。读者可以注意一下函数的具体实现和尾递归定义的相似之处。
    示例3-2:以尾递归的形式计算阶乘的一个函数实现
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    /*facttail.c*/
     
    #include"facttail.h"
     
    /*facttail*/
     
     
    int facttail(int n, int a)
    {
     
        /*Compute a factorialina tail - recursive manner.*/
         
        if (n < 0)
            return 0;    
        else if (n == 0)
            return 1;    
        else if (n == 1)
            return a;
        else
            return facttail(n - 1, n * a);
     
    }
    示例3-2中的函数是尾递归的,因为对facttail的单次递归调用是函数返回前最后执行的一条语句。在facttail中碰巧最后一条语句也是对facttail的调用,但这并不是必需的。换句话说,在递归调用之后还可以有其他的语句执行,只是它们只能在递归调用没有执行时才可以执行 。
    尾递归是极其重要的,不用尾递归,函数的堆栈耗用难以估量,需要保存很多中间函数的堆栈。比如f(n, sum) = f(n-1) + value(n) + sum; 会保存n个函数调用堆栈,而使用尾递归f(n, sum) = f(n-1, sum+value(n)); 这样则只保留后一个函数堆栈即可,之前的可优化删去。
    也许在C语言中有很多的特例,但编程语言不只有C语言,在函数式语言Erlang中(亦是栈语言),如果想要保持语言的高并发特性,就必须用尾递归来替代传统的递归。

    尾递归与传统递归比较

    以下是具体实例:
    线性递归:
    1
    2
    3
    4
    5
    long Rescuvie(long n) {
     
        return (n == 1) ? 1 : n * Rescuvie(n - 1);
     
    }
    尾递归:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    long TailRescuvie(long n, long a) {
     
        return (n == 1) ? a : TailRescuvie(n - 1, a * n);
     
    }
     
     
    long TailRescuvie(long n) {//封装用的
         
        return (n == 0) ? 1 : TailRescuvie(n, 1);
     
    }
    当n = 5时
    对于传统线性递归, 他的递归过程如下:
    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)                         return 120
                                                     ↑
    TailRescuvie(4, 5)                         return 120
                                                     ↑
    TailRescuvie(3, 20)                        return 120
                                                     ↑
    TailRescuvie(2, 60)                        return 120
                                                     ↑
    TailRescuvie(1, 120)                       return 120
                                                     ↑
    120                                //当运行到最后时,return a => return 120 ,将120返回上一级

    说明:

    尾递归的效果就是去除了将下层的结果再次返回给上层,需要上层继续计算才得出结果的弊端,如果仔细观看例子就可以看出,其实每个递归的结果是存储在第二个参数a中的,到最后一次计算的时候,会只返回一个a的值,但是因为是递归的原理虽然仍然要返回给上层,依次到顶部才给出结果,但是不需要再做计算了,这点的好处就是每次分配的内存不会因为递归而扩大。

    在效率上,两者的确差不多。


    尾递归的优势

            与普通递归相比,由于尾递归的调用处于方法的最后,因此方法之前所积累下的各种状态对于递归调用结果已经没有任何意义,因此完全可以把本次方法中留在堆栈中的数据完全清除,把空间让给最后的递归调用。这样的优化便使得递归不会在调用堆栈上产生堆积,意味着即时是“无限”递归也不会让堆栈溢出。这便是尾递归的优势。

    编译器优化支持尾递归说明:

    尾递归在某些语言的实现上,能避免上述所说的问题,注意是某些语言上,尾递归本身并不能消除函数调用栈过长的问题,那什么是尾递归呢?在上面写的一般递归函数 func() 中,我们可以看到,func(n)  是依赖于 func(n-1) 的,func(n) 只有在得到 func(n-1) 的结果之后,才能计算它自己的返回值,因此理论上,在 func(n-1) 返回之前,func(n),不能结束返回。因此func(n)就必须保留它在栈上的数据,直到func(n-1)先返回,而尾递归的实现则可以在编译器的帮助下,消除这个限制

    让我们先回顾一下函数调用的大概过程:

    1)调用开始前,调用方(或函数本身)会往栈上压相关的数据,参数,返回地址,局部变量等。

    2)执行函数。

    3)清理栈上相关的数据,返回。

    因此,在函数 A 执行的时候,如果在第二步中,它又调用了另一个函数 B,B 又调用 C.... 栈就会不断地增长不断地装入数据,当这个调用链很深的时候,栈很容易就满 了,这就是一般递归函数所容易面临的大问题。

    一直在强调,尾递归的实现依赖于编译器的帮助(或者说语言的规定),为什么这样说呢?先看下面的程序:

    复制代码
     1 #include <stdio.h>
     2 
     3 int tail_func(int n, int res)
     4 {
     5      if (n <= 1) return res;
     6 
     7      return tail_func(n - 1, n * res);
     8 }
     9 
    10 
    11 int main()
    12 {
    13     int dummy[1024*1024]; // 尽可能占用栈。
    14     
    15     tail_func(2048*2048, 1);
    16     
    17     return 1;
    18 }
    复制代码

    上面这个程序在开了编译优化和没开编译优化的情况下编出来的结果是不一样的,如果不开启优化,直接 gcc -o tr func_tail.c 编译然后运行的话,程序会爆栈崩溃,但如果开优化的话:gcc -o tr -O2 func_tail.c,上面的程序最后就能正常运行。 

    这里面的原因就在于,尾递归的写法只是具备了使当前函数在调用下一个函数前把当前占有的栈销毁,但是会不会真的这样做,是要具体看编译器是否最终这样做,如果在语言层面上,没有规定要优化这种尾调用,那编译器就可以有自己的选择来做不同的实现,在这种情况下,尾递归就不一定能解决一般递归的问题。

    我们可以先看看上面的例子在开优化与没开优化的情况下,编译出来的汇编代码有什么不同,首先是没开优化编译出来的汇编tail_func:

    复制代码
     1 .LFB3:
     2         pushq   %rbp
     3 .LCFI3:
     4         movq    %rsp, %rbp
     5 .LCFI4:
     6         subq    $16, %rsp
     7 .LCFI5:
     8         movl    %edi, -4(%rbp)
     9         movl    %esi, -8(%rbp)
    10         cmpl    $1, -4(%rbp)
    11         jg      .L4
    12         movl    -8(%rbp), %eax
    13         movl    %eax, -12(%rbp)
    14         jmp     .L3
    15 .L4:
    16         movl    -8(%rbp), %eax
    17         movl    %eax, %esi
    18         imull   -4(%rbp), %esi
    19         movl    -4(%rbp), %edi
    20         decl    %edi
    21         call    tail_func
    22         movl    %eax, -12(%rbp)
    23 .L3:
    24         movl    -12(%rbp), %eax
    25         leave
    26         ret
    复制代码

    注意上面标红色的一条语句,call 指令就是直接进行了函数调用,它会先压栈,然后再 jmp 去 tail_func,而当前的栈还在用!就是说,尾递归的作用没有发挥。

    再看看开了优化得到的汇编:

    复制代码
     1 tail_func:
     2 .LFB13:
     3         cmpl    $1, %edi
     4         jle     .L8
     5         .p2align 4,,7
     6 .L9:
     7         imull   %edi, %esi
     8         decl    %edi
     9         cmpl    $1, %edi
    10         jg      .L9
    11 .L8:
    12         movl    %esi, %eax
    13         ret
    复制代码

    注意第7,第10行,尤其是第10行!tail_func() 里面没有函数调用!它只是把当前函数的第二个参数改了一下,直接就又跳到函数开始的地方。此处的实现本质其实就是:下一个函数调用继续延用了当前函数的栈!

    这就是尾递归所能带来的效果: 控制栈的增长,且减少压栈,程序运行的效率也可能更高!

    上面所写的是 c 的实现,正如前面所说的,这并不是所有语言都摆支持,有些语言,比如说 python, 尾递归的写法在 python 上就没有任何作用,该爆的时候还是会爆。

    复制代码
    def func(n, res):
    
        if (n <= 1):
            return res
    
        return func(n-1, n*res)
    
    if __name__ =='__main__':
        print func(4096, 1)
    复制代码

    不仅仅是 python,据说 C# 也不支持,我在网上搜到了这个链接:https://connect.microsoft.com/VisualStudio/feedback/details/166013/c-compiler-should-optimize-tail-calls微软的人在上面回答说,实现这个优化有些问题需要处理,并不是想像中那么容易,因此暂时没有实现,但是这个回答是在2007年的时候了,到现在岁月变迁,不知支持了没?我看老赵写的尾递归博客是在2009年,用 c# 作的例子,估计现在 c# 是支持这个优化的了(待考).

    尾调用

    前面的讨论一直都集中在尾递归上,这其实有些狭隘,尾递归的优化属于尾调用优化这个大范畴,所谓尾调用,形式它与尾递归很像,都是一个函数内最后一个动作是调用下一个函数,不同的只是调用的是谁,显然尾递归只是尾调用的一个特例。

    复制代码
    int func1(int a)
    {
       static int b = 3;
       return a + b;
    }
    
    int func2(int c)
    {
        static int b = 2;
    
        return func1(c+b);
    }
    复制代码

    上面例子中,func2在调用func1之前显然也是可以完全丢掉自己占有的栈空间的,原因与尾递归一样,因此理论上也是可以进行优化的,而事实上这种优化也一直是程序编译优化里的一个常见选项,甚至很多的语言在标准里就直接要求要对尾调用进行优化,原因很明显,尾调用在程序里是经常出现的,优化它不仅能减少栈空间使用,通常也能给程序运行效率带来比较大的提升。 



    文章参考链接:

    漫谈递归:尾递归与CPS


    php可以采用函数自行优化,可以参考

    http://www.nowamagic.net/librarys/veda/detail/2334


    展开全文
  • 尾递归是什么?效率高很多

    千次阅读 2019-06-21 15:32:56
    了解尾递归之前,先了解一下尾调用。 function foo(data) { a(data); return b(data); } 这里的a(data)和b(data)都是函数调用,但是b(data)是函数返回前的最后运行的东西,所以也是所谓的尾位置。例如: ...
  • 一般递归与尾递归

    千次阅读 2018-08-07 15:58:35
    一般递归 def normal_recursion(n): if n == 1: return 1 else: return n + normal_recursion(n-1) 执行: normal_recursion(5) 5 + normal_recursion(4) 5 + 4 + normal_recursion(3) 5 + 4 ...
  • 递归和尾递归 一般递归 尾递归 概念 递归 在定义一个过程或函数时,直接或者间接调用自己的成分,称为(直接/间接)递归。直接递归就不用说了,间接递归如下。 间接递归都可以转化为直接递归,因此一般只...
  • 递归与尾递归

    2020-11-13 15:35:11
    递归 递归的概念大家应该都知道吧,平时开发中也经常用到,比如在做后台管理系统时路由菜单,就需要递归遍历嵌套的路由菜单。最经典的还是阶乘或累加函数,如: function add(n){ if(n <= 0) return 0 return ...
  • 递归转尾递归

    2019-06-27 18:45:49
    递归与尾递归 关于递归操作,相信大家都已经不陌生。简单地说,一个函数直接或间接地调用自身,是为直接或间接递归。例如,我们可以使用递归来计算一个单向链表的长度: public class Node { public Node(int value,...
  • 尾递归优化

    2018-02-23 17:09:57
    尾递归就是递归语句在函数最后执行,且无需对返回值进行进一步操作。编译器会对这种递归进行优化,在进入深层递归时候,不是在递归栈进行入栈操作,而是直接覆盖栈顶。线性递归与尾递归区别如下线性递归:12345long ...
  • JS尾递归优化

    千次阅读 2019-02-16 01:47:24
    4. 尾递归 5. 如何快速的发现尾递归的思路 6. 实战演练 1. 写在前面 本文适合对JS基础有较好的理解的基础上阅读体验最佳,若对JS基础没太搞明白的也难会有点晦涩难懂。不知道什么是尾递归的请去看我上一篇对于尾...
  • 递归及尾递归优化

    2018-05-26 21:16:51
    1、递归介绍递归简而言之就是自己调用自己。使用递归解决问题的核心就是分析出递归的模型,看这个问题能拆分出和自己类似的问题并且有一个递归出口。比如最简单的就5的阶乘,可以把它拆分成5*4!,然后求4!又可以调用...
  • 如何在Python中实现尾递归优化

    千次阅读 2018-04-27 20:07:22
    我的机器学习教程「美团」算法工程师带你入门机器学习 已经开始更新了,欢迎大家订阅~ 任何关于算法、编程、AI行业知识或博客内容的问题,可以随时扫码关注公众号「图灵的猫」,加入”学习...一般递归 ...
  • Python 的尾递归优化

    2018-02-08 20:42:47
    什么是尾递归 有很多时候,使用递归的方式写代码要比迭代更直观一些,以下面的阶乘为例: def factorial(n): if n == 0: return 1 return factorial(n - 1) * n 但是这个函数调用,如果展开,会变成如下...
  • 点击上方蓝色字体,关注我 ——一个在阿里云打工的清华学渣!今天,我们来聊聊递归函数。为啥突然想到递归?其实就从电影名字《恐怖游轮》《盗梦空间》想到了。递归是啥?递归函数大家肯定写过,...
  • Kotlin尾递归优化

    千次阅读 2018-04-03 00:33:19
    一、尾递归优化 1.递归的一种特殊形式 2.调用自身后无其他的操作 3.tailrec关键字提示编译器尾递归优化 二、具体的来看看一下代码说明 package net.println.kotlin.chapter5.tailrecursive /** * @author:...
  • C++ 尾递归优化

    2018-12-21 18:14:00
    参考来源:... 用 C++ 重现了一遍。 例子:裴波拉契数列: 1,1,2,3,5,8,。。。...用递归求第 n 项: double fabonacci(int n){//normal recursion if(n<=0){ cout...
  • 实现js尾递归优化的代码

    千次阅读 2018-03-15 10:54:39
    在学习数据结构和算法的时候,我们都知道所有的递归都是可以优化成栈+循环的。 对于特定的递归函数,一般我们都是手动对它们进行优化的。 在学习scala的时候,接触到尾递归的...对于不支持尾递归优化的环境,我...
  • C++程序栈与尾递归优化

    千次阅读 2016-10-28 13:44:52
    尾递归函数的特点是在回归过程中不用做任何操作,这个特性很重要,因为大多数现代的编译器会利用这种特点自动生成优化的代码。 -----取自百度百科   只要理解了函数调用栈,那么尾递归就很好理解了。如果你还...
  • 递归优化尾递归

    千次阅读 2017-10-16 18:15:22
    一个函数直接或间接调用自己本身,这种函数即为递归函数。 递归算法能够以一种优雅的思考方式简化问题,但由于递归通常是通过堆栈来实现的,一直背负着效率低的“臭名”。 以计算斐波那契数列为例,程序代码...

空空如也

1 2 3 4 5 ... 20
收藏数 68,200
精华内容 27,280
关键字:

尾递归