# [plt-scheme] guido on tail recursion

 From: Eli Barzilay (eli at barzilay.org) Date: Sat Apr 25 19:01:27 EDT 2009 Previous message: [plt-scheme] guido on tail recursion Next message: [plt-scheme] guido on tail recursion Messages sorted by: [date] [thread] [subject] [author]

```On Apr 25, Prabhakar Ragde wrote:
>
> Or the doofus-in-the-devel-tools, GCC, which will optimize a tail
> call if and only if the return type and space requirements for
> parameters for the called function exactly match those of the
> current function. Write mutually-recursive even? and odd?, stick a
> gratuitous local variable into one, and watch the stack overflow.
>
> Perhaps I shouldn't apply the term "doofus" to GCC, though, as it at
> least tries, unlike CPython. (And the JVM...) --PR

(This is now well off-topic, but I can't resist...)

I once looked at the code that GCC generates for mutually recursive
even/odd, with tail-call optimizations, and the machine code really
impressed me.  Doing that again, I get this with -O2 (translating the
assembly code):

is_odd:
if n=0 return 0
n -= 1
is_even:
if n=0 return 1
n -= 1
goto is_odd

and with -O3, the implicit loop is unrolled a few times (also
hand-translated):

is_even:
if n=0 return 1
if n=1 return 0
if n=2 return 1
if n=3 return 0
if n=4 return 1
if n=5 return 0
A := n-6
if A=0 return 1
loop:
if A=1 return 0
if A=2 return 1
if A=3 return 0
if A=4 return 1
if A=5 return 0
if A=6 return 1
if A=7 return 0
if A=8 return 1
if A=9 return 0
A := A-10
if A=0 return 1
goto loop

--
((lambda (x) (x x)) (lambda (x) (x x)))          Eli Barzilay:
http://www.barzilay.org/                 Maze is Life!

```

 Posted on the users mailing list. Previous message: [plt-scheme] guido on tail recursion Next message: [plt-scheme] guido on tail recursion Messages sorted by: [date] [thread] [subject] [author]