Двойная рекурсия - Double recursion - Wikipedia
В теория рекурсивных функций, двойная рекурсия является продолжением примитивная рекурсия что позволяет определять непримитивные рекурсивные функции, такие как Функция Аккермана.
Рафаэль М. Робинсон называется функциями двух натуральное число переменные грамм(п, Икс) дважды рекурсивно относительно данные функции, если
- грамм(0, Икс) является заданной функциейИкс.
- грамм(п + 1, 0) получается подстановкой из функции грамм(п, ·) И заданные функции.
- грамм(п + 1, Икс + 1) получается подстановкой из грамм(п + 1, Икс), функция грамм(п, ·) И заданные функции.[1]
Робинсон предлагает конкретную двойную рекурсивную функцию (первоначально определенную Рожа Петер )
- грамм(0, Икс) = Икс + 1
- грамм(п + 1, 0) = грамм(п, 1)
- грамм(п + 1, Икс + 1) = грамм(п, грамм(п + 1, Икс))
где данные функции примитивно рекурсивны, но грамм не является примитивно рекурсивным. Фактически, это именно та функция, которая сейчас известна как Функция Аккермана.
Смотрите также
Рекомендации
- ^ Рафаэль М. Робинсон (1948). «Рекурсия и двойная рекурсия». Бюллетень Американского математического общества. 54: 987–93. Дои:10.1090 / S0002-9904-1948-09121-2.
 | Этот математическая логика -связанная статья является заглушка. Вы можете помочь Википедии расширяя это. |