Здравствуйте, Эйнсток Файр, Вы писали:

ЭФ>Но не выделяем пока память под блоки для функций, вызываемых глубже (вассал моего вассала не мой вассал).
ЭФ>То есть, память выделяем не всю сразу, а на одно углубление по стеку.
ЭФ>При этом, при вызове функции в итерации цикла мы переиспользуем уже выделенный блок памяти
ЭФ>не обращаясь к механизму выделения.
ЭФ>Т.е. под функцию main выделяем блок, размер которого определяется переменными, которые использует main и размерами стеков функций,
ЭФ>которые main вызывает непосредственно.
ЭФ>Идея заключается в том, чтобы моменты выделения/удаления блоков (памяти, необходимых для работы циклов)
ЭФ>соответствовали не вызовам функций, а входам и выходам из циклов.
Вы рассмотрите пример, который я привёл. Ну, допустим, у нас весь фрейм стека функции имеет размер X. Поскольку никаких других функций в примере нету, то все фреймы того же размера x.
Допустим, мы написали такую умную виртуальную машину, которая умеет детектировать циклы; так что фрейм стека под вызов выделяется ровно один раз и переиспользуется.
Итак, мы вызываем нашу функцию Count на каком-то объекте (пока не в цикле). Под неё выделен фрейм размером X (F1).
В начале цикла мы выделяем ещё один фрейм размером X для вызовов (F2).
Делаем вызов на первом ребёнке; исполнение снова доходит до цикла, чтобы подсчитать "внуков". Теперь нам опять нужно выделить фрейм размером X — назовём его F3.
Не будем пока лезть в рекурсию дальше — но к моменту возврата со 2го уровня на 1й мы теряем информацию о фрейме F3 — её просто негде сохранить. Она была частью информации о выполнении вызова на первом ребёнке, и она нам более недоступна.
Поэтому, несмотря на то, что мы обрабатываем второго ребёнка с тем же фреймом F2, что и первого, фрейм F3 придётся выделять заново.
То есть мы всего лишь отложили проблему на 1 уровень.
И это никак не связано с рекурсией — точно так же себя будет вести система вложенных вызовов A()->B()->C(), где циклы расположены в A и B.