Ну так тебя и попросили показать, как развернуть в цикл

Так дальнейшее преобразование тривиально, хоть и громоздко. Все вызовы уже и так хвостовые (если кто не заметил), так что заменяются на goto, и, осталось только заменить создание замыкания (где (lambda (n) ...) захватывает cnt (указатель на предыдущее значение в стеке) и x) на какую либо реализацию самодельного стека. Мне лениво.

Это как это «без своего стека»? Я тебе такого не обещал.

То есть, ты предлагаешь заменить нативный стек своим, и это с твоей точки зрения сделает решение итеративным?

Ладно, так и быть, вот псевдокод на несуществующем промежуточном языке (схема с goto):

(define (ack x0 y0)
  (let ((x x0)
        (y y0)
        (stack nil))
    entry:
    (if (> x 0)
        (if (> y 0)
            (begin
              (set! y (- y 1))
              (set! stack (cons (- x 1) stack))
              (goto entry:))
            (begin
              (set! x (- x 1))
              (set! y 1)
              (goto entry:)))
        (match stack
           ((nx . nstack)
            (set! x nx)
            (set! y (+ y 1))
            (set! stack nstack)
            (goto entry:))
           (()
            (return (+ y 1)))))))

То есть, ты предлагаешь заменить нативный стек своим, и это с твоей точки зрения сделает решение итеративным?

Ну да ну да, итеративная функция, использующая для промежуточных значений std::vector<...> магически превращается в «рекурсивную», потому что а вдруг этот вектор на самом деле используется как стек?

А зачем тебе там goto? какая в нем необходимость?

А зачем тебе там goto? какая в нем необходимость?

Для механического перевода хвостового вызова. Плюс, если у нас была бы более сложная система, не одна, а несколько взаимно-рекурсивных функций, то было бы более одной точки входа, с потенциально нередуцируемым CFG.

Есть способы приведения нередуцируемого CFG к процедурному (через копирование блоков), но они очень громоздкие и выдают очень много кода, так что избавляться от внутреннего представления с goto ради непонятно чего нет смысла, да и все равно, первые шаги, до приведения CFG к редуцируемому виду, все равно придется делать в SSA (то есть, с базовыми блоками и goto). Никуда от этого не денешься. Нет такого преобразования для взаимно-рекурсивных функций, которое сразу бы давало без промежуточной лапши процедурный код.

То есть, да, в данном случае у нас редуцируемый тривиальный CFG, и никакого goto не надо, но я показываю, как это преобразование выполняет компилятор, и тут нет смысла пропускать важные шаги. Тем более, что я не видел компиляторов, которые бы напрягались избавляться от нередуцируемых CFG, этой хренью только декомпиляторы занимаются. Ну или разве что у тебя целевой язык это какой-нибудь OpenCL, где нередуцируемый CFG запрещен стандартом.

Для механического перевода хвостового вызова

Чем бы дитя не тешилось. ты забыл добавить «каретки»

Внимание!

Напоминаем, что кнопка «Показать удаленные комментарии», находится внизу страницы.

А стек куда ты денешь?

А зачем его куда-то девать? Что, с ним какие-то проблемы есть?

она ее хреново переводит, т.к. там случается StackOverflowException, которого в изначальном алгоритме не было вообще

Если изначальный рекурсивный алгоритм хреново написан, то это его проблемы, а не транслятора.

Это — набор инструкций, работающих со стеком и счётчиком команд. Никакой рекурсии тут, разумеется, нет.

Они и запилили. Называется TCO.

Ничего подобного. TCO работает лишь для хвостовых вызовов, что есть только подмножество.

Да, есть. Он засирает память и имеет ограничение на глубину.

И, типа, для рекурсивного алгоритма это не проблема?

Для рекурсивного алгоритма вообще — нет, только для частных случаев. в большинстве случаев рекурсивный алгоритм можно реализовать итеративным кодом.

только для частных случаев

Ну дык. То есть, проблема в одном — проблема в другом. Что тебе не нравится?

Чудеса логики ITT.

Ты куда то далеко от темы ушел. Изначально ты утверждал, что, мол, в машинных инструкциях рекурсии нет, поэтому проблем нет. Я показал, что есть проблемы. Дальше что тебе надо?

Ты не показал, что есть проблемы с автоматическим переписыванием. Ты показал, что есть проблемы с результатом. Ровно те же, которые были с оригиналом.

То что с автоматическим переписыванием есть поблемы, показывает даже наличие этого треда в природе. Ты, видимо, видишь только то, что хочешь видеть.

Следи за руками.

В машинах нет рекурсии. Существуют компиляторы языков с рекурсией. Значит, от любой рекурсии, допустимой в этих языках можно избавиться. Какая буква тебе непонятна?

подскажите алгоритм, который умеет символьно производить такую операцию, например для языков Java/C/C++ ? Может кто-то уже налабал готовый тул?

Ты уже ответил на этот вопрос топикстартера?

код итеративный.

структуры данных - конечные (т.е. без эмуляции стека на массиве или прочих списках)

насколько понимаю при таких вводных ограничениях придёться обмазываться самомодифицирующимися кодами либо реализовывать свой интерпретатор промежуточного языка :)

Наличие этого треда в природе показывает только то, что одному человеку захотелось задать вопрос. И только.

Схерали ты тут передергиваешь?

Так ты решил вопрос о том, как любую произвольную (НЕ tail-call) рекурсивную функцию в произвольном языке преобразовать в итерацию?

Запустить компилятор этого языка.

Что же мешает это сделать ТС'у?

Кривые руки? Недостаток мозга? Понятия не имею.

Компилятор преобразовывает.

Кривые руки? Недостаток мозга?

Так ты же утверждаешь, что компилятор за него все сделает. Зачем ему тогда включать мозг?

Чтобы отдать команду рукам запустить компилятор.

И? Он может развернуть любую рекурсию?

Разуй глаза он хочет трансляцию Java -> Java.

Чтобы отдать команду рукам запустить компилятор.

Стало быть, вот эта

а в указанных языках рекурсией пользоваться небезопасно (= нельзя)

проблема его не должна беспокоить?

Что у тебя за манямирок там? Нету в железе рекурсии, а в Си есть. Сам на вопрос ответишь?

Для того, чтобы преобразовать рекурсивный алгоритм в нерекурсивный — нет.

Он хочет трансляцию чего угодно -> чего угодно, с целью избежать проблем, создаваемых жабским компилятором, чьи возможности, в этом плане скромны. Ты может глаза разул, но мозг не включил.

Ладно, у меня большие сомнения, что ты понимаешь что такое рекурсия, и как она работает. Ты религиозен. Я не хочу больше это обсуждать. Любой язык гарантирует только хвосторекурсивную оптимизацию (если вообще гарантирует). Учи матчасть.

Компилятора Си не существует. Ура!

Ещё раз для тупых: об ОПТИМИЗАЦИИ речь не шла.

Он хочет трансляцию чего угодно -> чего угодно

Лол. Он не настолько упорот. С тобой точно не сравнить.

То есть, стек не строится, это все сказки?

Бедняга не может поверить, что его компуктер ничего не знает о рекурсии, вот досада.

Стек строится! Кошка котят родила! Ура!

Он может и о буковках не знает, которые ты в своей жабе пишешь, однако он ее выполняет, внезапно, тратит память на твое говно.

Ты нулевой.

Пок-пок-пок.

Пасяб.