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 );
    }
}

[download]
...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

[download]
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

In reply to Re^6: Behold! The power of recursion. by jordanh
in thread Behold! The power of recursion. by DigitalKitty

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.