рекурсивная => нерекурсивная реализация

Ну, если мне нельзя выделять память, то я мало чего смогу реализовать вообще. А если таки можно, то я сомневаюсь, что можно дать формальное определение эмулируется в программе стек или нет. А без формального определения и говорить не о чем =)

что можно дать формальное определение эмулируется в программе стек или нет

Да что ты говоришь. стопка тарелок, пуш поп, не не слыхали. может и у самого стека формального определения нет? Вон хашкелист вверху думает, что все есть только машинные коды.

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

Ты в самом деле такой медленный? Выше тебе очень детально объяснили, как именно это делать (через CPS и SSA). Да, естественно придется в некоторых случаях эмулировать стек, как было видно в примере про Аккермана, однако даже там это простое преобразование половину стека выкинуло.

Ну переведи мне механически if и for без goto. А я посмеюсь.

В примере про Аккермана выше тебе показали стек в виде списка.

Да хватит его кормить, хотя он, вроде, просто тупой.

Не, просто тупой молчал бы и пускал слюни. А этот шизофреник очень буйный.

Да что ты говоришь. стопка тарелок, пуш поп, не не слыхали. может и у самого стека формального определения нет? Вон хашкелист вверху думает, что все есть только машинные коды.

Тогда дай определение. Программа на языке X эмулирует стек, если....

То есть, ты считаешь, что анон которому ты отвечал, у которого «аккерман» на схеме с готу, умен? Ну, вы нашли друг друга, поздравляю!

Ты, для начала, объясни разницу, стек на уровне реализации, или самодельный, в чем ты видишь разницу?

об ОПТИМИЗАЦИИ речь не шла.

А о чем ты тогда вообще тут плетешь?

Тупо - самодельный не может вызвать stack overflow, если таковой имеется в твоей целевой платформе.

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

Не «очень много», а вообще все, какие только могут быть.

Я показал, что есть проблемы

Не показал.

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

если в программе есть «переменная» типа чья мощность счётная бесконечность.

т.е. по такому определения целые числа питона того же есть стеки.

есть же теорема о возможности построения машины на 2ух переменных.

любая рекурсия может быть привращена в итеративную запись, правильно?

Только в некоторых случаях получится громоздко, неочевидно и тормозно :) Скажем, функция Аккермана.

Только в некоторых случаях получится громоздко, неочевидно и тормозно :)

Это с какой такой радости «тормозно»?

Про Аккермана потерли, лови еще раз:

int ack(int x0, int y0)
{
  int x = x0;
  int y = y0;
  std::vector<int> stack;

 entry:
  if (x > 0) {
    if (y > 0) {
      y = y - 1;
      stack.push_back(x-1);
      goto entry;
    } else {
      x = x - 1;
      y = 1;
      goto entry;
    }
  } else if(stack.size()>0) 
    {
      x = stack[stack.size()-1];
      stack.pop_back();
      y = y + 1;
      goto entry;
    } else return y + 1;
}

Не, ты все таки, ИМХО, влез в какие то левые «материи». Стек — это просто, это структура данных типа: последним зашел, первым вышел.

Так ты не ответил, как ты будешь обходить все элементы двоичного дерева за O(1) памяти.

при достаточном числе бит стек можно в одной переменной держать.

Это неважно. Наш шизофреник пытается свести тему к тому, как любой алгоритм, использующий память, переписать так, чтобы память ему волшебным образом была вообще не нужна. Что явно не имеет уже ни малейшего отношения к постановке вопроса ТСа.

Ты, для начала, объясни разницу, стек на уровне реализации, или самодельный, в чем ты видишь разницу?

Не хочу, мне все равно. Мне интересно, в чем разница между «программа эмулирует стек» и «программа не эмулирует стек».

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

тогда иди, и нагугли, что такое CALL в x86.

Да нет никакой разницы, разве что, в нативной реализации манипуляции со стеком оптимизированы, есть нативная ошибка, stack overflow, которую, впрочем, тоже можно запилить. С концептуальной точки зрения нет разницы.

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

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

Стало быть, вот эта а в указанных языках рекурсией пользоваться небезопасно (= нельзя) проблема его не должна беспокоить?

нет. Потому что эта проблема к самой рекурсии никак не относится. Развёрнутая рекурсия также небезопасна, как свёрнутая (за исключением частного случая TCO).

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

вообще-то — шла. «подскажите алгоритм, который умеет символьно производить такую операцию». Это и есть — оптимизация.

Ты не понял.

рекурсивный алгоритм -->> итеративная реализация

рекурсивный алгоритм -->> рекурсивная реализация

Речь идет о таких алгоритмах, как например факториал, его принято считать рекурсивным априори, в кругах поциэнта.

мальчик. я сегодня уже говорил куда тебе пойти со своей скриптотой.

stack overflow — это у жабоедов на их жаба-«процессоре». у чотких пацанов на x86 segmentation fault, bus error, illegal instruction и т.д. на других платформах — аналогично.

ЛОР буквально наводнился полоумными, полуанонимными идиотами.

Ну одно дело эксплуатация стека вызовов функций - вызов функции может оказаться достаточно дорогой операцией - а другое дело - жонглирование указателем стека - это обычно дешевле. И за переполнением проще следить.

О том, как «любая рекурсия может быть привращена в итеративную запись».

Call делает три вещи: 1) пишет текущий ip в память по адресу, указанному в sp; 2) модифицирует sp; 3) делает goto. Где ты тут рекурсию узрел?

Это кто сказал? Оптимизацией это будет, если какие-то характеристики алгоритма улучшатся, а это, опять-таки, не требовалось.

Не говори, бро, анонiмус тут, dr. batty тут - внесли бы уже царя и все, этот спор будет длиться вечно. И все же правы, вот что главное! И никто больше ничего не понимает!

любая рекурсия может быть привращена в итеративную запись, правильно? (тезис Черча)

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

Это хвостовой вызов.

Речь идет о таких алгоритмах, как например факториал, его принято считать рекурсивным априори, в кругах поциэнта.

такой алгоритм как «факториал» допускает и итеративную реализацию, и рекурсивную. Как и определение факториала. Если в каких-то «кругах» не осилили итеративное определение(реализацию) — это проблема этих «кругов».

Call делает три вещи

CALL делает одну вещь: вызывает функцию. А то, что ты сказал — реализация.

Ещё «докажи», что «суммирования байтов не существует, существует только сложение битов по модулю 2 и переносы». Ещё можешь «доказать», что циклов тоже не существует, а есть только декремент, и условный JMP. А когда я тебя ткну в LOOP, скажи, что «у меня процессор — говно!», как анонимный кукаретик выше.

Это кто сказал? Оптимизацией это будет, если какие-то характеристики алгоритма улучшатся

они и улучшаются. Алгоритм записанный в итеративной форме в большинстве случаев работает быстрее и потребляет меньше ресурсов, нежели алгоритм записанный как рекурсия.

На уровне ассемблера понятия «функция» действительно не существует. И да, циклов тоже. Если бы ты хоть немного писал на ассемблере, ты бы знал, что все эти команды — call, ret, loop — вполне могут быть использованы и для совершенно других целей. Классический пример:

      call next
next: pop eax

Какую, говоришь, функцию мы тут вызываем?

Только потому, что обычно люди не напрягаются с переписыванием в нерекурсивную форму, если это ничего не даёт. Но в вопросе данное требование не ставилось.

Может. Через свой стек. Но процесс вычисления останется рекурсивным(в терминологии той же sicp).

Автор и спрашивает именно о процессе. От того, что ты реализуешь рекурсию «руками», завелосипедив, стек и раскрыв (явно) функциональные вызовы - рекурсия, очевидно, никуда не денется.

Но в вопросе данное требование не ставилось.

А ты не понял вопроса.

Отлично, будем теперь называть любой алгоритм, использующий память, «рекурсивным».

Отлично, будем теперь называть любой алгоритм, использующий память, «рекурсивным».

Ну не просто использующий, а использующий заранее неизвестным образом (в результате чего выделять нужно динамически). Иными словами, к итерации можно привести все ф-и, которые являются общерекурсивными (и некоторые частично-рекурсивные, наверное).