Re^6: Behold! The power of recursion.

[jordanh]

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

[tachyon]

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