Re: Tail recursion

Wilco Dijkstra <>
21 Aug 2000 00:03:14 -0400

          From comp.compilers

Related articles
Tail recursion (2000-08-10)
Re: Tail recursion (Ben Pfaff) (2000-08-13)
Re: Tail recursion (Daniel C. Wang) (2000-08-14)
Re: Tail recursion (Toon Moene) (2000-08-14)
Re: Tail recursion (2000-08-21)
Re: Tail recursion (Wilco Dijkstra) (2000-08-21)
Re: Tail recursion (2000-08-21)
Re: Tail recursion (2000-09-08)
Tail recursion (jjb) (2006-11-04)
Re: Tail recursion (russell kym horsell) (2006-11-04)
Re: Tail recursion (2006-11-05)
Re: Tail recursion (Oliver Wong) (2006-11-08)
[1 later articles]
| List of all articles for this month |

From: Wilco Dijkstra <>
Newsgroups: comp.compilers
Date: 21 Aug 2000 00:03:14 -0400
Organization: Compilers Central
References: 00-08-054 00-08-071 00-08-089
Keywords: optimize

"Daniel C. Wang" wrote:

> > The GCC compiler suite does tail recursion optimization at least
> > for C and C++ and probably for its other languages as well.
> But only "intra-procedurally"

Tailrecursion can only be applied intra-procedurally as a special
tailcall to the same function.

[ removed some example code ]

> which a smart Scheme and ML compiler would do...

Standard tailcall optimization gives you exactly what you want
because the functions don't use the stack:

odd PROC
                LDR r1,|L1.32|
                LDR r0,[r1,#0]
                CMP r0,#0
                SUBNE r0,r0,#1
                STRNE r0,[r1,#0]
                BNE even
                MOVEQ r0,#0
                BEQ exit
                DCD n

If you turn automatic inlining on all of this is academic: small functions
completely disappear. If you do tailrecursion before inlining I think you
get optimization that is close to that of functional languages: calls to
recursive functions would expand into loops.
However many C compilers do inlining before tailcall & tailrecursion...


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.