“匿名递归”是否有效？在 .NET 中工作？它在 Mono 中是这样的

Question

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

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

然后文章详细介绍了如何使用 柯里化和Y-combinator回到“匿名递归” C#。这很有趣，但恐怕对于我的日常编码来说有点复杂。至少在这一点上...

我喜欢亲眼看到一些东西，所以我打开了 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，我就等不及下一次面试了，他们要求我用我选择的语言 (Mono C#) 编写一个 Fibinocci 函数，我必须警告 .NET 无法工作。好吧，实际上我可以等待，因为我热爱我的工作。不过，有趣的是...

更新：

Mono 并没有真正执行“匿名”递归，因为它使用 fib 作为命名委托。我的不好。事实上，Mono C# 编译器在赋值之前假定 fib 为 null 值，这是一个错误，如下所述。我说“编译器”是因为 .NET CLR 可以很好地运行生成的程序集，即使 .NET C# 编译器不会编译代码。

对于所有纳粹采访：

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# 这样的语言中效率低下。有些人可能建议使用记忆化，但是，由于这仍然比迭代方法慢，他们可能只是是混蛋。 :-)

但在这一点上，这更像是函数式编程的广告而不是其他任何东西（因为递归版本要好得多）。这确实与我原来的问题没有任何关系，但有些答案认为这很重要。

Answer 1

这是 Mono 编译器中的一个错误。它违反了规范的第 §12.3.3 节。变量fib不能在变量初始值设定项中使用，因为它没有明确分配。

Answer 2

正如我在上面的评论中指出的，如果 Mono 这样做，那么他们就有一个错误。规范明确表明这应该被检测为错误。当然，该错误大多是无害的，并且大多数时候都会按照您的意愿行事。我们考虑过改变规则，使这种递归合法化；基本上，我们必须在规范中添加一个特殊情况，表明这种狭义定义的情况是合法的。但它从来都不是一个足够高的优先事项。

有关此问题的更多想法，请参阅我关于该主题的文章：

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

顺便说一句，我不会雇用任何在面试中给我直接递归实现 fib 的人。它极其效率低下；它的运行时间与其输出的大小成正比，并且 fib 呈指数增长。为了使其高效，请使用带有记忆化的递归，或实现明显的迭代解决方案。

Answer 3

试试这个...

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

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

Answer 4

看来，在我的兴奋之中，我从根本上错了。 .NET 和 Mono 都没有按照原始文章的方式提供“匿名递归”。您无法将 fib 作为独立实体进行传递。

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

csharp> Func<int, int> 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 实际上只是在初始赋值期间将 null 值预先分配给 fib，以便赋值有效。

我更喜欢不必声明 null 的便利，因此我确实喜欢这种行为。不过，这并不是原始文章真正讨论的内容。

Answer 5

在 Microsoft 的 C# 编译器中，仅当您首先将 fib 设置为 null 时，它才会起作用。

否则，它会给出错误，因为 fib 在分配之前就被使用了。
Mono的编译器足够“聪明”，可以避免这个错误（换句话说，它违反了官方规范）