“匿名递归”在.NET中有效吗? 它在Mono中

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

Func 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 fib = n => n > 1 ? fib(n - 1) + fib(n - 2) : n; Console.WriteLine(fib(x)); } } 

它也很完美地构建和运行!

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

这是在.NET上修复过的还是Mono的静音function? 这篇文章已经有几年了。

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

更新:

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

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

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

可以用迭代版本替换:

 Func 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但是,因为它仍然比迭代方法慢,所以它们可能只是游荡者。 🙂

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

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

正如我在上面的评论中所指出的,如果Mono这样做,那么他们就会有一个bug。 规范很清楚,这应该被检测为错误。 这个bug当然大部分都是无害的,大部分时间都可以满足您的需求。 我们考虑过改变规则,使这种递归合法化; 基本上我们必须在规范中添加一个特殊情况,说这个狭义的案例是合法的。 但它从来都不是一个足够重要的优先事项。

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

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

顺便说一句,我不会雇用任何在面试中给我直接递归实施fib的人。 效率极低; 它的运行时间与其输出的大小成正比,而fib的指数增长。 为了有效地使用memoization的递归,或实现明显的迭代解决方案。

试试这个…

 Func fib = null; fib = n => n > 1 ? fib(n - 1) + fib(n - 2) : n; 

…问题是当您尝试在上述方法中使用fib时未定义fib,因此静态分析器报告编译器错误。

看来,在我的兴奋中,我从根本上错了。 .NET和Mono都没有像原始文章那样提供“匿名递归”。 你无法将fib作为一个独立的实体传递。

在Mono C#REPL中查看以下序列:

 csharp> Func fib = n => n > 1 ? fib(n - 1) + fib(n - 2) : n; csharp> fibCopy = fib; csharp> fib(6); 8 csharp> fibCopy(6); 8 csharp> fib = n => n * 2; csharp> fib(6); 12 csharp> fibCopy(6); 18 

这是因为:

 fib = n => n * 2; fibCopy = n > 1 ? fib(n - 1) + fib(n - 2) : n; 

换一种说法,

 fibCopy = n > 1 ? (n - 1) * 2 + (n - 2) * 2 : n; // at the moment 

很明显, fibCopy只是指向fib (委托)的当前定义而不是它本身。 所以Mono实际上只是在初始赋值期间为fib预先赋值为null ,因此赋值是有效的。

我更喜欢不必声明null的便利,所以我喜欢这种行为。 不过,这并不是原始文章所说的。

在Microsoft的C#编译器中,只有在第一次将fib设置为null才会起作用。

否则,它会产生错误,因为在分配之前使用了fib
Mono的编译器“足够智能”以避免此错误(换句话说,它违反了官方规范)