- Как правильно пилотировать самолет?
- Делать надо так, как это делает хороший пилот...Вы не дочитали. Там дальше написано, как именно. Это первое. Второе - заявление, что универсального алгоритма перехода от рекурсии к итерации нет, неверно.
Это истинная правда. Такие классы действительно есть. Всё остальное Вы домыслили и потом начали спорить с домысленным и обижаться на домысленное.
О как… Ну тогда раскрутите, пожалуйста в итерацию функцию Аккермана при помощи Вашего “универсального алгоритма”
- Я изобрел универсальный растворитель! Растворяет все на свете!
- Да? А в чем вы собираетесь его хранить?
Я и говорю, что можно заниматься крючкотворством… Но лучше подумать о введенном в заблуждение второкурснике, который чуть не потерял веру в человечество 
1.Алгоритм не мой. 2. Будет полезней, если сделаете это сами. Сюжет (числа Аккермана), вроде бы, довольно прост для этого.
Понятно. Мне хорошо знаком тип людей, делающих различного рода категорические заявления и уходящих в кусты, как только дело коснется проверки этих заявлений.
Я же не собственные идеи пропагандирую, а известные, в общем, вещи. Поэтому Ваше требование приводить примеры (подготовка которых требует времени и усилий) неуместно. Если скажу, что Волга впадает в Каспийское море, не потребуете же собственноручно мною сделанных фотографий места впадения. Могу посоветовать книгу Бертрана Мейера “Методы программирования”, там есть пример, кажется, про Ханойские башни.
Если это, в общем, известная вещь", не могли бы Вы указать книгу, где приводится этот замечательный универсальный алгоритм (сам алгоритм, - надеюсь, Вам не надо объяснять значение этого термина?, - а не болтовня о том, что это возможно. Возможно в уме почти мгновенно перемножать многозначные числа, и такие люди есть, но их - единицы, а алгоритма, реально работающего нет). Рассказ о том, что суп готовят, налив воды в кастрюлю, поставив ее на огонь и засыпав необходимые ингредиенты - это не алгоритм. А не нужно отсылать меня а тривиальному примеру замены рекурсии итерацией в “Ханойских башнях”, речь шла о более сложном случае, когда параметры рекурсивного вызова сами вычисляются рекурсивно.
Не вижу смысла продолжать эту дискуссию с Вами. Извините. Книгу я назвал.
Спасибо. Я тоже не вижу смысла продолжать дискуссию с Вами. Мнение о Вас сложилось.
Алгоритм автоматического преобразования произвольной рекурсивной программы в циклическую
- Записывается рекурсивная программа на языке высокого уровня.
- Программа компилируется.
- Берется полученный машинный код откомпилированной программы и программа-интерпретатор (виртуальная машина) этого машинного кода. Такой интерпретатор с очевидностью не является рекурсивным, но является циклическим.
- Интерпретатор в совокупности с данными (машинным кодом исходной программы) и представляет собой эквивалентную исходной нерекурсивную программу. Voilà!
Варианты реализации:
- Java -> javac -> байт-код + java (JVM).
- Паскаль -> здешний компилятор -> IL-код + интерпретатор IL-кода.
- Подмножество Оберона (“О” с процедурами) -> компилятор, описанный в книге С. З. Свердлова “Языки программирования и методы трансляции” -> Виртуальная машина (OVM) + полученный компиляцией код виртуальной машины.
В последнем случае нетрудно получить исходный текст на Паскале (а также на Си, Яве, Си#, Обероне) эквивалентной нерекурсивной программы. При этом код виртуальной машины, который выполняет роль данных для виртуальной машины, может быть при желании встроен в текст программы (если это кому-то важно).
На стр. 406 упомянутой книги приведен результат компиляции программы “Ханойские башни”. Решение для функции Аккермана ничем принципиально не отличается.
Какое-то жульничество. Процессор это та же виртуальная машина и выполняет команды циклически. Да и делает обычные джапмы, меняя указатель стека.
Все честно. И это не шутка. Реальный процессор тоже можно привлечь в эту схему, но раз уж разговор про преобразование программ (из одной программы в другую программу), то виртуальная машина (которая 100% программа) выглядит на 100% убедительно.
А это программа (на Паскале), вычисляющая функцию Аккермана без рекурсии. Экзотическая, конечно, зато получена автоматически. Тынц.
Может даже минут за 20 вычислить A(4, 1), в отличие от рекурсивного варианта, которому в этом случае не хватает стека.
Как говорят в Одессе, “Пойдите на базар, купите себе гуся и загаживайте мозги ему”. Это не алгоритм с нормальной реализацией, а набор приемов, требующий чертову уйму времени и массу специальных навыков. Поставить себе Оберон, сделать компилятор из книги… расскажите это своей подруге.
1 лайк
Институт математики, механики и компьютерных наук ЮФУ, 2005–2021