From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-1.3 required=5.0 tests=BAYES_00,INVALID_MSGID
	autolearn=no autolearn_force=no version=3.4.4
X-Google-Language: ENGLISH,ASCII-7-bit
X-Google-Thread: 109fba,baaf5f793d03d420
X-Google-Attributes: gid109fba,public
X-Google-Thread: 103376,97188312486d4578
X-Google-Attributes: gid103376,public
X-Google-Thread: fc89c,97188312486d4578
X-Google-Attributes: gidfc89c,public
X-Google-Thread: 1014db,6154de2e240de72a
X-Google-Attributes: gid1014db,public
From: fjh@mundook.cs.mu.OZ.AU (Fergus Henderson)
Subject: Re: What's the best language to start with? [was: Re: Should I learn
 C or Pascal?]
Date: 1996/08/11
Message-ID: <4ukn3h$7b@mulga.cs.mu.OZ.AU>#1/1
X-Deja-AN: 173526889
references: <31FBC584.4188@ivic.qc.ca>
 	<01bb83f5$923391e0$87ee6fce@timpent.airshields.com>
 	<4uah1k$b2o@solutions.solon.com>
 	<01bb853b$ca4c8e00$87ee6fce@timpent.airshields.com>
 	<4udb2o$7io@solutions.solon.com>
 	<01bb8569$9910dca0$87ee6fce@timpent.airshields.com>
 <g1sp9xtkmd.fsf@hotspec.lanl.gov>
organization: Comp Sci, University of Melbourne
newsgroups: comp.lang.c,comp.lang.c++,comp.unix.programmer,comp.lang.ada
Date: 1996-08-11T00:00:00+00:00
List-Id: <comp.lang.ada>


clodius@hotspec.lanl.gov (William Clodius) writes:

>There is one special case of recursion, fortunately the most commonly
>encountered case, where it is "ridiculously" easy for a compiler to
>see that the recursion can be replaced by iteration. The recursive
>code must call itself directly on only one branch of the control of
>flow and is the last call before returning on that control of
>flow. Conventionally it is placed on the last branch of the control of
>flow for clarity, hence the name "tail" recursion.

That isn't sufficient condition; in C, it's also necessary for the
compiler to check that the function not take the address of any local
variables.  (GNU C checks a slightly more general condition -- it only
does tail recursion optimization in functions which don't have any
variables stored on the stack at all.)

The requirement that it be only one branch of the control flow is
unnecessary.  In C, it should be just as "ridiculously" easy for the
compiler to optimize any `return' statements which return the result
of a recursive call to the containing function, regardless of the
control flow.  For example, in

	void f(int x) {
		if (x % 4 == 0) return f(x/3 - 1);
		if (x % 3 == 0) return f(x/2 - 1);
		...
	}

it should be easy enough to replace this with

	void f(int x) {
	entry:
		if (x % 4 == 0) { x = x/3 - 1; goto entry; }
		if (x % 3 == 0) { x = x/2 - 1; goto entry; }
		...
	}

The compiler doesn't need to check that there is only one flow
of control, it just needs to check that the function doesn't
take the address of any local variables (before the recursive tail call).

--
Fergus Henderson <fjh@cs.mu.oz.au>   |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>   |  of excellence is a lethal habit"
PGP: finger fjh@128.250.37.3         |     -- the last words of T. S. Garp.