Hello World
Spiga

尾递归与Continuation

2009-03-26 22:24 by 老赵, 34808 visits

这几天恰好和朋友谈起了递归,忽然发现不少朋友对于“尾递归”的概念比较模糊,网上搜索一番也没有发现讲解地完整详细的资料,于是写了这么一篇文章,权当一次互联网资料的补充。:P

递归与尾递归

关于递归操作,相信大家都已经不陌生。简单地说,一个函数直接或间接地调用自身,是为直接或间接递归。例如,我们可以使用递归来计算一个单向链表的长度:

public class Node
{
    public Node(int value, Node next)
    {
        this.Value = value;
        this.Next = next;
    }

    public int Value { get; private set; }

    public Node Next { get; private set; }
}

编写一个递归的GetLength方法:

public static int GetLengthRecursively(Node head)
{
    if (head == null) return 0;
    return GetLengthRecursively(head.Next) + 1;
}

在调用时,GetLengthRecursively方法会不断调用自身,直至满足递归出口。对递归有些了解的朋友一定猜得到,如果单项链表十分长,那么上面这个方法就可能会遇到栈溢出,也就是抛出StackOverflowException。这是由于每个线程在执行代码时,都会分配一定尺寸的栈空间(Windows系统中为1M),每次方法调用时都会在栈里储存一定信息(如参数、局部变量、返回地址等等),这些信息再少也会占用一定空间,成千上万个此类空间累积起来,自然就超过线程的栈空间了。不过这个问题并非无解,我们只需把递归改成如下形式即可(在这篇文章里我们不考虑非递归的解法):

public static int GetLengthTailRecursively(Node head, int acc)
{
    if (head == null) return acc;
    return GetLengthTailRecursively(head.Next, acc + 1);
}

GetLengthTailRecursively方法多了一个acc参数,acc的为accumulator(累加器)的缩写,它的功能是在递归调用时“积累”之前调用的结果,并将其传入下一次递归调用中——这就是GetLengthTailRecursively方法与GetLengthRecursively方法相比在递归方式上最大的区别:GetLengthRecursive方法在递归调用后还需要进行一次“+1”,而GetLengthTailRecursively的递归调用属于方法的最后一个操作。这就是所谓的“尾递归”。与普通递归相比,由于尾递归的调用处于方法的最后,因此方法之前所积累下的各种状态对于递归调用结果已经没有任何意义,因此完全可以把本次方法中留在堆栈中的数据完全清除,把空间让给最后的递归调用。这样的优化1便使得递归不会在调用堆栈上产生堆积,意味着即时是“无限”递归也不会让堆栈溢出。这便是尾递归的优势。

有些朋友可能已经想到了,尾递归的本质,其实是将递归方法中的需要的“所有状态”通过方法的参数传入下一次调用中。对于GetLengthTailRecursively方法,我们在调用时需要给出acc参数的初始值:

GetLengthTailRecursively(head, 0)

为了进一步熟悉尾递归的使用方式,我们再用著名的“菲波纳锲”数列作为一个例子。传统的递归方式如下:

public static int FibonacciRecursively(int n)
{
    if (n < 2) return n;
    return FibonacciRecursively(n - 1) + FibonacciRecursively(n - 2);
}

而改造成尾递归,我们则需要提供两个累加器:

public static int FibonacciTailRecursively(int n, int acc1, int acc2)
{
    if (n == 0) return acc1;
    return FibonacciTailRecursively(n - 1, acc2, acc1 + acc2);
}

于是在调用时,需要提供两个累加器的初始值:

FibonacciTailRecursively(10, 0, 1)

尾递归与Continuation

Continuation,即为“完成某件事情”之后“还需要做的事情”。例如,在.NET中标准的APM调用方式,便是由BeginXXX方法和EndXXX方法构成,这其实便是一种Continuation:在完成了BeginXXX方法之后,还需要调用EndXXX方法。而这种做法,也可以体现在尾递归构造中。例如以下为阶乘方法的传统递归定义:

public static int FactorialRecursively(int n)
{
    if (n == 0) return 1;
    return FactorialRecursively(n - 1) * n;
}

显然,这不是一个尾递归的方式,当然我们轻易将其转换为之前提到的尾递归调用方式。不过我们现在把它这样“理解”:每次计算n的阶乘时,其实是“先获取n - 1的阶乘”之后再“与n相乘并返回”,于是我们的FactorialRecursively方法可以改造成:

public static int FactorialRecursively(int n)
{
    return FactorialContinuation(n - 1, r => n * r);
}

// 6. FactorialContinuation(n, x => x)
public static int FactorialContinuation(int n, Func<int, int> continuation)
{
    ...
}

FactorialContinuation方法的含义是“计算n的阶乘,并将结果传入continuation方法,并返回其调用结果”。于是,很容易得出,FactorialContinuation方法自身便是一个递归调用:

public static int FactorialContinuation(int n, Func<int, int> continuation)
{
    return FactorialContinuation(n - 1,
        r => continuation(n * r));
}

FactorialContinuation方法的实现可以这样表述:“计算n的阶乘,并将结果传入continuation方法并返回”,也就是“计算n - 1的阶乘,并将结果与n相乘,再调用continuation方法”。为了实现“并将结果与n相乘,再调用continuation方法”这个逻辑,代码又构造了一个匿名方法,再次传入FactorialContinuation方法。当然,我们还需要为它补充递归的出口条件:

public static int FactorialContinuation(int n, Func<int, int> continuation)
{
    if (n == 0) return continuation(1);
    return FactorialContinuation(n - 1,
        r => continuation(n * r));
}

很明显,FactorialContinuation实现了尾递归。如果要计算n的阶乘,我们需要如下调用FactorialContinuation方法,表示“计算10的阶乘,并将结果直接返回”:

FactorialContinuation(10, x => x)

再加深一下印象,大家是否能够理解以下计算“菲波纳锲”数列第n项值的写法?

public static int FibonacciContinuation(int n, Func<int, int> continuation)
{
    if (n < 2) return continuation(n);
    return FibonacciContinuation(n - 1,
        r1 => FibonacciContinuation(n - 2,
            r2 => continuation(r1 + r2)));
}

在函数式编程中,此类调用方式便形成了“Continuation Passing Style(CPS)”。由于C#的Lambda表达式能够轻松构成一个匿名方法,我们也可以在C#中实现这样的调用方式。您可能会想——汗,何必搞得这么复杂,计算阶乘和“菲波纳锲”数列不是一下子就能转换成尾递归形式的吗?不过,您试试看以下的例子呢?

对二叉树进行先序遍历(pre-order traversal)是典型的递归操作,假设有如下TreeNode类:

public class TreeNode
{
    public TreeNode(int value, TreeNode left, TreeNode right)
    {
        this.Value = value;
        this.Left = left;
        this.Right = right;
    }

    public int Value { get; private set; }

    public TreeNode Left { get; private set; }

    public TreeNode Right { get; private set; }
}

于是我们来传统的先序遍历一下:

public static void PreOrderTraversal(TreeNode root)
{
    if (root == null) return;

    Console.WriteLine(root.Value);
    PreOrderTraversal(root.Left);
    PreOrderTraversal(root.Right);
}

您能用“普通”的方式将它转换为尾递归调用吗?这里先后调用了两次PreOrderTraversal,这意味着必然有一次调用没法放在末尾。这时候便要利用到Continuation了:

public static void PreOrderTraversal(TreeNode root, Action<TreeNode> continuation)
{
    if (root == null)
    {
        continuation(null);
        return;
    }

    Console.WriteLine(root.Value);

    PreOrderTraversal(root.Left,
        left => PreOrderTraversal(root.Right,
            right => continuation(right)));
}

我们现在把每次递归调用都作为代码的最后一次操作,把接下来的操作使用Continuation包装起来,这样就实现了尾递归,避免了堆栈数据的堆积。可见,虽然使用Continuation是一个略有些“诡异”的使用方式,但是在某些时候它也是必不可少的使用技巧。

Continuation的改进

看看刚才的先序遍历实现,您有没有发现一个有些奇怪的地方?

PreOrderTraversal(root.Left,
    left => PreOrderTraversal(root.Right,
        right => continuation(right)));

关于最后一步,我们构造了一个匿名函数作为第二次PreOrderTraversal调用的Continuation,但是其内部直接调用了continuation参数——那么我们为什么不直接把它交给第二次调用呢?如下:

PreOrderTraversal(root.Left,
    left => PreOrderTraversal(root.Right, continuation));

我们使用Continuation实现了尾递归,其实是把原本应该分配在栈上的信息丢到了托管堆上。每个匿名方法其实都是托管堆上的对象,虽然说这种生存周期短的对象不会对内存资源方面造成多大问题,但是尽可能减少此类对象,对于性能肯定是有帮助的。这里再举一个更为明显的例子,求二叉树的大小(Size):

public static int GetSize(TreeNode root, Func<int, int> continuation)
{
    if (root == null) return continuation(0);
    return GetSize(root.Left,
        leftSize => GetSize(root.Right,
            rightSize => continuation(leftSize + rightSize + 1)));
}

GetSize方法使用了Continuation,它的理解方法是“获取root的大小,再将结果传入continuation,并返回其调用结果”。我们可以将其进行改写,减少Continuation方法的构造次数:

public static int GetSize2(TreeNode root, int acc, Func<int, int> continuation)
{
    if (root == null) return continuation(acc);
    return GetSize2(root.Left, acc,
        accLeftSize => GetSize2(root.Right, accLeftSize + 1, continuation));
}

GetSize2方法多了一个累加器参数,同时它的理解方式也有了变化:“将root的大小累加到acc上,再将结果传入continuation,并返回其调用结果”。也就是说GetSize2返回的其实是一个累加值,而并非是root参数的实际尺寸。当然,我们在调用时GetSize2时,只需将累加器置零便可:

GetSize2(root, 0, x => x)

不知您清楚了吗?

结束

在命令式编程中,我们解决一些问题往往可以使用循环来代替递归,这样便不会因为数据规模造成堆栈溢出。但是在函数式编程中,要实现“循环”的唯一方法便是“递归”,因此尾递归和CPS对于函数式编程的意义非常重大。了解尾递归,对于编程思维也有很大帮助,因此大家不妨多加思考和练习,让这样的方式为自己所用。

相关文章

 

注1:事实上,在C#中,即使您实现了尾递归,编译器(包括C#编译器及JIT)也不会进行优化,也就是说还是无法避免StackOverflowException。我会在不久之后单独讨论一下这方面问题。

Creative Commons License

本文基于署名 2.5 中国大陆许可协议发布,欢迎转载,演绎或用于商业目的,但是必须保留本文的署名赵劼(包含链接),具体操作方式可参考此处。如您有任何疑问或者授权方面的协商,请给我留言

Add your comment

114 条回复

  1. MATZ[未注册用户]
    *.*.*.*
    链接

    MATZ[未注册用户] 2009-03-26 14:12:00

    这么用过,但是不知道这就是尾递归。。学习了

  2. !A.Z[未注册用户]
    *.*.*.*
    链接

    !A.Z[未注册用户] 2009-03-26 14:12:00

    沙发。函数递归栈溢出是需要预判和改写代码的

  3. 慢了[未注册用户]
    *.*.*.*
    链接

    慢了[未注册用户] 2009-03-26 14:29:00

    之前我已经问过脑袋这个问题, 不过他还未回复我,今天又看到尾递归, 而且还看到我的问题的例子, 所以我想再问一下, 我下面的代码执行后的时间大概是传统尾递归时间的3 倍到4倍左右, 我不是很清楚是不是Lambda表达式导致的, 麻烦能顺便解析一下吗?
    private void print(int n, int result)
    {
    textBox1.Text += "n=" + n.ToString() + " => " + result.ToString() + System.Environment.NewLine;
    }
    private void cacl(int n, Func<int, int> feb)
    {
    if (n <= 35)
    {
    print(n, feb(n));
    cacl(n + 1, feb);
    }
    }
    static void Main()
    {
    var feb = Fix<int, int>(f => x => x > 2 ? f(x - 1) + f(x - 2) : 1);
    cacl(1, feb);
    }

  4. Allen Lee
    *.*.*.*
    链接

    Allen Lee 2009-03-26 14:39:00

    写得不错

  5. 韦恩卑鄙
    *.*.*.*
    链接

    韦恩卑鄙 2009-03-26 14:50:00

    作为一个 vber 我来问一句

    这玩艺vb有么

  6. 老赵
    admin
    链接

    老赵 2009-03-26 14:59:00

    --引用--------------------------------------------------
    !A.Z: 沙发。函数递归栈溢出是需要预判和改写代码的
    --------------------------------------------------------
    这是什么意思?

  7. 老赵
    admin
    链接

    老赵 2009-03-26 15:00:00

    --引用--------------------------------------------------
    Allen Lee: 写得不错
    --------------------------------------------------------
    谢谢支持

  8. 老赵
    admin
    链接

    老赵 2009-03-26 15:00:00

    --引用--------------------------------------------------
    韦恩卑鄙: 作为一个 vber 我来问一句

    这玩艺vb有么
    --------------------------------------------------------
    VB不懂啊,不过应该可以吧

  9. 老赵
    admin
    链接

    老赵 2009-03-26 15:00:00

    @慢了
    fixed-point combinator?

  10. Allen Lee
    *.*.*.*
    链接

    Allen Lee 2009-03-26 15:50:00

    --引用--------------------------------------------------
    Jeffrey Zhao: --引用--------------------------------------------------
    韦恩卑鄙: 作为一个 vber 我来问一句

    这玩艺vb有么
    --------------------------------------------------------
    VB不懂啊,不过应该可以吧
    --------------------------------------------------------
    VB可以找装配脑袋。。

  11. Leven
    *.*.*.*
    链接

    Leven 2009-03-26 15:52:00

    好文,学习了...

  12. 老赵
    admin
    链接

    老赵 2009-03-26 16:17:00

    @Allen Lee
    脑袋的脑袋就是好使,羡慕一把

  13. JimLiu
    *.*.*.*
    链接

    JimLiu 2009-03-26 17:10:00

    计算机系统果然神奇……
    不过话说回来,能不递归的时候还是不递归的好

  14. 老赵
    admin
    链接

    老赵 2009-03-26 17:12:00

    --引用--------------------------------------------------
    JimLiu: 计算机系统果然神奇……
    不过话说回来,能不递归的时候还是不递归的好
    --------------------------------------------------------
    嗯嗯,不过……
    1、有些时候递归思路清晰,比如最简单的,汉诺塔。
    2、函数式编程里,递归是唯一选择。

  15. shen126[未注册用户]
    *.*.*.*
    链接

    shen126[未注册用户] 2009-03-26 17:45:00

    我的理解是:
    只要是函数调用就要消耗堆栈空间,尾递归也不例外。只不过每次尾递归比普通递归少消耗点堆栈空间罢了,是这样吗?

  16. 老赵
    admin
    链接

    老赵 2009-03-26 17:47:00

    @shen126
    不是,文章里写了,尾递归是*丝毫*不会在堆栈里累积数据的。

  17. 装配脑袋
    *.*.*.*
    链接

    装配脑袋 2009-03-26 17:55:00

    var feb = Fix<int, int>(f => x => x > 2 ? f(x - 1) + f(x - 2) : 1);
    这个不是尾递归嘛。
    尾递归的逻辑通常其实是迭代算法。
    var feb2 = Fix<int, int, int, int>(f => (n, x, y) => n <= 2 ? y : f(n - 1, y, x + y));

  18. 装配脑袋
    *.*.*.*
    链接

    装配脑袋 2009-03-26 17:59:00

    PS我回复的是3楼。。。

  19. 老赵
    admin
    链接

    老赵 2009-03-26 18:53:00

    @装配脑袋
    你这个性能难道不是没有变化的,这里不是尾递归与否造成的性能问题吧……

  20. 装配脑袋
    *.*.*.*
    链接

    装配脑袋 2009-03-26 19:29:00

    Fix的实现仅供参考……不明白3楼的意思,飘过~
    static Func<T1, T2, T3, TR> Fix<T1, T2, T3, TR>(Func<Func<T1, T2, T3, TR>, Func<T1, T2, T3, TR>> f)
    {
    return (x, y, z) => f(Fix(f))(x, y, z);
    }

  21. 佩恩
    *.*.*.*
    链接

    佩恩 2009-03-26 20:48:00

    《Lua程序设计(第二版)》也有讲到这种尾递归,里边举的例子是迷宫游戏,玩家可以走无限步骤却不会造成溢出,而且代码很简洁。

    没想到C#也有类似概念……

  22. 重典
    *.*.*.*
    链接

    重典 2009-03-26 21:14:00

    快枪赵,脑袋~~~~
    我又被扫盲了
    感谢脑袋感谢枪

  23. 徐少侠
    *.*.*.*
    链接

    徐少侠 2009-03-26 21:43:00

    好文

    学习

    感动啊

    呵呵,和各位比起来很多地方还是差太多了

  24. ildf[未注册用户]
    *.*.*.*
    链接

    ildf[未注册用户] 2009-03-26 22:31:00

    有个疑问:就算是使用尾递归,调用递归函数时仍然是存在参数传递和函数调用开销的,这样就会在栈上分配空间,如果是无限递归还是会造成栈溢出哦。

  25. JimLiu
    *.*.*.*
    链接

    JimLiu 2009-03-26 22:34:00

    --引用--------------------------------------------------
    佩恩: 《Lua程序设计(第二版)》也有讲到这种尾递归,里边举的例子是迷宫游戏,玩家可以走无限步骤却不会造成溢出,而且代码很简洁。

    没想到C#也有类似概念……
    --------------------------------------------------------
    嗯,Lambda表达式的出现(其实匿名委托就已经有那么点意思)让C#有了很多函数式编程的影子,起码可以稍微体会那么一点点Functional的感觉。

  26. 老赵
    admin
    链接

    老赵 2009-03-26 22:37:00

    --引用--------------------------------------------------
    ildf: 有个疑问:就算是使用尾递归,调用递归函数时仍然是存在参数传递和函数调用开销的,这样就会在栈上分配空间,如果是无限递归还是会造成栈溢出哦。
    --------------------------------------------------------
    每次只要在栈上保留当前调用方法的参数传递等开销,就像第一次调用方法而已,不需要像普通递归那样会积累之前的方法调用数据,越积越多。

  27. weldon
    *.*.*.*
    链接

    weldon 2009-03-26 22:37:00

    顶啊~~

  28. 老赵
    admin
    链接

    老赵 2009-03-26 22:37:00

    @JimLiu
    嗯,C# 3.0引入了函数式编程的部分特性,很多东西变得有意思起来。

  29. Hr
    *.*.*.*
    链接

    Hr 2009-03-26 22:52:00

    我觉得24楼说的应该是有道理的,只要是递归,本身就存在一个调用堆栈,所谓的调用堆栈是指调用另外一个函数的时候会存在一个返回地址放在栈上,不然当函数执行完毕后cpu怎么知道该返回到哪里继续执行呢,这个时候就是靠栈上的返回地址来完成的,另外调用参数为传值方式的时候还会继续复制一份参数拷贝在栈上,只要函数在不断的调用自身或者是其它的函数,本身还没有返回的话都会一直在栈上压入参数,地址等,我认为如果是次数很多的递归还是会溢出的,这个还是要预估一下的,关于这方面在汇编教程里的递归调用堆栈图已经描述的很清楚了.

  30. 王德水
    *.*.*.*
    链接

    王德水 2009-03-26 22:59:00

    @Jeffrey Zhao
    每次看完你的文章,对自己走编程这条路越来越没信心呀。

  31. 老赵
    admin
    链接

    老赵 2009-03-26 23:22:00

    @Hr
    建议您看一下尾递归的资料,优化过的尾递归是不会积累任何数据的,打个比方,阶乘:
    int Fac(n, acc) { return Fac(n - 1, acc * n); } // 省略递归出口

    void Main()
    {
      Fib(5, 1);
    }

    调用时会执行到Fib(4, 5),此时Main方法调用Fib(5, 1)时所在堆栈上累积起来的信息会全部消除(因为已经不需要之前的任何信息了),就相当直接在Main方法里调用了:
    void Main()
    {
      Fib(4, 5);
    }

    因此,尾递归不会对堆栈有任何积累。
    如果您还是无法理解的话,那么我就再用汇编进行解释,呵呵。

  32. 老赵
    admin
    链接

    老赵 2009-03-26 23:41:00

    --引用--------------------------------------------------
    王德水: @Jeffrey Zhao
    每次看完你的文章,对自己走编程这条路越来越没信心呀。
    --------------------------------------------------------
    为什么不是觉得编程是一件很有趣的事情?

  33. Hr
    *.*.*.*
    链接

    Hr 2009-03-26 23:47:00

    老赵,在我的意识里面尾递归确实消除了堆栈上的信息,但是我认为次数较多的递归是存在调用返回ip在栈上的,在fib(4,5)未返回之前那些之前的递归调用返回地址是不能被清除的,因此我做了以下实验,我用的是delphi,不要笑俺哈:)

    function Fac(const n: integer): integer; 也就是所谓的无限递归
    begin
    Result := Fac(n + 1);
    end;

    然后直接运行fac(1);

    过了一会便报堆栈溢出了,这样我更加认定了我所想的,我也顺便查了一下资料,最后我总结的是 "普通的递归相对于尾递归更加耗费栈资源",老赵有时间的话再给我解释解释吧,谢谢.

  34. 老赵
    admin
    链接

    老赵 2009-03-26 23:53:00

    @Hr
    不经过优化的尾递归当然还是会溢出的,我说的是经过优化的啊。尾递归可以优化,普通递归没法自动优化。
    是否会积累和递归次数有没有关系,如果调用1次或10次不会积累,那么调用10000次也不会有积累啊。
    你应该去看一下我在文章里给出的链接,它们已经说得很清楚了,而且业界都已经有各种实现了。
    咋就想不明白呢?看来我还是一定要解释到无比程度才行……

  35. Hr
    *.*.*.*
    链接

    Hr 2009-03-26 23:54:00

    我找到了一点资料,原来这样的程序是被编译器优化成了一种循环,所以才不会产生栈溢出的情况,.

    http://www.kuqin.com/developtool/20080525/8909.html

  36. Hr
    *.*.*.*
    链接

    Hr 2009-03-26 23:56:00

    --引用--------------------------------------------------
    Jeffrey Zhao: @Hr
    不经过优化的尾递归当然还是会溢出的,我说的是经过优化的啊。尾递归可以优化,普通递归没法自动优化。
    你应该去看一下我在文章里给出的链接,它们已经说得很清楚了。
    看来我一定要解释到无比程度才行了……
    --------------------------------------------------------
    呵呵, 没看到你写的注1,因为在最后哈哈,sorry,sorry, 这样就符合情理了,不然我实在无法理解 :)

  37. 老赵
    admin
    链接

    老赵 2009-03-26 23:56:00

    --引用--------------------------------------------------
    Hr: 我找到了一点资料,原来这样的程序是被编译器优化成了一种循环,所以才不会产生栈溢出的情况。
    --------------------------------------------------------
    循环是一种优化方式,消除堆栈的递归是另外一种。

  38. 老赵
    admin
    链接

    老赵 2009-03-26 23:58:00

    @Hr
    文章里也写了,注1只是说C#没有优化而已。
    估计你还是理解错了……优化的方式并非只是改成循环而已。

  39. Hr
    *.*.*.*
    链接

    Hr 2009-03-27 00:03:00

    恩,可能我现在暂时还不能理解,我会继续查一下资料,并把它弄明白,宁可被骂我也不要装懂, 我会继续向你讨教,希望能不厌其烦我这个理解力差的人 :(

  40. 老赵
    admin
    链接

    老赵 2009-03-27 00:07:00

    --引用--------------------------------------------------
    Hr: 恩,可能我现在暂时还不能理解,我会继续查一下资料,并把它弄明白,宁可被骂我也不要装懂, 我会继续向你讨教,希望能不厌其烦我这个理解力差的人 :(
    --------------------------------------------------------
    我能找到又一个感兴趣的人已经不容易了,呵呵,而且你的理解能力肯定不会比我差的……

  41. Hr
    *.*.*.*
    链接

    Hr 2009-03-27 00:13:00

    我知道你很早以前用过DELPHI,敢问DELPHI可以实现尾递归吗?

  42. 老赵
    admin
    链接

    老赵 2009-03-27 00:19:00

    @Hr
    用Delphi是快10年前的事情了,当时还不了解尾递归……后来就没有关心过了。

  43. Colin Han
    *.*.*.*
    链接

    Colin Han 2009-03-27 00:37:00

    呵呵,当我看到“注一”的时候真的有点想骂娘了。:)
    确实对于读者是一个误导。 哈哈,不管怎样,确实是一篇好文章。又被扫盲了。

  44. 老赵
    admin
    链接

    老赵 2009-03-27 00:40:00

    --引用--------------------------------------------------
    Colin Han: 呵呵,当我看到“注一”的时候真的有点想骂娘了。:)
    确实对于读者是一个误导。 哈哈,不管怎样,确实是一篇好文章。又被扫盲了。
    --------------------------------------------------------
    我本来就是在讲尾递归,只不过用C#实现了而已,C#是否真正优化了无所谓啊,我只是在讲一个理论而已,呵呵。

  45. 5995[未注册用户]
    *.*.*.*
    链接

    5995[未注册用户] 2009-03-27 01:03:00

    很整齐啊
    收藏一下 懒得登陆了

  46. Hr
    *.*.*.*
    链接

    Hr 2009-03-27 03:43:00

    老赵,我看了一些资料,总算有点头目了,放在最后一句写调用自己,这样就不用再保存调用者EIP,在最终2进制实现层面上,一种是优化成了循环,一种是自己调用自身的语句不再使用Call来执行,而是使用jmp跳转,并把此次方法中的所有使用临时的局部变量占用的栈空间清除,因为它们没有任何用处了,从而消除了压入返回地址到栈中的机制[在我看来这也是循环:)],最终的结果可以直接绕过调用者返回给原始调用者也就是调用者的调用者,只有这样我才能画的出执行序列栈图.

    另外尾递归不是说不使用栈,而是在调用到自身的那句代码时候就可以释放临时变量占用的栈空间了,因为它们没有任何价值了,此时既不压入返回EIP,又消除了临时变量的栈,及时的返还了空间,所以栈上不会继续递增的使用空间,所以也不会产生栈溢出的现象.

    请问老赵这样理解是否正确了? 谢谢你的这篇文章.

    不过我的D7编译器无法做这样的优化,也就是说无论怎么写都是会栈溢出的.

  47. 幸存者
    *.*.*.*
    链接

    幸存者 2009-03-27 05:57:00

    3楼的性能问题估计是f(x-1)和f(x-2)里有大量重复计算,用传统递归方式实现斐波纳契数列时会有这个问题,下图摘自SICP网上电子书
    http://mitpress.mit.edu/sicp/full-text/book/ch1-Z-G-13.gif
    可以发现其中有很多子树都是相同的,说明进行了重复计算

  48. edfg5233[未注册用户]
    *.*.*.*
    链接

    edfg5233[未注册用户] 2009-03-27 06:33:00

    看不懂

  49. hoodlum1980
    *.*.*.*
    链接

    hoodlum1980 2009-03-27 07:20:00

    注1:事实上,在C#中,即使您实现了尾递归,编译器(包括C#编译器及JIT)也不会进行优化,也就是说还是无法避免StackOverflowException。老赵会在不久之后单独讨论一下这方面问题。
    =====================================
    从你举的例子来看,我思考了一下,如果编译器原样翻译代码,实际上第二种的“尾递归”和第一种递归就没什么太大区别,第一种方法中也就是对累加器进行了一次加法操作,代码上的操作只是时间增加少许而已(复杂度不变),而对栈空间如果还是层层调用到最深一层然后再回归的话,那么对栈空间不但没减少,反而是增加了负担,因为第二种方法的参数量比第一个大。(除非编译器做彻底的颠覆式的重翻译优化,这个我就不太清楚)

    ===
    循环可以等效写成递归函数的形式,因为本质上都是同一段代码的反复执行。
    由于栈很小,无法承受太深的递归消耗,所以递归函数又可以用分配在其他位置的更大的“辅助栈”改写为非递归函数。
    栈中的数据本质上是“代码”执行前后的context。

  50. 老赵
    admin
    链接

    老赵 2009-03-27 09:08:00

    @Hr
    差不多,但是我觉得最好还是不要认为这是循环,比如阶乘这样简单的通过累加器的递归可以轻易优化成循环,但是如果是带Continuation的,那么变成循环就要保留大量Continuation函数。那就又“优化”成了普通手写的递归转非递归,这编译器似乎还是很难做到的。当然你非要理解为转成循环……我也不知道可不可以。
    至于你说的“另外尾递归不是说不使用栈,而是在调用到自身的那句代码时候就可以释放临时变量占用的栈空间了,因为它们没有任何价值了,此时既不压入返回EIP,又消除了临时变量的栈,及时的返还了空间,所以栈上不会继续递增的使用空间,所以也不会产生栈溢出的现象. ”我觉得是没有问题的,我一直就是这个意思。

  51. 老赵
    admin
    链接

    老赵 2009-03-27 09:10:00

    @hoodlum1980
    嗯,这个就类似于Continuation的做法

  52. 装配脑袋
    *.*.*.*
    链接

    装配脑袋 2009-03-27 09:17:00

    有时,我怀疑CLR的尾递归检测和优化并不会阻止栈溢出,只不过把这件事看成可以事先预测的…… 未经证实。

  53. 老赵
    admin
    链接

    老赵 2009-03-27 09:22:00

    @装配脑袋
    脑袋证实一下吧,不过C#是不会被优化的,所以我觉得也说明JIT也不会被优化。网上找到一些说法,还未细看。似乎说是64bit jit和gen后的代码,是有优化的。

  54. 装配脑袋
    *.*.*.*
    链接

    装配脑袋 2009-03-27 09:35:00

    在64位Windows 7 BETA上试验,当Platform是AnyCPU时,递归10000次就会溢出。是x64时递归10000次不会溢出,但递归100000次还是栈溢出了。不管AnyCPU还是x64都是按64位程序运行的。

    程序是简单的求连加和递归,声明4个巨大的decimal在本地栈上浪费空间。

  55. 老赵
    admin
    链接

    老赵 2009-03-27 09:36:00

    @装配脑袋
    我还没有验证,有机会我仔细看看那些文章。

  56. 装配脑袋
    *.*.*.*
    链接

    装配脑袋 2009-03-27 09:40:00

    实验结果对VB和C#相同,说明无需语言干预。

  57. 老赵
    admin
    链接

    老赵 2009-03-27 09:43:00

    @装配脑袋
    总有人要作优化——要么语言编译器直接优化IL(应该是没有),要么JIT优化IL,不过看上去都没有。

  58. 老赵
    admin
    链接

    老赵 2009-03-27 09:43:00

    --引用--------------------------------------------------
    装配脑袋: 实验结果对VB和C#相同,说明无需语言干预。
    --------------------------------------------------------
    对了,F#应该是优化的,所有的函数式编程语言都应该优化了——虽然F#也可以按照命令式编程,但是函数式也占了相当大的比例。

  59. ildf[未注册用户]
    *.*.*.*
    链接

    ildf[未注册用户] 2009-03-27 10:05:00

    明白了,尾递归的实现原理,就是递归调用时重用当前的函数调用栈空间,与传统函数调用的压栈方式不同,需要经过编译器的优化才能实现。
    和hr一样,也是因为没有看到注1造成的理解偏差。

  60. 老赵
    admin
    链接

    老赵 2009-03-27 10:09:00

    @ildf
    难道都没有看到文章里的“优化”,呵呵……

  61. 装配脑袋
    *.*.*.*
    链接

    装配脑袋 2009-03-27 10:15:00

    按理说,函数式语言应该是没有调用栈的,函数式语言的函数可以按某个规则展开和归约。所以尾递归就可以和命令式语言的循环一样进行。

  62. 老赵
    admin
    链接

    老赵 2009-03-27 10:28:00

    @装配脑袋
    我不知道函数式语言的演变,和其编译器的实现是不是一回事情。
    我觉得在老冯的体系上,最自然的就是命令式的编程,其中call一个方法也是指令里最常用的,所以函数式的语言真用了调用栈也不足为奇……

  63. PureEviL
    *.*.*.*
    链接

    PureEviL 2009-03-27 10:38:00

    "尾递归可以用goto来消除递归", 所以既然已经优化成尾递归了,就多作一步把递归消除了吧:)

  64. Indigo Dai
    *.*.*.*
    链接

    Indigo Dai 2009-03-27 10:53:00

    一开始我始终一开始,真是没法理解尾递归不要会造成栈溢出,怎么想都想不通,调用方法都没有执行完,怎么关于此方法的堆栈信息就pop掉了。
    所以如果不会溢出,那肯定编译器形成了公约,认为遇到尾递归调用,就可以pop掉当前方法有关的堆栈信息,然后去执行被调用的方法(自身)。
    开始从没关注过这方面的问题,但是看到老赵文章理解不透彻,就不罢休。理解不深,感觉是个累赘,非要追根究底算不算是个恶习?!
    从命令式编程到函数式编程,感觉是要经历一个很大的思维转换。不过看了那些有关lambda形式的有关文献,感觉命令式编程前途真是一片光明啊。
    在文中,让我觉得老赵的编程和抽象思维能力让我佩服。

  65. Indigo Dai
    *.*.*.*
    链接

    Indigo Dai 2009-03-27 10:58:00

    一开始我始终一开始,真是没法理解尾递归不要会造成栈溢出,怎么想都想不通,调用方法都没有执行完,怎么关于此方法的堆栈信息就pop掉了。
    所以如果不会溢出,那肯定编译器形成了公约,认为遇到尾递归调用,就可以pop掉当前方法有关的堆栈信息,然后去执行被调用的方法(自身)。
    开始从没关注过这方面的问题,但是看到老赵文章理解不透彻,就不罢休。理解不深,感觉是个累赘,非要追根究底算不算是个恶习?!
    从命令式编程到函数式编程,感觉是要经历一个很大的思维转换。不过看了那些有关lambda形式的有关文献,感觉命令式编程前途真是一片光明啊。
    在文中,老赵的编程和抽象思维能力让我佩服。

  66. Hr
    *.*.*.*
    链接

    Hr 2009-03-27 11:05:00

    --引用--------------------------------------------------
    Indigo Dai: 一开始我始终一开始,真是没法理解尾递归不要会造成栈溢出,怎么想都想不通,调用方法都没有执行完,怎么关于此方法的堆栈信息就pop掉了。
    所以如果不会溢出,那肯定编译器形成了公约,认为遇到尾递归调用,就可以pop掉当前方法有关的堆栈信息,然后去执行被调用的方法(自身)。
    开始从没关注过这方面的问题,但是看到老赵文章理解不透彻,就不罢休。理解不深,感觉是个累赘,非要追根究底算不算是个恶习?!
    从命令式编程到函数式编程,感觉是要经历一个很大的思维转换。不过看了那些有关lambda形式的有关文献,感觉命令式编程前途真是一片光明啊。
    在文中,老赵的编程和抽象思维能力让我佩服。
    --------------------------------------------------------
    确实不能用命令式的过程调用方式来看待函数式编程方式,这正是我一开始不明白为什么不用压入返回的EIP,对于这种概念性问题还是要追根问底才好,我不觉得追根究底是个坏事,不是每个人都可以做到的难道不是吗,一知半解没有用的,不怕被别人说你懂个屁,就怕自己懂的是装懂.

  67. Hr
    *.*.*.*
    链接

    Hr 2009-03-27 11:14:00

    --引用--------------------------------------------------
    装配脑袋: 按理说,函数式语言应该是没有调用栈的,函数式语言的函数可以按某个规则展开和归约。所以尾递归就可以和命令式语言的循环一样进行。
    --------------------------------------------------------
    你的想法正是我之前想的,最终是被展开和归约的,从而在2进制指令体系中变成一种循环,不过这种循环的味道变了,在我看来不是语言上的循环,这仅仅是在编译后的2进制指令上的,任何语言无论怎么高级到最好还是会走到最下面一层,那无非就是一些call,jmp等所以就像老赵说的那样用了call产生调用栈也不足为奇.

  68. 韦恩卑鄙
    *.*.*.*
    链接

    韦恩卑鄙 2009-03-27 11:19:00

    光知道逃避递归的某人继续飘过



    要我说老赵还是把递归和尾递归的il结果拿出来比较 大家才容易有直观认识吧

  69. Indigo Dai
    *.*.*.*
    链接

    Indigo Dai 2009-03-27 11:37:00

    @Hr
    哎,没觉得我说这句话时:"非要追根究底算不算是个恶习?! "是种玩笑的口吻么.

  70. Cesc Shen
    *.*.*.*
    链接

    Cesc Shen 2009-03-27 11:43:00

    菲波纳锲那例子,分别用递归与尾递归方法调用,调用时间相差好多,我想了会,是不是FibonacciRecursively(n - 1) + FibonacciRecursively(n - 2)算法时间为O(n-1)+O(n-2),而FibonacciTailRecursively(n - 1, acc2, acc1 + acc2);算法时间为O(n-1),是这个原因带来的性能差吗?还望指点.


  71. 老赵
    admin
    链接

    老赵 2009-03-27 11:47:00

    --引用--------------------------------------------------
    韦恩卑鄙: 光知道逃避递归的某人继续飘过
    要我说老赵还是把递归和尾递归的il结果拿出来比较 大家才容易有直观认识吧
    --------------------------------------------------------
    我不喜欢用这些东西来说啊,所以你看我讲问题都基本用语言不用IL哗哗贴。
    不过这东西真要说清,IL估计还不够,要用汇编……

  72. Hr
    *.*.*.*
    链接

    Hr 2009-03-27 11:47:00

    --引用--------------------------------------------------
    Indigo Dai: @Hr
    哎,没觉得我说这句话时:&quot;非要追根究底算不算是个恶习?! &quot;是种玩笑的口吻么.
    --------------------------------------------------------
    你说呢,当时脑袋里连你说话口气的样子都貌似出来了 :), 难道不能把它拿出来溜溜吗

  73. 老赵
    admin
    链接

    老赵 2009-03-27 11:48:00

    @Cesc Shen
    原因对了,时间复杂度算错了……

  74. Indigo Dai
    *.*.*.*
    链接

    Indigo Dai 2009-03-27 11:54:00

    老赵用C#来讲Tail Recursion,但是C#编译器却不支持在这方面的栈优化,这有点不像了啊?hoho

  75. Hr
    *.*.*.*
    链接

    Hr 2009-03-27 11:54:00

    --引用--------------------------------------------------
    Jeffrey Zhao: --引用--------------------------------------------------
    韦恩卑鄙: 光知道逃避递归的某人继续飘过
    要我说老赵还是把递归和尾递归的il结果拿出来比较 大家才容易有直观认识吧
    --------------------------------------------------------
    我不喜欢用这些东西来说啊,所以你看我讲问题都基本用语言不用IL哗哗贴。
    不过这东西真要说清,IL估计还不够,要用汇编……
    --------------------------------------------------------
    :( 这句话怎么听着带刺啊 , 老赵,我的错,别太认真啊

  76. Indigo Dai
    *.*.*.*
    链接

    Indigo Dai 2009-03-27 11:55:00

    @Hr
    嗯嗯,我们还是讨论讨论技术方面的问题吧。另外深究不是坏事,赫赫。

  77. 老赵
    admin
    链接

    老赵 2009-03-27 12:02:00

    --引用--------------------------------------------------
    Indigo Dai: 老赵用C#来讲Tail Recursion,但是C#编译器却不支持在这方面的栈优化,这有点不像了啊?hoho
    --------------------------------------------------------
    为什么讲究理论非要有实践才行,我还想用伪代码来讲呢。

  78. 老赵
    admin
    链接

    老赵 2009-03-27 12:03:00

    @Hr
    哪有带刺,我说的是事实,因为C#编译器生成IL时还是在较高的抽象上,关于调用堆栈之类的,还是需要看汇编……

  79. Hr
    *.*.*.*
    链接

    Hr 2009-03-27 12:32:00

    --引用--------------------------------------------------
    Jeffrey Zhao: @Hr
    哪有带刺,我说的是事实,因为C#编译器生成IL时还是在较高的抽象上,关于调用堆栈之类的,还是需要看汇编……
    --------------------------------------------------------
    老赵说的确实是啊,我已经很落伍了,不会.net,在我看来IL确实还是抽象的,最终要理解调用堆栈还是要回到汇编层看,有共同的兴趣话题才会有学医讨教和讨论,谢谢你写的这篇文章.

  80. 韦恩卑鄙
    *.*.*.*
    链接

    韦恩卑鄙 2009-03-27 12:55:00

    因为我对il完全不懂
    所以反倒是很怀疑

    感觉.net的堆和栈 应该是在clr这个级别上的
    虽然很抽象 但是目前讨论的仍然是 clr 中的栈 还没到汇编层平台相关的cpu栈,il分析理应足够了的样子。


    因为不懂 所以质疑会比较多拉嘿嘿


  81. 老赵
    admin
    链接

    老赵 2009-03-27 13:42:00

    @韦恩卑鄙
    clr的栈就是操作系统的栈啊,就像clr线程器其实就是操作系统线程。我们平时说struct分配在栈上,就是指操作系统的栈。
    .net比较特别,有两次编译,都可以优化,IL上可以不优化,但是JIT优化,所以还得看汇编……因为C#编译器没有优化。

  82. DiryBoy
    *.*.*.*
    链接

    DiryBoy 2009-03-27 16:19:00

    貌似F#会用IL的tail指令来优化,MC++会改写成循环来优化,至于JIT有没有优化,不知道了……

  83. 老赵
    admin
    链接

    老赵 2009-03-27 16:22:00

    @DiryBoy
    C#没有编译出tail指令,如果用了tail,那么估计JIT就不优化了——直接翻译。
    我周末研究一下

  84. 张荣华
    *.*.*.*
    链接

    张荣华 2009-03-29 14:09:00

    嗯 学习了 ,关于尾递归是第一次听说,在老赵这里总能长见识。

  85. syuko——驿路梨花
    *.*.*.*
    链接

    syuko——驿路梨花 2009-03-31 09:05:00

    现在有些单位的领导都会要求员工在工作中充分利用自己现有的能力。领导不一定需要自己的员工在工作中太多地提高自己,那样会在短时间内降低工作效率。当需要更复杂、更新的技术时,领导宁愿去招一个成手,而不会选择让自己现有的员工去提升到那个层次。这样就会导致员工淹没在繁重,重复的工作当中,领导也乐意这样做。
    作为员工我们必须在繁重,重复的工作间隙,充分提高自己,就像这篇文章一样(当然我的意思不是说老赵是这样的员工,实际老赵是领导:))。研究尾递归也会会花几个小时,也许会花几个晚上,水平不同所花的时间也不同,当然这些都是我们的休息时间。我们就要充分在工作和自我学习当中找到一个平衡点。不然自己就会不进则退了,就会变成一个30岁左右就做不了程序员的人了。
    能看到这篇文章的人也都是在积极自我提高的人。
    在夹缝中自我提高。
    有感于自己重复的工作而发,无多少引申的意思,大家不要拍砖。

  86. 未登录的怪怪[未注册用户]
    *.*.*.*
    链接

    未登录的怪怪[未注册用户] 2009-04-03 07:08:00

    早就估计类似的内容博客园上也会有人写,结果一直没有...

    没想到最后居然是老赵动的手....

  87. 老赵
    admin
    链接

    老赵 2009-04-03 08:23:00

    @未登录的怪怪
    我和你正好相反,如果我估计也有人会写(但还没有写),那么就会先写掉……

  88. 未登录的怪怪[未注册用户]
    *.*.*.*
    链接

    未登录的怪怪[未注册用户] 2009-04-03 08:33:00

    @Jeffrey Zhao
    不是我想写,是我不想每次想起这个话茬还得去某些我讨厌的网站看我讨厌的人有新的讨论没有...,让我觉得自己像做贼 -___-

    但是我以为是那些比较关注函数式的人会先动手..,既然是你开始的,那你就多写一点带动风气吧哈哈。

  89. 甲乙丙丁
    *.*.*.*
    链接

    甲乙丙丁 2009-04-04 13:37:00

    只在程序员面试宝典里面看到过尾递归的概念

  90. 甲乙丙丁
    *.*.*.*
    链接

    甲乙丙丁 2009-04-04 13:45:00

    GetLengthTailRecursively的递归调用属于方法的最后一个操作 这句话怎么理解?

  91. mikezhuyuan[未注册用户]
    *.*.*.*
    链接

    mikezhuyuan[未注册用户] 2009-04-12 23:17:00

    1. 肯定存在无stackoverflow的尾递归, 就像FibonacciTailRecursively(n - 1, acc2, acc1 + acc2)这类, 不难想象其无需保留stack history的调用情况

    2. Continuation还是太tricky了, 像FactorialContinuation(n - 1, r => continuation(n * r)). 感觉像是一方面用尾递归达到了消stack,一方面在传参中构建了一个类似stack的function chain. f(n*f(n-1*f(..2*f(1)))). 对于functional programming不熟悉, 尚不知其优化细节.

    3. 必然存在无法用尾递归消stack的递归. 如中序遍历二叉. 即使Continuation了, 也会生成'隐性'stack. 否则Continuation早就是主流技术 人人皆知了

  92. 老赵
    admin
    链接

    老赵 2009-04-12 23:59:00

    @mikezhuyuan
    不觉得f(n * f(n - 1)...这种在足够多的情况下也会造成stackoverflow吗?这也是“隐形”stack啊,所以需要特殊指令来消除stack,中续编历二叉树也是可以continuation的。
    还有,没看懂“否则早就是主流技术人人皆知”的原因,难道“可以实现”就是“人人皆知”的充分条件?

  93. CoolCode
    *.*.*.*
    链接

    CoolCode 2009-06-17 13:16:00

    希望老赵能写一篇比较一般递归与尾递归的性能分析文章,谢谢!

  94. 韦恩卑鄙
    *.*.*.*
    链接

    韦恩卑鄙 2009-08-14 17:23:00

    老赵 我最后还是写了一个递归的扩展方法
    自己重复一样的代码腻味了。

    string dir = @"D:\webcast";
    var xx = dir.GetRecursionEnumeratable(s => System.IO.Directory.GetDirectories(s));
    return xx.ToList<string>();

  95. 老赵
    admin
    链接

    老赵 2009-08-15 01:00:00

    @韦恩卑鄙
    好啊,不过这是做什么的阿?

  96. ariestiger[未注册用户]
    *.*.*.*
    链接

    ariestiger[未注册用户] 2009-12-07 17:18:00

    你好,我觉得你这个东西总的来说讲得非常好,但有一点问题,貌似你里面用的不应该叫continuation,应该叫闭包closure吧?我对C#也不是很熟,只是这几天在看,但我对ruby,groovy,javascript,erlang,java这些比较了解,这个尾递归的话,erlang里很简单了,通过匹配程度(可能不应该用这个词啊,就是看参数跟哪个方法更匹配了)来选择调用哪个方法(当然说的是同名,同参数个数)。而你这里面用的continuation在groovy,ruby里,都应该是闭包,我个人在刚开始接触javascript的闭包时也被这个鬼名称搞糊涂过,不过我现在的理解就是,一个匿名方法而已,当然在ruby里可能调调就多一点,什么lambda表达式,什么proc,又叫什么闭包,之间有一点小差别,但说的都是差不多的事,在ruby中,也有一个continuaion的东西,不过那是通过callcc方法产生的,它接受的参数是一个闭包,结果就是把这个闭包转换成了continuation。嗯,当然,这两者是有一定联系的,不然也不可能转换成功,但也应该有些差别吧,不过,我还没深入看,嗯,就这些吧,顶一下,还是学到了不少东西。

  97. 老赵
    admin
    链接

    老赵 2009-12-07 18:05:00

    @ariestiger
    closure和continuation是不冲突的,不是一个层面上的东西。

  98. continuation types
    221.221.209.*
    链接

    continuation types 2010-08-10 23:25:21

    continuation :

    first class continuation

    continuation passing style

    delimited continuations

  99. fanfan
    219.142.46.*
    链接

    fanfan 2010-10-20 11:24:46

    看过LZ和HR的讨论,支持HR. 其它是LZ说的时候不太清楚,让人误解了. 其实可以这么说, 从逻辑上讲,尾递归并不能做到清除前一调用的局部变量,更不可能无限递归. 但现实确实在有些语言上又可以做到, 那只是因为它是编译器优化的结果罢了, 编译器在底层做的优化,自动把尾递归变为重复使用前一调用的相同地址空间,从而保证了不会栈溢出. 尾递归还是相当不错的

  100. sunwork
    58.246.227.*
    链接

    sunwork 2011-04-21 14:35:26

    非常感谢,学习了, 个人归纳一下感觉是:递归转迭代的过程。 另借宝地本人求工作中...

  101. ADA
    210.13.69.*
    链接

    ADA 2011-05-30 18:11:37

    老赵, 不好意思, 要把你的老文章拿来题了....

    在你的结束语中, 你也说了“在C#中,即使您实现了尾递归,编译器(包括C#编译器及JIT)也不会进行优化,也就是说还是无法避免StackOverflowException”

    也就是说, 如果编译器没有对尾递归进行优化的话, 或者对尾递归支持得不太好的话, 使用尾递归还是会出现递归你文章里边说的那些问题。

    我觉得SUN的JVM对尾递归支持得不好, 就拿以下这个例子:

    public static int FibonacciTailRecursively(int n, int acc1, int acc2) {

    if (n == 0) return acc1;
    return FibonacciTailRecursively(n - 1, acc2, acc1 + acc2);
    

    }

    这个是个尾递归, 采用这个尾递归之后的确比传统的递归计算效率块很多, 它比public static int FibonacciRecursively(int n) 快很多, 但还是会出现StackOverflowException的可能, 我这里试了下, 当n=10000的时候, 就会报StackOverflowException异常。。。

    想问下SUN的JVM有对尾递归进行优化吗?

  102. 老赵
    admin
    链接

    老赵 2011-05-31 10:18:51

    @ADA

    所有的JVM都没优化,这是JVM的一个缺陷,等待以后补足了。

  103. frank
    147.243.236.*
    链接

    frank 2012-04-27 15:38:44

    @老赵

    是不是可以这样理解,continuation 和 closure 的区别是前者是为了解决惰性语言的有序求值而产生,而后者是为了解决允许函数访问外部状态的问题产生的?

  104. sufei
    218.28.254.*
    链接

    sufei 2012-09-23 13:40:13

    文章不错转走了,收益了。呵呵。

  105. 链接

    caochao88 2012-10-21 19:28:57

    在erlang里,伪递归非常好用,

    tail-recursion:

    reverse(L) -> reverse_acc(L, []).
    
    reverse_acc([], Acc) -> Acc;
    
    reverse_acc([H|T], Acc) -> reverse_acc(T, [H|Acc]).
    
  106. Ant
    58.247.150.*
    链接

    Ant 2012-12-16 01:42:35

    Ant爬过

    整体思路表示赞同,但个人认为文中关于匿名方法的使用不合理

    public static int FactorialContinuation(int n, Func<int, int> continuation)
    {
        if (n == 0) return continuation(1);
        return FactorialContinuation(n - 1,
            r => continuation(n * r));
    }
    

    每递归一次,新创建的匿名方法内部会引用原匿名方法。 递归次数越多,匿名方法的调用层次也就越深。 效率只会更低。

  107. 老赵
    admin
    链接

    老赵 2012-12-17 16:14:50

    @Ant

    再仔细想想尾递归解决的是什么问题,而不是什么问题。

  108. 飞飞
    112.65.179.*
    链接

    飞飞 2012-12-19 14:25:37

    请教老赵,按照您老的说法^^ 我试验了一下 尾递归,可是怎么还是堆栈溢出了。。。?

    代码如下:

    static void Main(string[] args)
    {
    
        Node head = CreateWithLast(100000,null);
        Console.Write("LastLength:" + GetLengthWithLast(head, 0));
    
    }
    
    public static Node Create(int length)
    {
        Node temp = new Node(0, null);
        for (int i = 0; i < length; i++)
        {
            temp = new Node(i, temp);
        }
        return temp;
    }
    
    
    public static int GetLengthWithLast(Node head, int len)
    {
        if (head == null)
        {
            return len;
        }
        else
        {
            return GetLengthWithLast(head.Next, len + 1);
        }
    }
    

    请您指点一二。。。

  109. 老赵
    admin
    链接

    老赵 2012-12-19 14:57:23

    @飞飞

    没看到文章最后一句话?

  110. 飞飞
    112.65.179.*
    链接

    飞飞 2012-12-19 16:42:28

    谢谢您的点拨。。。的确没看到最后一句话。。。。看到中间部分的时候就看不下去了。。。 因为,我在边看您的文章,边写代码。。。 补充一下 递归创建链表的function。

    public static Node Create(int length, Node next)
    {
        if (length > 0)
        {
            Node temp;
            temp= new Node(length--, Create(length, next));
            return temp;
        }
        else
        {
            return next;
        }
    }
    

    嗯,编译器暂时不支持。。。那估计暂时。。。也不能。。。搞了。。。 于此同时,您的博客确认让我受益匪浅。谢谢,您的分享。^^

  111. 链接

    杰 余 2013-01-03 21:58:58

    另外尾递归不是说不使用栈,而是在调用到自身的那句代码时候就可以释放临时变量占用的栈空间了,因为它们没有任何价值了,此时既不压入返回EIP,又消除了临时变量的栈,及时的返还了空间,所以栈上不会继续递增的使用空间,所以也不会产生栈溢出的现象.

    这个想法,我也比较认同,但是,我认为,它每一次递归都只是像传递公式,知道最后一次才计算。

  112. Dreamer57
    218.17.55.*
    链接

    Dreamer57 2013-08-26 15:52:44

    第一段,如何创建Node的实例?

  113. 小菜
    183.62.238.*
    链接

    小菜 2014-03-08 11:16:09

    老赵,还是没弄懂尾递归。递归加载Tree怎样改成尾递归呢? public static void TreeRecursively(List ts, int? parentId) { foreach (var item in ts.Where(t => t.ParentId == parentId)) { Console.WriteLine(item.Id + "--" + item.ParentId); TreeRecursively(ts, item.Id); } }

    有循环的怎么改成尾递归?

  114. gaines
    222.129.46.*
    链接

    gaines 2014-12-03 22:16:16

    我这有段sml程序,实现了命题求真。采用 continuation。 结果总是不对,哪位大侠可以指点? 下面是code:

    (* Skeleton file for Assignment 6, Problem 4 ) ( Derived from code by Chris Stone *)

    exception Unimplemented

    (* An implementation of environments ) type 'a env = string -> 'a option ( env is function, string -> bool ) val empty = fn _ => NONE ( function ) fun lookup (f, x) = f x ( asn id ) fun extend (f, k : string, x) = ( asn, id, true ) fn k' => if (k=k') then SOME x else f k' (the return of extend is a function with argument k' *)

    datatype prop = Var of string | Or of prop * prop | And of prop * prop | If of prop * prop | Not of prop

    type assignment = bool env (* assignment is env , that is string -> bool *)

    (* satisfy: prop * assignment * (assignment -> bool) -> bool

    "satisfy(p, asn, k)" checks whether there is an assignment
    of booleans to variables that: 
      (a) makes proposition p true
      (b) agrees with the given assignment asn 
          (i.e., doesn't change any values already appearing in asn) 
      (c) makes the continuation k return true.
    
    Note that in this version, we are just checking whether
    an assignment exists or not.  (If you're bored, you might
    consider how you'd rewrite the code so that you could
    get out the satisfying assignment.)
    

    *)

    (* at beginning, asn is empty, k is fn _ => true *)

    fun satisfy (Var v, asn, k) = (* k is the continuatin function *) (case lookup (asn, v) of
    NONE => SOME (extend (asn, v, true))

    | SOME true  => SOME asn 
    
      | SOME false => NONE )     (*for satisfy, *)
    

    | satisfy (And(p1,p2), asn, k) = (case satisfy(p1, asn,k) of SOME asn2 => satisfy(p2, asn2, k)

    | NONE => NONE 
    )
    

    | satisfy (Or(p1, p2), asn, k) =

    (case satisfy(p1, asn, k) of
         SOME asn2  =>   SOME asn2 
         | NONE => satisfy(p2, asn,k)  
       )
    

    | satisfy (Not p, asn, k) = falsify(p, asn, k)

    | satisfy (If(p1, p2), asn, k) = satisfy(Or(Not p1, p2), asn, k)

    (* falsify: prop * assignment * (assignment -> bool) -> bool Just like satisfy except we are looking for an assignment that makes the given proposition false. *) and falsify (Var v, asn, k) = (case lookup (asn, v) of NONE => SOME (extend (asn, v, false))

    | SOME false  => SOME asn 
      | SOME true => NONE )
    

    | falsify (And(p1,p2), asn, k) = (case falsify(p1, asn,k) of SOME asnn => falsify(p2, asnn, k) | NONE => NONE )

    | falsify (Or(p1, p2), asn, k) = (case falsify(p1, asn, k) of SOME asnn => SOME asnn | NONE => falsify(p2, asn,k))

    | falsify (Not p, asn, k) =
    satisfy(p, asn, k)

    | falsify (If(p1, p2), asn, k) = falsify(Or(Not p1, p2), asn, k)

    (* satisfiable: prop -> bool falsifiable: prop -> bool valid: prop -> bool.

    Determine whether the given proposition is satisfiable, falsifiable, or valid. Valid is easy, since validity means cannot-be-falsified. ) fun satisfiable p = satisfy(p, empty, fn _ => true) fun falsifiable p = falsify(p, empty, fn _ => true) (fun valid(p) = not (falsifiable p)*)

    (* Two test inputs. You should definitely come up with your own tests as well. *)

    val P = Var "p" val Q = Var "q" val R = Var "r"

    val test1 = And(Or(P,Q), Not(P))

    val test2 = If(And(And(Or(P,Q), If(P,R)), If(Q,R)), R) val test3 = Not(And(Or(P,Q), Not(P)))

发表回复

登录 / 登录并记住我 ,登陆后便可删除或修改已发表的评论 (请注意保留评论内容)

昵称:(必填)

邮箱:(必填,仅用于Gavatar

主页:(可选)

评论内容(大于5个字符):

  1. Your Name yyyy-MM-dd HH:mm:ss

使用Live Messenger联系我