В SICP говорится, что в C потребление памяти увеличивается, даже когда рекурсивные вызовы на самом деле являются итеративными. Зачем?

По сути, он пытается сказать, что компиляторы для этих языков не могут устранить хвостовую рекурсию. Короче говоря, он ошибается (или в любом случае чрезмерно обобщает - я думаю, что «большинство реализаций» достаточно ласковой формулировки, чтобы технически это могло быть в некотором роде правильным, хотя в лучшем случае вводящим в заблуждение). Хотя я, конечно, не могу гарантировать, что каждый компилятор для любого другого языка устраняет хвостовую рекурсию, нет никаких сомнений в том, что по крайней мере некоторые компиляторы C и C++ (например, Intel C++, gcc/g++) могут и будут это делать. Я не проверял, но, учитывая, что GNAT (компилятор Gnu Ada) использует тот же оптимизатор, что и их компиляторы C и C++, я сразу предполагаю, что он также может устранять хвостовую рекурсию.

Прошло достаточно много времени с тех пор, как я использовал Паскаль, и я не могу сделать разумного комментария по этому поводу - мое непосредственное предположение было бы "нет", но это не имеет ничего общего с самим языком, и в основном сводится к факту что самое последнее использование Pascal восходит к Borland, и они, казалось, никогда не прилагали много усилий для оптимальной генерации кода.

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

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

Вы спросили: а как же C#?

C #, как и Java, но в отличие от большинства реализаций C / C ++ или ADA, компилируется в промежуточный язык, который затем компилируется, как правило, во время выполнения «компилятором точно в срок».

На момент написания компилятор C# не будет выполнять устранение хвостовой рекурсии, но JIT может.

Подробную информацию см. в разделе http://blogs.msdn.com/b/clrcodegeneration/archive/2009/05/11/tail-call-improvements-in-net-framework-4.aspx

Это не имеет ничего общего с реализациями компиляторов.

Вы упустили тот самый момент, который он пытается подчеркнуть, а именно различие между процессами и процедурами. Процедура может быть рекурсивной, даже если лежащий в ее основе процесс, который она реализует, в принципе является итеративным; а рекурсивные процедуры потребляют стек.