什么是隐式递归？

Question

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

- StackUnderflow

Answer 1

我很少见到这个术语的使用。在谷歌搜索中找到了一本关于lambda演算的书中使用了这个术语。该书的论点如下：

1. An equation that claims to be a definition should not include the thing defined on the right-hand side. (I agree with this.)

2. If such an equation, like

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

   does show up, we'll call it "implicit recursion" and say it's illegal. (I'm a bit dubious about this.)

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

x = x + 1

"bottom"可能代表"错误"，"未定义"或"发散"。

我认为教科书中的这行是试图区分"隐式递归"(我会称之为递归方程或递归式)和使用显式不动点运算符的数学定义，例如Y组合子。

当涉及实际编程语言时，所有这些讨论都极为学术。编程语言完全支持"隐式递归"，尽管显式不动点组合子也非常有用。

- Norman Ramsey

---

我怀疑原帖作者是编造这个术语的，作为“显式递归”的相反（如其他答案中所述）。 - ShreevatsaR

Answer 2

我听说过显式递归和隐式递归这两个词来对比递归函数定义（显式递归），例如：

sum (x:xs) = x + sum xs
sum [] = 0

使用像fold和map这样显式递归函数的函数，(隐式)例如:

sum xs = foldr (+) 0 xs

- Zoey Hewll

---

是的，在Haskell的非正式交谈中，通常就是这个意思。 - duplode