Что такое неявная рекурсия?

Question

Что такое неявная рекурсия? Чем он отличается от явной рекурсии?

Answer 1

Я не видел часто используемый термин. Поиск Google обнаружил использование в книге по лямбда-исчислению. Эта книга утверждает следующее:

1. Уравнение, которое претендует на определение, не должно включать в себя то, что определено в правой части. (Я согласен с этим.)

2. Если такое уравнение, как

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

   действительно появляется, мы назовем это "неявной рекурсией" и скажем, что это незаконно. (Я немного сомневаюсь в этом.)

Я не знаю, почему этот термин считается полезным; для меня это просто еще один кусок терминологии. Важно отличить истинное математическое определение от рекурсивного уравнения , которое необходимо решить. Не каждое рекурсивное уравнение имеет полезное или интересное решение; например, хотя факториальная функция является решением для FAC выше, единственное полезное решение для

x = x + 1

означает «нижний», что может означать «неправильный», «неопределенный» или «расхождение».

Я думаю, что строка в учебнике пытается провести различие между «неявной рекурсией» (которую я бы назвал уравнением рекурсии или рекурсивным уравнением) и математическим определением, которое использует явный оператор с фиксированной точкой как комбинатор Y.

Когда речь идет о практических языках программирования, все это обсуждение носит исключительно академический характер. Языки программирования полностью настроены для поддержки «неявной рекурсии», хотя явные комбинаторы с фиксированной точкой также удивительно полезны .

Answer 2

Я слышал термины явный и неявная рекурсия для сравнения определений рекурсивных функций (явных), например:

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

С функциями, которые используют явно рекурсивные функции, такие как fold s и map, (неявные), например:

sum xs = foldr (+) 0 xs