Re: Tail recursion

Wilco Dijkstra <Wilco.Dijkstra@arm.com>
21 Aug 2000 00:03:14 -0400

          From comp.compilers
Related articles
Tail recursion strohm@airmail.net (2000-08-10)
Re: Tail recursion pfaffben@msu.edu (Ben Pfaff) (2000-08-13)
Re: Tail recursion danwang+news@cs.princeton.edu (Daniel C. Wang) (2000-08-14)
Re: Tail recursion toon@moene.indiv.nluug.nl (Toon Moene) (2000-08-14)
Re: Tail recursion fjh@cs.mu.OZ.AU (2000-08-21)
Re: Tail recursion Wilco.Dijkstra@arm.com (Wilco Dijkstra) (2000-08-21)
Re: Tail recursion mrs@kithrup.com (2000-08-21)
Re: Tail recursion ian0kerr@my-deja.com (2000-09-08)
Tail recursion Alexey.Mikhailov@gmail.com (jjb) (2006-11-04)
Re: Tail recursion kym@ukato.freeshell.org (russell kym horsell) (2006-11-04)
Re: Tail recursion diablovision@yahoo.com (2006-11-05)
Re: Tail recursion owong@castortech.com (Oliver Wong) (2006-11-08)
[1 later articles]
| List of all articles for this month |
From: Wilco Dijkstra <Wilco.Dijkstra@arm.com>
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
|L1.32|
                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...


Wilco

Post a followup to this message

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