In SICP, it says that in C memory consumption goes up even when recursive calls are actually iterative. why?

Question

The original words are

One reason that the distinction between process and procedure may be confusing is that most implementations of common languages (including Ada, Pascal, and C) are designed in such a way that the interpretation of any recursive procedure consumes an amount of memory that grows with the number of procedure calls, even when the process described is, in principle, iterative. As a consequence, these languages can describe iterative processes only by resorting to special-purpose ``looping constructs'' such as do, repeat, until, for, and while.

I am not familiar with C language, what about Java or C#? Is this true with them as well? And why?

Note: I thought the author is talking about abilities of different languages. But actually it is just about different implementations of compilers.

Answer 1

He's basically trying to say that compilers for these languages can't do tail recursion elimination. To make a long story short, he's wrong (or over-generalizing anyway -- I guess "most implementations" is enough of weasel wording that it could technically be sort of correct, though misleading at best). While I certainly can't guarantee that every compiler for every other language does tail recursion elimination, there's no question that at least some C and C++ compilers (e.g., Intel C++, gcc/g++) can and will. I haven't checked, but given that GNAT (the Gnu Ada compiler) uses the same optimizer and such as their C and C++ compilers, my immediate guess would be that it can do tail recursion elimination as well.

It's been long enough since I've used Pascal that I can't make an intelligent comment on it -- my immediate guess would be "no", but that has little to do with the language itself, and mostly comes down to the fact that most current use of Pascal traces back to Borland, and they never seemed to put a lot of effort into optimal code generation.

Answer 2

C (and similar languages) typically use a call stack to store variables local to each function. Every time a function is called, some more of the stack gets occupied; every time a function returns, the stack usage reduces.

However, there's no reason that a smart compiler can't do things like tail-call optimisation where appropriate, thus eliminating the stack usage. In languages like Lisp, I think the interpreter is required to perform such optimisations, so that may be the distinction that the author is trying to make.

Answer 3

You asked: what about C#?

C#, like Java but unlike most C/C++ or ADA implementation compiles to an intermediate language, that is then further compiled, typically at runtime by the "just in time compiler".

At the time of writing, the C# compiler will not perform tail recursion elimination, but the JIT may.

For detailed information, see http://blogs.msdn.com/b/clrcodegeneration/archive/2009/05/11/tail-call-improvements-in-net-framework-4.aspx

Answer 4

It has nothing to do with implementations of compilers.

You have missed the very point he is trying to make, which is a distinction between processes and procedures. A procedure may be recursive even though the underlying process it is implementing is in principle iterative; and recursive procedures consume stack.