haskell - 什么是隐式递归？

Question

什么是隐式递归？它与显式递归有何不同？

Answer 1

我没见过经常使用的术语。谷歌搜索揭示了一本关于 lambda 演算的书的用法。那本书的论点如下:

1. 声称是定义的等式不应该包括右边定义的东西。 (我同意这一点。)

2. 如果这样一个等式，比如

   FAC = \n. if n = 0 then 1 else n * FAC (n-1),
   

   确实出现了，我们称它为“隐式递归”并说它是非法的。 (对此我有点怀疑。)

我不知道为什么这个词被认为是有用的；对我来说，这只是另一个术语。重要的是区分真正的数学定义和必须求解的递归方程。并非每个递归方程都有有用或有趣的解；例如，尽管阶乘函数是上面 FAC 的解决方案，但唯一有用的解决方案是

x = x + 1

是“底部”，可能代表“错误”或“未定义”或“分歧”。

我认为教科书中的行试图区分“隐式递归”(我称之为递归方程或递归方程)和使用显式定点运算符 就像 Y 组合器。

当谈到实用的编程语言时，所有这些讨论都非常学术化。尽管 explicit fixed-point combinators are also surprisingly useful 编程语言完全支持“隐式递归” .