5

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

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

然后，本文详细介绍了如何使用currying和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# 编译器假定分配前的null值fib是一个错误，如下所述。我说“编译器”是因为 .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# 等语言中效率低下。有些人可能会建议使用记忆，但由于这仍然比迭代方法慢，他们可能只是个傻瓜。:-)

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

4

5 回答 5

7

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

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

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

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

于 2011-03-30T15:28:52.083 回答
7

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

于 2011-03-30T15:34:40.263 回答
3

试试这个...

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

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

于 2011-03-30T14:56:44.083 回答
1

看来，在我的兴奋中，我从根本上错了。.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 实际上只是在初始分配期间预先分配了nullto的值，fib以便分配有效。

我更喜欢不必声明的便利，null所以我喜欢这种行为。不过，这并不是原始文章真正在谈论的内容。

于 2011-03-30T15:29:34.430 回答
0

在微软的 C# 编译器中，它只有在你首先设置fib为null.

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

于 2011-03-30T14:56:57.233 回答