"匿名递归"在.NET中有效吗？它在Mono中

Question

几天前我在"C#匿名递归"中浏览了这个网站.本文的主旨是以下代码在C#中不起作用:

Func<int, int> fib = n => n > 1 ? fib(n - 1) + fib(n - 2) : n;

然后,文章详细介绍了如何使用currying和Y-combinator回到C#中的"Anonymous Recursion".这很有趣,但我担心日常编码有点复杂.此时至少......

我喜欢看自己的东西,所以我打开了Mono CSharp REPL并输入了该行.没有错误.所以,我进来了fib(8);.令我非常惊讶的是,它奏效了!REPL回复了21!

我想也许这可能是REPL的一些魔力,所以我点了'vi',输入以下程序,然后编译它.

using System;

public class Program
{
    public static void Main(string[] args)
    {
        int x = int.Parse(args[0]);
        Func<int, int> fib = n => n > 1 ? fib(n - 1) + fib(n - 2) : n;
        Console.WriteLine(fib(x));
    }
}

它也完美地建造和运行!

我在Mac上运行Mono 2.10.我现在无法访问Windows计算机,所以我无法在Windows上的.NET上进行测试.

这是在.NET上修复过的还是Mono的静音功能？这篇文章已经有几年了.

如果它只是单声道,我不能等待下一次面试,他们要求我用我选择的语言(Mono C#)编写Fibinocci函数,我必须提供.NET无法使用的警告.好吧,实际上我可以等,因为我热爱自己的工作.还是有意思......

更新:

Mono并没有真正进行"匿名"递归,因为它正在fib用作命名委托.我的错.Mono C#编译器假定赋值之前的null值fib是一个错误,如下所示.我说"编译器"是因为即使.NET C#编译器无法编译代码,.NET CLR也能正常运行生成的程序集.

对于所有采访纳粹在那里:

Func<int, int> fib = n => n > 1 ? fib(n - 1) + fib(n - 2) : n;

可以用迭代版本替换:

Func<int, int> fib = n => 
{
    int old = 1;
    int current = 1;
    int next;

    for (int i = 2; i < n; i++)
    {
        next = current + old;
        old = current;
        current = next;
    }
    return current;
};

您可能希望这样做,因为递归版本在C#等语言中效率低下.有些人可能会建议使用memoization但是,因为它仍然比迭代方法慢,所以它们可能只是游荡者.:-)

在这一点上,这变得更像是一个功能编程的广告而不是其他任何东西(因为递归版本更好).它与我原来的问题没有任何关系,但有些答案认为这很重要.

Answer 1

正如我在上面的评论中所指出的,如果Mono这样做,那么他们就有一个bug.规范很清楚,这应该被检测为错误.这个bug当然大部分都是无害的,而且大部分时间都是你想要的.我们考虑过改变规则,使这种递归合法化; 基本上我们必须在规范中添加一个特殊情况,说这个狭义的案例是合法的.尽管如此,它从未有过足够高的优先级.

有关此问题的更多想法,请参阅我关于此主题的文章:

http://blogs.msdn.com/b/ericlippert/archive/2006/08/18/706398.aspx

顺便说一下,我不会雇用任何在面试中给我直接递归实施fib的人.这是非常低效的; 它的运行时间与其输出的大小成正比,并且fib呈指数增长.为了有效地使用带有memoization的递归,或者实现明显的迭代解决方案.

Answer 2

这是Mono编译器中的一个错误.它违反了规范的第12.3.3节.变量fib不能在变量初始化程序中使用,因为它没有明确赋值.