一些重要的算法
浮点数的二进制表示学习笔记

尾递归与Continuation

marz posted @ Aug 11, 2010 06:16:38 AM in algorithm with tags recursion , 1685 readers

 

 

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

 

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。

 

源文档 <http://blog.201314.info/2010/05/24/%E5%B0%BE%E9%80%92%E5%BD%92%E4%B8%8Econtinuation.html>

  • No match
Small_feed Comments (17)
1
[Reply]
meidir said:
Jan 14, 2023 01:04:01 AM

Thank you for this impressive report. I am refreshed following reading this. Thank you! 카지노사이트

2
[Reply]
meidir said:
Feb 12, 2023 09:39:16 PM

This is my first time i visit here. I found so many informative stuffs on your blog, especially its discussion. Form the tons of comments and posts, I guess I am not the only one having all enjoyment here. Keep up the good work. Macbook Pro

 

 

===========================

 

 

 

Hello i am so delighted I discovered your blog, I actually discovered you by error, while I was searching Yahoo for something else, Anyways I am here now and would just like to say thanks for a great blog posting and a all round absorbing blog (I also love the theme/design), I do not have time to read it all at the right now but I have bookmarked it and also added your RSS feeds, so when I have time I will be back to read more. 여우알바

3
[Reply]
meidir said:
Feb 22, 2023 08:52:38 PM

Also, whatever happened to those vaunted shields that in the television show always protected the ship from harm? In this movie the shields are about as effective as paper-mache as the Enterprise is strafed, bombed, rocketed, smashed, tossed, toppled, and shaken like a baby’s toy. 여우알바

4
[Reply]
meidir said:
Oct 05, 2023 11:21:21 PM

I was recommended this web site by my cousin. I am not sure whether this post is written by him as nobody else know such detailed about my difficulty. You are amazing! Thanks! 花藝設計

5
[Reply]
meidir said:
Dec 09, 2023 03:37:43 PM

There are a couple of interesting points in time on this page but I don’t determine if I see them all center to heart. There exists some validity but I’ll take hold opinion until I consider it further. Great post , thanks and now we want a lot more! Included in FeedBurner at the same time 玫瑰花

 

===================

 

Thanks for the good critique. Me & my friend were just preparing to do a little research about this. We got a book from our area library but I think I’ve learned more from this post. I’m very glad to see such magnificent info being shared freely out there… 開張花籃花牌

 

====================

 

There may be jacksonville florida health insurance a means in making cash not having doing work yourself tired in addition to without having restricting your moment. You need to use the ability on the Online to earn more income and now have any time to truly enjoy it. No matter the way tiny you realize about the Net as well as how much internet business encounter you will have, you possibly can take advantage of the countless incredible opportunities to generate income right on your computer. 訂花推介

 

====================

 

I am curious to find out what blog system you’re working with? I’m experiencing some small security issues with my latest blog and I would like to find something more safeguarded. Do you have any suggestions? 訂花

6
[Reply]
meidir said:
Dec 09, 2023 11:22:42 PM

This will be the correct weblog for really wants to learn about this topic. You are aware of much its nearly challenging to argue with you (not that I actually would want…HaHa). You actually put a new spin on the topic thats been discussing for some time. Fantastic stuff, just great! amazon

7
[Reply]
meidir said:
Dec 27, 2023 02:11:46 AM

Very interesting subject , thanks for putting up. universitas medan

8
[Reply]
meidir said:
Jan 11, 2024 04:41:50 PM

Pretty nice post, thanks for the awesome article. I’m having troubles subscribing to your blogs feed. Thought I’d let you know Agencja marketingowa Gdańsk

 

===================

 

Hi there this is kinda of off topic but I was wondering if bloger use editors or if you have to manually code with HTML. I’m starting a blog soon but have no coding know-how so I wanted to get guidance from someone with experience. Any help would be greatly appreciated! 訂花

 

===================

 

I like the precious information you offer for your articles. I will be able to bookmark your weblog and feature my youngsters check up here generally. I’m somewhat certain they are going to learn numerous new stuff here than anyone else! 訂花推介

 

===================

 

Hey you. I do not know whether it’s acceptable, but this blog is really well designed. 開張花籃花牌

 

===================

 

I’m impressed, I have to admit. Truly rarely will i encounter a blog that’s both educative and entertaining, and without a doubt, you have hit the nail on the head. Your concept is outstanding; the problem is something that too few folks are speaking intelligently about. I’m delighted that we came across this within my seek out some thing relating to this. 玫瑰花

 

===================

 

This is the type of movie that the less you know, the more enjoyable it will be. Seiko King Samurai

 

===================

 

This post something certainly worth reading. There are tons of sites that really make no sense at all. Please keep up the fresh blogging and many more people will keep coming. seiko watch bands

 

===================

 

Youre so cool! I dont suppose Ive read anything such as this just before. So nice to discover somebody with some original ideas on this subject. realy thanks for starting this up. this fabulous website is a thing that is needed on the net, someone after a little originality. beneficial problem for bringing a new challenge on the internet! watch straps

 

===================

 

Hiya. Very cool web site!! Man .. Beautiful .. Superb .. I’ll bookmark your web site and take the feeds also…I’m glad to find a lot of useful info here in the article. Thank you for sharing.. seiko 5 sports gmt

 

===================

 

Hello, you used to write fantastic, but the last few posts have been kinda boring… I miss your tremendous writings. Past few posts are just a bit out of track! come on! 二手電腦

9
[Reply]
meidir said:
Jan 21, 2024 10:29:07 PM

i would love to get some free calendars on the internet, are there are sites or company that gives one?,. AI Workflow Automation Guide

10
[Reply]
meidir said:
Jan 26, 2024 06:33:40 AM

You made some good points there. I did a search on the subject and found most individuals will go along with with your website. FM카지노먹튀

11
[Reply]
meidir said:
Feb 16, 2024 05:35:25 AM

I feel that is among the so much important info for me. And i’m satisfied studying your article. However wanna commentary on some normal things, The site taste is ideal, the articles is actually nice . Good task, cheers. black dollar cleaning machine

 

==============

 

Hi, your blog is full of comments and it is very active,    母親節

 

==============

 

Yes, really. I join told all above. We can communicate on this theme. Here or in PM. 玫瑰花

 

==============

 

Very good written blog. It will be useful to everyone who usess it, including myself. Keep up the good work. 生日訂花

 

==============

 

being a blogger myself , i can see someone with great potential,    法式花藝

 

==============

 

I visited a lot of website but I believe this one has got something extra in it. 手機回收

 

==============

 

There are a few interesting points in time in this posting but I do not determine if I see these people center to heart. There may be some validity but Let me take hold opinion until I take a look at it further. Very good write-up , thanks and we want much more! Included in FeedBurner likewise Seiko King Samurai

 

==============

 

I was just imagine about it and you provided me the correct information I really bookmark it seiko watch bands

 

==============

 

Awsome site! I am loving it!! Will be back later to read some more. I am taking your feeds also watch straps

 

==============

 

An fascinating discussion will be worth comment. I do think that you should write on this topic, it might not often be a taboo subject but generally persons are insufficient to talk on such topics. To the next. Cheers seiko 5 sports gmt

12
[Reply]
meidir said:
Feb 17, 2024 07:01:21 AM

Good info, good to be knowledge and distributed to the public ZLD SYSTEM MANUFACTURER (ZERO LIQUID DISCHARGE SYSTEM)

 

 

=======================

 

 

You ought to be a part of a tournament personally of the most useful blogs over the internet. I’m going to suggest this site! ARSENIC REMOVAL PLANT MANUFACTURER

13
[Reply]
Meidir said:
Mar 20, 2024 03:24:10 PM

Spot i’ll carry on with this write-up, I must say i believe this excellent website requirements far more consideration. I’ll probably be once more to see additional, thank you that information. Download WordPress

14
[Reply]
Meidir said:
Mar 21, 2024 11:26:56 PM

hey there and thank you for your info – I have definitely picked up something new from right here. I did however expertise some technical issues using this website, as I experienced to reload the web site a lot of times previous to I could get it to load correctly. I had been wondering if your web host is OK? Not that I’m complaining, but sluggish loading instances times will very frequently affect your placement in google and could damage your high-quality score if ads and marketing with Adwords. Anyway I’m adding this RSS to my email and can look out for a lot more of your respective interesting content. Ensure that you update this again soon.. 母親節

 

===================

 

puppies and dogs are very cute, i always love to play with them during my spare time’ 玫瑰花

 

===================

 

This is Great. So much good, useful and well written information and entertaining too! I appreciate the time you have spent on this. It is a big help for me. – Thank you! 生日訂花

 

===================

 

Awesome! I thank you your input to this matter. It has been useful. my blog: maple syrup 法式花藝

 

===================

 

I believe there’s a issue with your blog working with Safari internet browser. 回收iphone

 

===================

 

Just as before, you need to alteration your tax bill obligations for anybody who is expected an important substantial return. Seiko King Samurai

 

===================

 

Awesome site! You’ve some quite interesting posts.. Nice background as well haha. Keep up the nice work, Ill make sure to come across to see really your page! seiko watch bands

 

===================

 

I am glad to read this post, it’s an impressive piece. I am always searching for quality posts and articles and this is what I found here, I hope you will be adding more in future. watch straps

 

====================

 

Only wanna say that this is extremely helpful, Thanks for taking your time to write this. seiko 5 sports gmt

15
[Reply]
Meidir said:
Mar 28, 2024 06:46:49 PM

I would like to point out my gratitude for your kind-heartedness in support of women who actually need help with that situation. Your real commitment to passing the solution all through became pretty insightful and has consistently encouraged professionals like me to realize their objectives. Your new useful tips and hints can mean a lot to me and still more to my peers. Thanks a lot; from all of us. Tech

 

 

====================

 

 

evening dresses should always be classy, simple but elegant. you don’t need to invest several hundred bucks on a classy evening dress“ Tech

16
[Reply]
Meidir said:
Mar 31, 2024 03:51:07 AM

Thanks, I’ve recently been searching for info about this subject matter for ages and yours is the best I’ve discovered so far. klub piłkarski

 

 

========================

 

 

Appreciate bothering to talk about this unique, Personally i think eagerly measurements and thus really enjoy figuring out regarding this unique theme. Any time prospects, any time you generate expertise, on earth would you ideas writing your personal web site utilizing even further important information? This is of great help for anyone. Clean black money in Africa

17
[Reply]
Meidir said:
Apr 12, 2024 03:40:09 PM

You actually make it seem so easy along with your presentation however I to find this topic to be actually one thing which I feel I’d by no means understand. It kind of feels too complicated and extremely vast for me. I’m looking forward on your subsequent put up, I will try to get the cling of it! Yep Marketing Agency


Login *


loading captcha image...
(type the code from the image)
or Ctrl+Enter