-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
On Mon, Nov 28, 2005 at 05:53:24AM +1100, Tess Snider wrote:
> 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. This is because every time you make a
> function call, it has to temporarily tuck away all of the local
> information in the last scope out of the way onto the stack, so it can
> go back and retrieve it later, when the function is done. So, as you
> dive down into your recursion, your stack gets bigger and bigger. You
> can visualize this by putting a large number into the factorial
> function, and then putting a breakpoint down at your boundary
> condition, and looking at the stack trace in the debugger of your
> choice. Holy cow!
The stack will grow linearly with the number but the integer will
overflow much sooner than your stack does.
I've NEVER liked the use of factorial as an example of recursion in
books on programming because it is such a bad example that can obviously
be much better implemented iteratively and worse, (perhaps not obviously)
multiplying up integers is a terrible way to calculate factorials (not
much better than doing division by repeated subtraction).
- ----------------------------------------------------------------------
#include <math.h>
extern double tgamma( double );
double fact( double x ) { return( tgamma( x + 1 )); }
#include <stdio.h>
int main()
{
int i;
for( i = 0; i < 50; i++ )
{
printf( "fact( %d ) = %g\n", i, fact( i ));
}
}
- ----------------------------------------------------------------------
Recursion only gets useful when dealing with tree structures and in
that case ALL languages will grow their stack (because they need to
store the intermediate values). In such a situation the recursive
solution will be much easier to write and usually more efficient to
execute than the non-recursive solution. Certainly it will be
easier to debug because the stack contents are easy to inspect.
Try writing a qsort() without recursion...
- Tel
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.1 (GNU/Linux)
iQIVAwUBQ4rn+MfOVl0KFTApAQLT/w/+KxAxByWByNRrysFZG8o0FpLObCZp4B/g
S3aQ/5Q/39jTK491NEjwisag4Bv2/M6VRGy5efYAc//j/9Tp6VXyQpQ+8MFQ5D+9
xk9R9njKp12h67zHIPva7jQV5A05Crt/i3c5FATHpPVVRTTEaABl+5r4VlINpKtE
AmxKxg+DmjIOQMAgsymtDP0WwAam9fegYWPJds/2e2GLWO3outbvtA9qerXJZ2gJ
BSTrzI2Y8tdsvLgfzQrl4T/2+uvKBD6E/ezNvMcF1TKeBtFE7nrpU70qIoTPIXEe
mBMKuXqk8yi6A0IbqU+384wQNbeQ8znlWPxwFWy9AyvNWLiNul45ovvvnTD1iWYK
u5xdpceVB+MgBr3qSEib1T3UP6ACtA+TsWWcMA52z5DzDGEx8dyRCVk3bxQQgb9P
DQlu6jk3Hj0loAfmxR43M+fU5CIePfFK/iYLgNoCKY1+a3GD2nAu2s0DzS24D5Ad
Rqfiyfr5+T/+y6btPauKIfNyt3mhKq1/HJDFwzdmiGnPzt2mvoccaXKhZ5Tc5q+S
R0xtLohHJ8uOAEWgCUi8P+3YFgWTWX3/IIJRsMqV38ILzJKl629mhaQpEHL3YMcg
0vayNrwZcj6SqUki5h/GmzzV+mdKrQevyfg/wDj/qRqCULrAaRYmQkJ3/OEnKKS7
f5TxnDWV65Q=
=NEdk
-----END PGP SIGNATURE-----
--
SLUG - Sydney Linux User's Group Mailing List - http://slug.org.au/
Subscription info and FAQs: http://slug.org.au/faq/mailinglists.html
