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