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

Question

В настоящее время я читаю Ремесло функционального программирования Саймона Томпсона , и при описании рекурсии он также упоминает форму рекурсии под названием Примитивная рекурсия .

Не могли бы вы объяснить, чем этот тип рекурсии отличается от "обычных" рекурсивных функций?

Вот пример примитивной рекурсивной функции (в Haskell):

power2 n
    | n == 0    = 1
    | n > 0     = 2 * power2(n - 1)

Answer 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 n@(Succ n'  )) = fib n + fib n' -- addition is primitive recursive

Answer 2

Примитивно-рекурсивные функции - естественный ответ (математики) на проблему остановки, лишая возможности совершать произвольную неограниченную саморекурсию.

Рассмотрим "злую" функцию

f n
  | n is an odd perfect number = true
  | otherwise = f n+2

f завершается? Вы не можете знать без решения открытой проблемы о том, существуют ли нечетные совершенные числа. Именно способность создавать такие функции делает проблему остановки трудной.

Примитивная рекурсия как конструкция не позволяет вам этого делать; смысл в том, чтобы запретить "f n + 2", оставаясь при этом максимально гибким - вы не можете примитивно-рекурсивно определить f (n) в терминах f (n + 1).

Обратите внимание, что только то, что функция не является примитивно-рекурсивной, не означает, что она не завершается; Функция Аккермана является каноническим примером.

Answer 3

рекурсивные функции, которые могут быть реализованы только с помощью циклов do, являются примитивными рекурсивными функциями.

Answer 4

http://en.wikipedia.org/wiki/Primitive_recursive_function