为什么 F# 和 OCaml（以及可能其他语言）中的函数默认情况下不是递归的？
换句话说，为什么语言设计者们会决定在声明中明确要求您键入 rec，这被认为是一个好主意：
let rec foo ... = ...
为什么不默认给函数递归能力？为什么需要显式使用 rec 关键字？
6个回答
94
原始ML的法国和英国后代做出了不同的选择，并且这些选择已经通过几十年传承到现代变体中。因此，这只是遗留问题，但确实影响了这些语言中的习语。
在法国CAML语言系列（包括OCaml）中，默认情况下函数不是递归的。这个选择使得在这些语言中使用let轻松地替代函数（和变量）定义，因为您可以在新定义的主体内引用先前的定义。F#从OCaml继承了这种语法。
例如，在计算OCaml中序列的Shannon熵时替换函数p：
let shannon fold p =
let p x = p x *. log(p x) /. log 2.0 in
let p t x = t +. p x in
-. fold p 0.0
请注意高阶函数
shannon的参数p在函数体的第一行被另一个p所取代，然后在函数体的第二行又被另一个p所取代。相反，ML语言族中英国的SML分支选择了另一种方式，SML的
fun绑定函数默认是递归的。当大多数函数定义不需要访问其函数名的先前绑定时，这会导致代码更简单。但是，被替换的函数需要使用不同的名称（f1，f2等），这会污染作用域并使意外调用函数的错误“版本”成为可能。现在隐式递归的fun绑定函数和非递归的val绑定函数之间存在差异。Haskell通过将定义限制为纯函数来推断它们之间的依赖关系。这使得玩具示例看起来更简单，但在其他方面代价很大。
请注意Ganesh和Eddie给出的答案是红鲱鱼。他们解释了为什么不能将函数组放在一个巨大的
let rec ... and ...中，因为它会影响类型变量何时泛化。这与SML中默认情况下rec有关，但与OCaml无关。- J D
5
3我认为它们不是故弄玄虚的: 如果没有推理限制，很可能整个程序或模块会自动被视为相互递归，就像大多数其他语言一样。这将使得是否需要"rec"成为具体设计决策变得无意义。 - GS - Apologise to Monica
"...就像大多数其他编程语言一样，自动视为相互递归。但 BASIC、C、C++、Clojure、Erlang、F#、Factor、Forth、Fortran、Groovy、OCaml、Pascal、Smalltalk 和 Standard ML 不会这样处理。" - J D
3仅需要C/C++提供前向定义的原型，这与明确标记递归并无关。Java、C#和Perl肯定具有隐式递归。我们可以就“大多数”语言的含义和每种语言的重要性展开无休止的辩论，所以让我们就“非常多”的其他语言达成一致。 - GS - Apologise to Monica
3在C/C++中，仅需要用原型来进行前向定义，这并不是显式标记递归的关键。只有在自递归的特殊情况下才需要。而在一般的相互递归情况下，无论是C还是C++都需要使用前置声明。 - J D
3实际上，在C++的类作用域中并不需要前向声明，也就是说，静态方法可以相互调用而无需任何声明。 - polkovnikov.ph
55
rec 的显式使用在于 Hindley-Milner 类型推断，该推断是所有静态类型的函数式编程语言的基础（虽然以不同的方式改变和扩展）。如果您定义了 let f x = x，则应该期望其具有类型 'a -> 'a 并且可在不同的 'a 类型上在不同的点上应用。但同样地，如果您编写 let g x = (x + 1) + ...，则希望在 g 的其余部分中将 x 视为 int。
Hindley-Milner 推断处理此区别的方式是通过显式的 泛化 步骤。在处理程序时，在特定的点上，类型系统停止并说“好的，这些定义的类型将在此处泛化，因此当有人使用它们时，它们类型中的任何自由类型变量都将被全新实例化，从而不会干扰此定义的任何其他用途。”事实证明，在检查相互递归的一组函数之后进行此种泛化是合理的。在任何更早的时候，您都将泛化得太多，导致类型实际上可能会发生冲突。如果再晚一些，您将泛化得太少，使得无法使用多个类型实例化的定义。
因此，鉴于类型检查器需要知道哪些定义集是相互递归的，它能做什么呢？一个可能性是对作用域中所有定义进行依赖项分析，并将它们重新排序为最小可能的组。 Haskell 实际上就是这样做的，但是在具有不受限制的副作用的语言（例如 F#、OCaml 和 SML）中，这是一个坏主意，因为它可能会重新排序副作用。因此，它要求用户明确标记哪些定义是相互递归的，从而间接地确定泛化应该发生的位置。
- GS - Apologise to Monica
8
3不，你的第一段话是错误的（你谈论的是“and”的明确使用而非“rec”），因此其余内容都不相关。 - J D
5谢谢解释，但我从未满意这个要求。这是Haskell设计更加优越的另一个原因。 - Bent Rasmussen
9不可能！怎么会这样？这个答案完全错误！请阅读下面的Harrop的答案或查看《标准ML定义》（Milner，Tofte，Harper，MacQueen--1997）[第24页]。 - lambdapower
9正如我在回答中所说，类型推断问题是需要使用rec的原因之一，而不是唯一的原因。Jon的回答也是非常合理的（除了有关Haskell的常规讽刺性评论）; 我认为这两个观点并不矛盾。 - GS - Apologise to Monica
17“类型推导问题是需要使用' rec '的原因之一。” OCaml需要'rec'而SML不需要，这是一个明显的反例。如果像你描述的那样，类型推断是问题的原因，那么OCaml和SML不能像它们所做的那样选择不同的解决方案。当然，原因是你在谈论'and'以使Haskell相关。 - J D
显示剩余3条评论
11
这是个好主意的两个关键原因：
首先，如果启用递归定义，那么就不能引用同名值的先前绑定。当您正在扩展现有模块等操作时，这通常是一种有用的习惯用法。
其次，递归值，尤其是互相递归的值集合，比按顺序进行的定义（每个新定义都建立在已经定义的基础之上）更难理解。阅读这样的代码很好，除了显式标记为递归的定义外，新定义只能引用先前定义。
- zrr
5
一些猜测：
优化非递归函数可能更容易。
创建递归函数时创建的闭包需要包含指向函数本身的条目（以便函数可以递归调用自身），这使得递归闭包比非递归闭包更复杂。因此，当您不需要递归时，创建较简单的非递归闭包可能会很好。
它允许您根据先前定义的同名函数或值来定义一个函数；虽然我认为这是不好的实践。
额外的安全性？确保您正在执行您打算执行的操作。例如，如果您不打算进行递归，但在函数内部意外使用了与函数本身相同的名称，它很可能会抱怨（除非该名称已被定义）。
let 不仅用于绑定函数，还可以绑定其他常规值。大多数形式的值都不允许递归。某些递归形式的值是允许的（例如函数、惰性表达式等），因此需要明确的语法来指示这一点。let 结构类似于 Lisp 和 Scheme 中的 let 结构；它们都是非递归的。Scheme中有一个单独的letrec结构用于递归的let。- newacct
1
大多数形式的值不允许递归。某些形式的递归值是允许的（例如函数、惰性表达式等），因此需要显式语法来指示这一点。这对于F#来说是正确的，但我不确定它对OCaml来说有多少正确，因为你可以使用
let rec xs = 0::ys and ys = 1::xs。 - J D4
鉴于此：
let f x = ... and g y = ...;;
对比：
let f a = f (g a)
有了这个：
let rec f a = f (g a)
前者重新定义f，将先前定义的f应用于将g应用于a的结果。后者重新定义f，无限循环地将g应用于a，这通常不是ML变体中想要的。
话虽如此，这是一种语言设计师的风格问题。就按照它去做吧。
- james woodyatt
1
其中一个重要的部分是它为程序员提供了更多对局部作用域复杂性的控制。
let、let* 和 let rec 的范围提供了不断增加的 power 和 cost。 let* 和 let rec 本质上是简单的 let 的嵌套版本，因此使用任何一个都更加昂贵。这种分级允许您微观管理程序的优化，因为您可以选择针对手头任务需要哪个 let 级别。如果您不需要递归或引用先前的绑定，则可以回退到简单的 let 来节省一些性能。
这类似于 Scheme 中分级相等谓词（即eq?、eqv?和 equal?）。
- Evan Meagher
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接