问题标签 [anonymous-recursion]

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

然后，本文详细介绍了如何使用currying和Y-combinator回到 C# 中的“匿名递归”。这很有趣，但恐怕对我的日常编码来说有点复杂。至少在这个时候...

我喜欢自己看东西，所以我打开了 Mono CSharp REPL并输入了那行。没有错误。于是，我进入了fib(8);。令我大吃一惊的是，它奏效了！REPL 回复了21!

我想这可能是 REPL 的一些神奇之处，所以我启动了“vi”，输入以下程序并编译它。

它也完美地构建和运行！

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

这是否也已在 .NET 上得到修复，或者这是 Mono 的静默功能？这篇文章是几年前的。

如果它只是 Mono，我等不及下一次工作面试，他们要求我用我选择的语言（Mono C#）编写一个 Fibinocci 函数，我必须提供警告，即 .NET 将无法工作。好吧，其实我可以等，因为我热爱我的工作。不过，有趣的是...

更新：

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

对于所有纳粹采访：

可以替换为迭代版本：

您可能希望这样做，因为递归版本在 C# 等语言中效率低下。有些人可能会建议使用记忆，但由于这仍然比迭代方法慢，他们可能只是个傻瓜。:-)

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

将方法体中定义的阶乘函数视为 lambda 表达式并分配给变量：

这失败了，因为它还factfail没有被局部变量绑定。

有没有办法添加一种固定点 - 通过对函数本身进行抽象？！

长话短说：我需要编写一个具有改变某些外部状态的副作用的递归函数。因此，我试图将该方法编写为捕获该外部状态的 lambda 表达式。

我仍在尝试使用不同的样式来编写它，并且 - 除了对所有递归调用都需要相同的那本字典之外 - 我希望尽可能地具有纯粹的功能性和惰性。

所以我在玩 LINQ，因为它可以帮助我减少相互数据。它还有助于理解代码的哪些部分可以以函数式样式表示。

简而言之，在 LINQ 语句中，能够在前面定义一些辅助函数很有帮助，我通过将 lambda 表达式绑定到变量来做到这一点。

并且使用 lamda 表达式，我还可以捕获我的字典，而无需显式地将其引用传递给该方法，这非常好。

不确定我是否走在正确的轨道上...

可能的重复：
javascript：递归匿名函数？
匿名递归 PHP 函数

我想知道......是否可以使用匿名函数进行递归？

下面是一个例子：我需要得到可能只包含数字和空格的六字符长字符串。唯一的规则是它不能以空格开头或结尾。我们检查它，如果发生这种情况 - 只需在相同的匿名函数上调用递归。究竟如何！？

我在一个 Scheme 类中，我很好奇在不使用定义的情况下编写递归函数。当然，主要问题是，如果函数没有名称，则不能在其内部调用函数。

我确实找到了这个例子：它是一个只使用 lambda 的阶乘生成器。

但我什至无法理解第一次调用，(lambda (x) (xx))：这到底是做什么的？你在哪里输入你想要得到阶乘的值？

这不是为了上课，这只是出于好奇。

注意：这是一种家庭作业，有点不是——最终目标是让一个函数产生一组数字的幂集，作为数字列表提供给函数。我有该函数的递归版本，但我现在需要找到一些方法，用等效的 lambda-only 表达式替换我拥有的解决方案（等）append中的每个显式递归函数。mapm

因此，我从较小的问题开始，并希望将它们全部结合起来编写一个完整的函数。我已经设法使用纯 lambda（Y 组合器）提出了一个非递归阶乘函数，但我现在正试图提出一个很好的函数，它将列表中的每个数字平方 - 尝试在跳跃之前解决较小的问题最多一个乘法递归函数：

上面的代码不会递归，尽管它之前存在 Y 组合器——我显然在将正确的参数传递给其中的函数时遇到了一些问题——有什么想法吗？

我试图解决最大子序列和问题并提出了一个neato解决方案

您调用包装函数msss，然后调用f，这反过来又实际完成了工作。解决方案很好，而且 afaik 工作正常。如果由于某种原因我必须解决生产代码中的最大子序列和问题，那我就是这样做的。

然而，这个包装函数真的让我很烦。我喜欢在 haskell 中的方式，如果你足够坚持，你可以在一行上编写你的整个程序，真正让人们明白程序几乎只是一个大表达式。所以我想我会尝试消除包装函数来应对额外的挑战。

现在我遇到了经典问题：如何进行匿名递归？当你不能给函数命名时，你如何进行递归？值得庆幸的是，计算之父很久以前就通过发现定点组合器解决了这个问题，其中最受欢迎的是Y 组合器。

我已经进行了各种尝试来设置 Y 组合器，但它们无法通过编译器。

只是给

改变从 只是f (y y f)给f (y f)

我已经尝试通过仅在外部定义组合器来采用不同的方法，但这仍然不起作用，并且并没有真正满足我在一个表达式中完成它的挑战。

你能看出我在做什么有什么问题吗？我不知所措。对构造无限类型的抱怨真的让我很生气，因为我认为 Haskell 就是这样的事情。它有无限的数据结构，那么为什么会有无限类型的问题呢？我怀疑这与显示无类型 lambda 演算不一致的悖论有关。不过我不确定。如果有人能澄清一下就好了。

另外，我的印象是递归总是可以用折叠函数来表示。谁能告诉我如何仅使用折叠来做到这一点？尽管如此，代码是单个表达式的要求仍然存在。

下面是匿名递归的函数和测试。第一个是真正的Y-combinator，看起来很简单，但是很慢。执行 100 万次迭代需要 1000 毫秒。由于 c(c,item) 的原因，第二个非常难看，但比第一个快两倍。

我需要让我的代码更简单、更灵活、更稳定（如果我需要递归调用，不要创建一组函数等）。

有没有更好的方法来组织匿名递归？

我正在使用递归函数在树中转换我的菜单。我从数据库中得到的数组是：

我通过将上述数组传递给该函数来调用递归函数：

现在，如果我die();在此功能之后使用它会显示正确的菜单，并且如果不使用die();页面将无法加载并给出此错误：

内容编码错误您尝试查看的页面无法显示，因为它使用了无效或不受支持的压缩形式。”

...并且没有显示输出。这是我的递归函数：

我花了一天时间阅读The Little Schemerlength≤1一书中的第 166 页；有以下代码：

其中lis(apples)和eternityis 如下：

第 166 页（第 4 版）指出：

当我们申请mk-length一次时，我们得到length≤1

进而

我们可以多次这样做吗？

但我不知道如何做到这一点length≤2？

我一直在研究禁止 use-before-def 并且没有可变单元格（no set!or setq）的语言如何提供递归。我当然遇到了（著名的？臭名昭著的？）Y 组合器和朋友，例如：

• http://www.ece.uc.edu/~franco/C511/html/Scheme/ycomb.html
• http://okmij.org/ftp/Computation/fixed-point-combinators.html
• http://www.angelfire.com/tx4/cus/combinator/birds.html
• http://en.wikipedia.org/wiki/Fixed-point_combinator

当我以这种风格实现“letrec”语义时（也就是说，允许定义一个局部变量，使其可以是一个递归函数，在幕后它永远不会引用它自己的名字），组合器我最终写成这样：

或者，分解出 U 组合子：

将其读作： Y_letrec 是一个函数，它接受一个待递归函数f。 f必须是一个接受的单参数函数s，其中s是f可以调用实现自递归的函数。f预计将定义并返回执行“真实”操作的“内部”函数。该内部函数接受参数a（或者在一般情况下是参数列表，但不能用传统符号表示）。调用 Y_letrec 的结果是调用的结果 f，并且它被假定为一个“内部”函数，准备被调用。

我这样设置的原因是我可以直接使用待递归函数的解析树形式，而无需修改，只需在处理 letrec 时在转换过程中围绕它包裹一个额外的函数层。例如，如果原始代码是：

那么转换后的形式将是：

请注意，两者之间的内部函数体是相同的。

我的问题是：

• 我的 Y_letrec 函数常用吗？
• 它有一个公认的名字吗？

注意：上面的第一个链接引用了与“应用顺序 Y 组合器”类似的函数（在“步骤 5”中），尽管我在找到该命名的权威来源时遇到了麻烦。

2013 年 4 月 28 日更新：

我意识到上面定义的 Y_letrec非常接近但不等同于维基百科中定义的 Z 组合子。根据 Wikipedia，Z 组合器和“按值调用 Y 组合器”是同一个东西，看起来这确实是更常被称为“应用顺序 Y 组合器”的东西。

所以，我上面所说的与通常写的应用顺序 Y 组合子不同，但几乎可以肯定它们是相关的。这是我进行比较的方法：

从...开始：

应用内部 U：

应用外部 U：

重命名以匹配 Wikipedia 对 Z 组合子的定义：

将此与维基百科的 Z 组合器进行比较：

显着的区别在于函数f的应用位置。有关系吗？尽管存在这种差异，这两个功能是否等效？