Tail recursion

[Gregory Smith]

In article <708 at bentley.UUCP> kwh at bentley.UUCP (KW Heuer) writes:
>In article <2516 at 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