什么是隐式递归？

Question

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

Answer 1

我没见过经常使用的术语.谷歌搜索在一本关于lambda演算的书中揭示了一种用法.那本书的主张如下:

1. 声称是定义的等式不应包括右侧定义的事物.(我同意这一点.)

2. 如果这样的等式,就像

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

   确实出现了,我们称之为"隐式递归",并说它是非法的.(我对此有点怀疑.)

我不知道为什么这个词被认为是有用的; 对我而言,这只是另一个术语.重要的是将真正的数学定义与必须求解的递归方程区分开来.并非每个递归方程都有一个有用或有趣的解决方案; 例如,虽然阶乘函数是上述解决方案FAC,但是唯一有用的解决方案

x = x + 1

是"底部",可能代表"错误"或"未定义"或"分歧".

我认为教科书中的这一行试图区分"隐式递归"(我称之为递归方程或递归方程)和使用显式定点算子(如Y组合子)的数学定义.

谈到实用的编程语言,所有这些讨论都是非常学术性的.编程语言完全设置为支持"隐式递归",尽管显式定点组合器也非常有用.