-----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