С таким определением моё решение - вполне нерекурсивное.
Если я правильно понял, Вы организуете стек в виде списка...
Вы же сами понимаете, что
по сути Ваше решение всё же "рекурсивное"
![Smile :)](./images/smilies/icon_smile.gif)
А от меня хотите, чтобы я дал строгую формализацию, запрещающие "рекурсивные" решения. Нет, чтобы проявить добрую волю
![Smile :)](./images/smilies/icon_smile.gif)
Хорошо, сделаем так.
Запрещается использовать динамическую память. То есть в программе должно быть изначально объявлено конечное число переменных "статического типа", под каждую из которых отведена одна-единственная ячейка памяти (способная хранить произвольное целое число). И программа по ходу работы может пользоваться только этой памятью...
Если хотите, порешайте эту задачу. Но... вообще-то хрен редьки не слаще. Внутрь безразмерной ячейки памяти можно загнать счётное число таких же безразмерных ячеек, используя теорему об единственности разложения натуральных чисел в произведение простых множителей. Или используя приём с функцией Гёделя, основанный на китайской теореме об остатках. А далее одну из ячеек можно выделить под тот же самый стек...
Честно говоря, то решение, которое я изначально имел в виду, по сути это и делает. То есть
принципиально нерекурсивных программ, вычисляющих функцию Аккермана, похоже, нет и быть не может. Так что по большому счёту я пока снимаю задачу. Ну или признаю её даже не то, что открытой проблемой, а проблемой, которую непонятно как надо формализовывать
-- Чт ноя 05, 2009 00:06:17 --Примитивная рекурсия - это цикл for.
Оператор
![$\mu$ $\mu$](https://dxdy-01.korotkov.co.uk/f/0/7/6/07617f9d8fe48b4a7b3f523d6730eef082.png)
- это цикл while.
Ага
![Smile :)](./images/smilies/icon_smile.gif)
Причём есть такой интересной факт: любая вычислимая функция может быть представлена в виде
![$f(x) = l(\mu t(g(x,t)=0))$ $f(x) = l(\mu t(g(x,t)=0))$](https://dxdy-02.korotkov.co.uk/f/9/4/a/94ab3326ff373f407cdf997dd9d3e1dc82.png)
, где
![$l$ $l$](https://dxdy-03.korotkov.co.uk/f/2/f/2/2f2322dff5bde89c37bcae4116fe20a882.png)
и
![$g$ $g$](https://dxdy-04.korotkov.co.uk/f/3/c/f/3cf4fbd05970446973fc3d9fa3fe3c4182.png)
--- примитивно рекурсивные функции. То есть любую вычислимую функцию можно запрограммировать так, что будет использоваться только один цикл while и какое-то конечное число циклов for (и не будет использоваться goto).
Профессор Снэйп, объясните, пожалуйста, немного подробнее, какая связь между частичной рекурсивностью функции и возможностью ее вычисления с помощью итеративного алгоритма. (Можно ссылкой на учебник ).
Ну... это фольклор
![Smile :)](./images/smilies/icon_smile.gif)
Возможно, где-то в каком-то учебнике это и прописано, но я его не читал.
Если совсем схематично, то
Xaositect уже объяснил. А чуть более подробно... в двух словах не изложишь. Почитайте где-нибудь доказательство теоремы о том, что функция частично рекурсивно тогда и только тогда, когда она вычислима на обладающей достаточными вычислительными возможностями машине (какой-нибудь заранее выбранной, классика --- машина Тьюринга, хотя её можно заменить и на обычный снабжённый тем же Паскалем компьютер с потенциально бесконечной памятью). Там очень много чисто технических деталей, но если всё осилить, становится понятным, что имеется в виду.