Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/18/84; site utcsri.UUCP
Path: utzoo!utcsri!greg
From: greg@utcsri.UUCP (Gregory Smith)
Newsgroups: net.lang.c
Subject: Tail recursion
Message-ID: <2563@utcsri.UUCP>
Date: Wed, 16-Apr-86 01:29:20 EST
Article-I.D.: utcsri.2563
Posted: Wed Apr 16 01:29:20 1986
Date-Received: Wed, 16-Apr-86 01:54:54 EST
References: <2516@utcsri.UUCP> <708@bentley.UUCP>
Reply-To: greg@utcsri.UUCP (Gregory Smith)
Organization: CSRI, University of Toronto
Lines: 52
Summary: 

In article <708@bentley.UUCP> kwh@bentley.UUCP (KW Heuer) writes:
>In article <2516@utcsri.UUCP> utcsri!greg (Gregory Smith) writes:
>>What it should do next is .., call itself recursively to sort the shortest
>>list.  It should then *loop back* to sort the longest list (if it is more
>>than one item).  Thus a stack frame is saved while sorting the longer one.
>
>A good optimizer should compile tail-recursion into a jump anyway.  (But
>there are few good optimizers by that standard.)

This intrigues me... I would not have expected an optimizer to catch this
sort of thing, and would be interested in hearing details of any that do.

The salient parts of my code were:

func(a,b){
	do{
		foo bar;
		a = aa; b = bb;
	}while( cond );
}

The 'recursive version' is:
func( a,b ){
	foo bar;
	if( cond ) func(aa,bb);
}

The following is equivalent, and *might* be easier to catch, but shouldn't
be if proper control-flow analysis is done:

func(a,b){
	foo bar;
	if(!cond) return;
	func(aa,bb);
}
/* any comments? */
Does anybody end up with the do-while jump after compiling ( and optimizing )
one of the recursive ones? I tried a few variations and it didn't happen.
( 4.2 BSD vax 11/780 ).

This reminds me of one of the commonest 'tricks' in assembler - instead
of CALL X/RET, you write JMP X and then hopefully apologize in the comments.
Of course X must not be expecting any stack context. One of the DEC libraries
I was using to write pdp11 code had a macro CALLR X which was just JMP X !
I once wrote a CRT driver in Z80 code - if I hadn't used this trick, it
would have used about 10 levels of stack - with this trick, the maximum
was 2 ( This was significant - there was ..very.. little RAM available :-) ).

-- 
"If you aren't making any mistakes, you aren't doing anything".
----------------------------------------------------------------------
Greg Smith     University of Toronto      UUCP: ..utzoo!utcsri!greg