В настоящее время я читаю Simon Thompson The Craft of Functional Programming, а при описании рекурсии он также упоминает форму рекурсии, называемую примитивной рекурсией.
Не могли бы вы объяснить, как этот тип рекурсии отличается от "нормальных" рекурсивных функций?
Здесь пример функции примитивной рекурсии (в Haskell):
power2 n
| n == 0 = 1
| n > 0 = 2 * power2(n - 1)
Упрощенный ответ заключается в том, что примитивно-рекурсивные функции - это те, которые определены в терминах других примитивно-рекурсивных функций и рекурсия на структуру натуральных чисел. Естественные числа концептуально выглядят следующим образом:
data Nat
= Zero
| Succ Nat -- Succ is short for 'successor of', i.e. n+1
Это означает, что вы можете их повторить следующим образом:
f Zero = ...
f (Succ n) = ...
Мы можем написать ваш пример как:
power2 Zero = Succ Zero -- (Succ 0) == 1
power2 (Succ n) = 2 * power2 n -- this is allowed because (*) is primitive recursive as well
Композиция примитивно-рекурсивных функций также примитивно рекурсивна.
Другим примером является число Фибоначчи:
fib Zero = Zero
fib (Succ Zero) = (Succ Zero)
fib (Succ [email protected](Succ n' )) = fib n + fib n' -- addition is primitive recursive
Примитивные рекурсивные функции являются естественным ответом (математика) на проблему остановки, лишая силы произвольной неограниченной саморекурсии.
Рассмотрим "злую" функцию
f n
| n is an odd perfect number = true
| otherwise = f n+2
Заканчивается ли f? Вы не можете знать, не решая открытой проблемы о том, существуют ли нечетные совершенные числа. Это способность создавать такие функции, которые затрудняют проблему остановки.
Примитивная рекурсия как конструкция не позволяет вам это делать; дело в том, чтобы запретить "f n + 2" вещь, оставаясь как можно более гибкой - вы не можете примитивно-рекурсивно определить f (n) через f (n + 1).
Обратите внимание, что только потому, что функция не является примитивной рекурсивной, это не означает, что она не заканчивается; Функция Аккермана является каноническим примером.
рекурсивные функции, которые могут быть реализованы только через do, являются примитивными рекурсивными функциями.