адача
17. Пусть n
и m - целые
неотрицательные числа. Написать
рекурсивную программу, вычисляющую
классическую в теории рекурсии функцию
Аккермана:
(4)
Решение. Вычислить функцию Аккермана, исходя непосредственно из определения (4), удается лишь для некоторых малых n и m. Связано это со сложностью и необычностью данного рекурсивного определения. В общем случае не только ak() вычисляется через ak(), но и второй из аргументов функции также требует рекурсивного вызова ak(). Соответствующая программа-функция может быть записана так:
Следующий вариант программы для вычисления функции Аккермана включает в себя лишь один рекурсивный вызов:
Замечание. Для m=0..4 справедливы соотношения [15, с. 69]:
Эти формулы могут оказаться полезными при построении контрольных примеров для отладки новых, более эффективных вариантов программ вычисления функции Аккермана.
В работе [15, c. 256-260] приведен нерекурсивный вариант алгоритма вычисления значений функции Аккермана.
