Beefy Boxes and Bandwidth Generously Provided by pair Networks
go ahead... be a heretic
 
PerlMonks  

Re^6: Behold! The power of recursion.

by jordanh (Chaplain)
on Oct 19, 2004 at 01:03 UTC ( #400365=note: print w/ replies, xml ) Need Help??


in reply to Re^5: Behold! The power of recursion.
in thread Behold! The power of recursion.

I don't have inline installed on the Perl on the machine I'm typing this on, so I took the liberty of doing a pure C benchmark. I had to admit that I was, at first, surprised at the result, since I had heard that gcc does tail call elimination, then I found this article that explained why gcc was failing to perform this optimization. Subsequently, I changed guess_rec_c to read:

int guess_rec_c( int ans, int lower, int higher ) { int guess; guess = (int)((lower + higher)/2); if (ans == guess) return guess; if ( guess > ans ) { return guess_rec_c( ans, lower, guess -1 ); } else { return guess_rec_c( ans, guess +1, higher ); } }
...and using:
gcc -v
Reading specs from /usr/lib/gcc-lib/i586-suse-linux/3.3.3/specs
Configured with: ../configure --enable-threads=posix 
--prefix=/usr --with-local-prefix=/usr/local 
--infodir=/usr/share/info --mandir=/usr/share/man 
--enable-languages=c,c++,f77,objc,java,ada 
--disable-checking --libdir=/usr/lib --enable-libgcj 
--with-gxx-include-dir=/usr/include/g++ --with-slibdir=/lib 
--with-system-zlib --enable-shared --enable-__cxa_atexit 
i586-suse-linux
Thread model: posix
gcc version 3.3.3 (SuSE Linux)
with the compiler optimization -O3, the recursive version was slightly faster than the iterative version:
jordan@linux-jordan:~> more guess.c int guess_it_c( int ans, int lower, int higher ) { int guess; for(;;) { guess = (int)((lower + higher)/2); if ( ans == guess ) break; if ( guess > ans ) higher = guess -1; else lower = guess +1; } return guess; } int guess_rec_c( int ans, int lower, int higher ) { int guess; guess = (int)((lower + higher)/2); if (ans == guess) return guess; if ( guess > ans ) { return guess_rec_c( ans, lower, guess -1 ); } else { return guess_rec_c( ans, guess +1, higher ); } } int main() { int n; for (n=0; n<1000000; n++) VERSION(4999,1,10000); } jordan@linux-jordan:~> gcc -Wall -DVERSION=guess_it_c -O3 -o guess_it +guess.c jordan@linux-jordan:~> gcc -Wall -DVERSION=guess_rec_c -O3 -o guess_re +c guess.c jordan@linux-jordan:~> time ./guess_it real 0m0.291s user 0m0.285s sys 0m0.003s jordan@linux-jordan:~> time ./guess_rec real 0m0.284s user 0m0.276s sys 0m0.004s
I think this demonstrates that the recursive version of a program can be as efficient as an iterative solution. You might point to the fact that I changed the code, but the code is now arguably more "correct" as the -Wall check would complain about the routines declared to return int and reaching the end without a return statement. The fact that gcc did not recognize the equivalence of the routine call and the routine call preceded by the return is a quality of implementation issue. Just as I said, there's no reason why the recursive version couldn't be compiled to yield an equivalent program. I am disappointed that more compilers don't automatically offer this obvious and simple optimization.

Updated: Some formatting


Comment on Re^6: Behold! The power of recursion.
Select or Download Code
Re^7: Behold! The power of recursion.
by tachyon (Chancellor) on Oct 19, 2004 at 04:02 UTC

    The reason for the optimisation failure is interesting, thanks very much for the link.

    cheers

    tachyon

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://400365]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others pondering the Monastery: (8)
As of 2014-08-01 08:45 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    My favorite superfluous repetitious redundant duplicative phrase is:









    Results (257 votes), past polls