At Mon, 28 Nov 2005 05:53:24 +1100, Tess Snider wrote:
> On 11/27/05, Crossfire <[EMAIL PROTECTED]> wrote:
> > This is a case of recursion.
> What's totally crazy is that once you've been programming a while, and
> really understand this recursion stuff well, you have to then learn to
> stop using it. It's very sad, because recursion is good stuff, but
> the trouble is that, in C, arbitrarily large recursions make your
> stack the size of Godzilla.
I realise I'm a bit behind the times with continuing this thread, but
I'm surprised no-one mentioned that modern compilers are quite capable
of turning tail-recursion into in-place iteration.
As a silly example, just to make it obvious:
int recurse_forever(int n) {
if (++n % 10000 == 0) printf("n is %d\n", n);
return recurse_forever(n); /* n will wrap occasionally */
}
int main(int argc, char **argv) {
recurse_forever(0);
return 0;
}
Compile and run it without optimisation and it grows in memory and
segfaults. Compile it with -O and it will happily run forever without
growing in memory. Compare the assembly output from each and the
change is obvious - the recursive call is changed to a jmp since none
of the original state is actually needed after the recursed call
returns.
Scheme interpreters/compilers, as another example, *require* this
ability since tail-recursion is the only method of doing loops in
scheme.
--
- Gus
--
SLUG - Sydney Linux User's Group Mailing List - http://slug.org.au/
Subscription info and FAQs: http://slug.org.au/faq/mailinglists.html
