Как примитивная рекурсия отличается от “нормальной” рекурсии?
Понимают для C++ , должен быть в состоянии помочь Вам: это создает базу данных, к которой можно получить доступ от Perl.
4 ответа
Упрощенный ответ заключается в том, что примитивные рекурсивные функции - это те, которые определены в терминах других примитивных рекурсивных функций и рекурсии в структуре натуральных чисел. Натуральные числа концептуально выглядят следующим образом:
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
Примитивно-рекурсивные функции - это естественный ответ (математика) на проблему остановки, лишенный возможности выполнять произвольную неограниченную саморекурсию.
Рассмотрим "злую" функцию.
f n
| n is an odd perfect number = true
| otherwise = f n+2
Имеет ли f прекратить? Вы не можете узнать, не решив открытой проблемы, существуют ли совершенные нечетные числа. Именно способность создавать подобные функции усложняет проблему остановки.
Примитивная рекурсия как конструкция не позволяет вам этого делать; суть в том, чтобы запретить «f n + 2», оставаясь при этом максимально гибким - вы не можете примитивно-рекурсивно определить f (n) в терминах f (n + 1).
Обратите внимание, что просто поскольку функция не является примитивно рекурсивной, это не означает, что она не завершается; Каноническим примером является функция Аккермана.
рекурсивные функции, которые могут быть реализованы только с помощью циклов do, являются примитивно-рекурсивными функциями.