'В языках типа Pascal, C реализация любой рекурсивной процедуры требует
объем памяти линейно возрастающий с вызовом процедур. Поэтому в них и
приходится прибегать к таким вещам, как циклы (что, по сути, является
синтаксическим сахаром). Scheme избавлена от этого недостатка и
выполняет итеративный процесс используя фиксированное кол-во памяти.
Это свойство называется хвостовой рекурсией.'
Несколько вопросов по написанному выше:
1) Почему C, Pascal при реализации ЛЮБОЙ рекурсивной процедуры требует
памяти, линейно возрастающей с вызовом процедур? Насколько я понимаю, в
момент вызова процедуры в стек помещаются параметры процедуры. А если
их нет? Адрес возврата?
2) Каким образом разработчикам Schema удалось избежать линейно
возрастающих требований к памяти при реализации рекурсии?
Здравствуйте, DemAS, Вы писали:
DAS>1) Почему C, Pascal при реализации ЛЮБОЙ рекурсивной процедуры требует DAS>памяти, линейно возрастающей с вызовом процедур? Насколько я понимаю, в DAS>момент вызова процедуры в стек помещаются параметры процедуры. А если DAS>их нет? Адрес возврата?
Зависит от. Может и адрес, тыж не сказал на каком процессоре в каком компиляторе.
С практической т.зр. рекурсивная функция без параметров большого смысла не имеет.
Т.к. единственный способ выхода из ней — использовать грязные они же "императивные" фичи.
DAS>2) Каким образом разработчикам Schema удалось избежать линейно DAS>возрастающих требований к памяти при реализации рекурсии?
Здравствуйте, DemAS, Вы писали:
DAS>1) Почему C, Pascal при реализации ЛЮБОЙ рекурсивной процедуры требует DAS>памяти, линейно возрастающей с вызовом процедур?
GCC имеет оптимизацию хвостовой рекурсии (Visual C++ вроде тоже), так что не все и не любой...
DAS>2) Каким образом разработчикам Schema удалось избежать линейно DAS>возрастающих требований к памяти при реализации рекурсии?
DemAS пишет:
> синтаксическим сахаром). Scheme избавлена от этого недостатка и > выполняет итеративный процесс используя фиксированное кол-во памяти. > Это свойство называется хвостовой рекурсией.'
Не всегда только, не всегда во всех случаях Scheme или LISP
от этого недостатка избавлены. А вот чтобы они были избавлены
и надо применять хвостовую рекурсию, и тогда компилятор или
интерпретатор сможет сделать ее оптимизацию и заменить ее
на тот же цикл.
> 1) Почему C, Pascal при реализации ЛЮБОЙ рекурсивной процедуры требует > памяти, линейно возрастающей с вызовом процедур?
Ну не умеют компиляторы С и Паскаля оптимизировать такое.
Хотя, кстати, может какие-то и умеют ... Но для таких
языков такие приемы не являются, как бы сказать,
идеоматическими, поэтому их оптимизации меньше внимания
уделяют.
Насколько я понимаю, в > момент вызова процедуры в стек помещаются параметры процедуры.
да, правильно.
А если > их нет? Адрес возврата?
Да, адрес возврата, кроме того, могут быть еще какие-то служебные данные,
типа суммарного размера всех параметров (как в __stdcall-соглашении) или
напр.
> > 2) Каким образом разработчикам Schema удалось избежать линейно > возрастающих требований к памяти при реализации рекурсии?
Заменой на цикл. Если рекурсия хвостовая (точнее, это — необходимое
условие, но не достаточное), то возможно у функции есть
одно свойство — после передачи управления рекурсивному вызову самой
себя никакая из локальных переменных этой функции в ее вызывающем
варианте не будет нужна для формирования результата. В таком
случае вызываемый вариант может использовать для переменных
ту же память, что использовал вызывающий.
Здравствуйте, DemAS, Вы писали:
DAS>1) Почему C, Pascal при реализации ЛЮБОЙ рекурсивной процедуры требует DAS>памяти, линейно возрастающей с вызовом процедур? Насколько я понимаю, в DAS>момент вызова процедуры в стек помещаются параметры процедуры. А если DAS>их нет? Адрес возврата?
Да. Так или иначе запоминается адрес возврата.
Локальные переменные ещё.
DAS>2) Каким образом разработчикам Schema удалось избежать линейно DAS>возрастающих требований к памяти при реализации рекурсии?
Переиспользованием. На ассмеблере при желании это тоже можно сделать Для этого надо:
— очистить стек от своих локальных переменных (они больше не понадобятся — возврата не будет)
— вручную сформировать правильный стек для вызова, положив в него параметры и адрес возврата к исходной точке
— вызвать функцию командой jmp, а не call
MasterZiv пишет: > Насколько я понимаю, в >> момент вызова процедуры в стек помещаются параметры процедуры.
Я еще хотел подчеркнуть, что то, как вызываются функции, стандартом
не регламентируется, поэтому в общем случае вы теоретически просто
не знаете, как передаются параметры.
Здравствуйте, SergH, Вы писали:
G>>GCC имеет оптимизацию хвостовой рекурсии (Visual C++ вроде тоже), так что не все и не любой... SH>А с деструкторами как?
А они иногда бывают тривиальными...
... << RSDN@Home 1.2.0 alpha rev. 745>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Так а в чем проблема ?
Казалось бы, если функция преобразуется в тело цикла,
то и все ее локальные объекты становятся локальными в теле цикла,
а тут вызывать деструкторы С++ умеет ...
> Делай что должно, и будь что будет
Кстати, этот девиз и на моём "гербе" тоже ...
Здравствуйте, MasterZiv, Вы писали:
MZ>Так а в чем проблема ? MZ>Казалось бы, если функция преобразуется в тело цикла, MZ>то и все ее локальные объекты становятся локальными в теле цикла, MZ>а тут вызывать деструкторы С++ умеет ...
Ммм, не совсем так. Точнее, если так сделать можно — то отлично. Но просто довольно часто так сделать нельзя, потому что рекурсия не является "истинно хвостовой", после вызова должны вызваться деструкторы. И нужно хорошо подумать, чтобы вызвать их иначе. Ну, типа так:
Где будем освобождать память? И про исключения не забываем.. Не, подумать и придумать можно. Осталось это засунуть в компилятор. Хорошо языкам с GC, у них таких проблем просто не стоит.
>> Делай что должно, и будь что будет MZ>Кстати, этот девиз и на моём "гербе" тоже ...
Здравствуйте, MasterZiv, Вы писали:
MZ>Ну не умеют компиляторы С и Паскаля оптимизировать такое. MZ>Хотя, кстати, может какие-то и умеют ... Но для таких MZ>языков такие приемы не являются, как бы сказать, MZ>идеоматическими, поэтому их оптимизации меньше внимания MZ>уделяют.
Современные C++ компиляторы практически все оптимизируют хвостовую
рекурсию. Кроме того тот же VC уже давно умеет агрессивно инлайнить
рекурсивные функции, притом произвольные рекурсивные функции, необязательно
с хвостовой рекурсией, как результат быстодействие может вырасти на порядки,
конечно цена раздутый код (из 100 строчной сишной функции бывает и до 100000
ассемблерных строк)
А идеоматичность зависит не только от инструмента, но и от пользователя
SH>Ммм, не совсем так. Точнее, если так сделать можно — то отлично. Но просто довольно часто так сделать нельзя, потому что рекурсия не является "истинно хвостовой", после вызова должны вызваться деструкторы. И нужно хорошо подумать, чтобы вызвать их иначе. Ну, типа так:
SH>
SH>Где будем освобождать память? И про исключения не забываем.. Не, подумать и придумать можно. Осталось это засунуть в компилятор. Хорошо языкам с GC, у них таких проблем просто не стоит.
Да в таких случаях хочешь не хочешь нужно держать на стеке временные переменные, вот для такого
Здравствуйте, MasterZiv, Вы писали:
MZ>SergH пишет: >> Ммм, не совсем так. Точнее, если так сделать можно — то отлично. Но
MZ>Я так и не понял, в чем же там проблема с деструкторами.
Тупят компиляторы (как и я ) с времеными переменными.