Xref: utzoo comp.theory:1447 comp.lang.functional:594
Path: utzoo!censor!geac!torsqnt!news-server.csri.toronto.edu!cs.utexas.edu!uunet!mcsun!hp4nl!sci.kun.nl!cs.kun.nl!eerke
From: eerke@cs.kun.nl (Eerke Boiten)
Newsgroups: comp.theory,comp.lang.functional
Subject: Re: recursive =?=> iterative ?
Message-ID: <2665@wn1.sci.kun.nl>
Date: 21 Jan 91 12:42:04 GMT
References: <1991Jan17.160716.292@lth.se> <1991Jan19.182618.7727@sbcs.sunysb.edu>
Sender: root@sci.kun.nl
Followup-To: comp.theory
Organization: University of Nijmegen, The Netherlands
Lines: 137

In article <1991Jan19.182618.7727@sbcs.sunysb.edu> stark@sbstark (Eugene Stark) writes:
[Glenn Jennings writes:]
>>Can anyone please point me to any *published* works dealing with this issue:
>>
>>  Is it easy or hard to automatically transform an algorithm which
>>  is expressed recursively, into one that is expressed iteratively ?
>>
>>  Practical results are preferred, but theoretical discussions are still
>>helpful.  I am guessing that it is hard (in general) to devise a program 
>>which can convert an arbitrary recursive program into one having only loops.  

I was going to respond to this, Gene Stark was ahead of me:
>
>Isn't this something that is done by nearly every compiler?
>

Yes, of course it is done by nearly every compiler. So, generally it is
easy. Just the stacks-implementation of recursion.

The interesting question is not whether it is possible to transform
recursive algorithms into iterative ones, but whether it is possible to
do this *without using stacks*.

Tail-recursive functions, i.e. fns of the form
	f(x) = if P(x) then H(x) else f(K(x)) fi
can be immediately translated into
	y:= x;
	WHILE NOT P(y) DO y:= K(y);
	RETURN H(y)
General linear recursive functions, of the form
	f(x) = if P(x) then H(x) else E(x,f(K(x))) fi
cannot, in general, be translated into iterative form without using
stacks. This is proved by Paterson and Hewitt [Pat70].
In the literature on transformational programming (cf. the book by my 
"boss" H. Partsch [Par90a], or [Fea87]), many examples of transformations from
linear recursion to tail recursion are treated (in particular, use of an
accumulator and inversion of computation).

Follows a small excerpt from my BibTeX file on transformational
programming etc. :
@ARTICLE{
		Ars82,
		Author= {J. Arsac and Y. Kodratoff},
		Title= {Some Techniques for Recursion Removal from Recursive
			Functions},
		Journal= toplas,
		Volume= 4, Number= 2,
		Month= Apr, Year= 1982,
		Pages= {295--322}}
% Ars82: Transformational, many techniques.
@ARTICLE{
		Aus78,
		Author= {M.A. Auslander and M.R. Strong},
		Title= {Systematic Recursion Removal},
		Journal= cacm,
		Volume= 21, Number= 2,
		Pages= {127--133},
		Year= 1978}
% Aus78 and other work by Strong: classical.
@BOOK{
		Bau82a,
		Author= {Bauer, F.L. and W{\"o}ssner, H.},
		Title= {Algorithmic Language and Program Development},
		Publisher= sv,
		Address= {Berlin},
		Year= 1982}
% Early textbook on transformational programming;
% contains large section on recursion simplification and -removal.
@CONFERENCE{
		Fea87,
		Author= {Feather,  M.S.},
		Title= {A Survey and Classification of some Program
			Transformation Approaches and Techniques},
		Crossref= {Mee87},
		Pages= {165--196}}
@PROCEEDINGS{
		Mee87,
		Booktitle= {Program Specification and Transformation. Proceedings of
			the {IFIP} {TC2}/{WG2.1} Working Conference on Program
			Specification and Transformation}
		Title= {Program Specification and Transformation. Proceedings of
			the {IFIP} {TC2}/{WG2.1} Working Conference on Program
			Specification and Transformation}
		Editor= {Meertens, L.G.L.T.},
		Publisher= nhpc,
		Address= {Amsterdam},
		Year= 1987}
% General survey in IFIP TC2 conference proceedings.
@BOOK{
		Par90a,
		Author= {Partsch, H.},
		Title= {Specification and Transformation of Programs - a Formal
			Approach to Software Development},
		Address= {Berlin},
		Publisher= sv,
		Year= 1990}
% Recent textbook on transformational programming.
@CONFERENCE{
		Pat70,
		Author= {Paterson, M.S. and Hewitt, C.E.},
		Title= {Comparative Schematology},
		Booktitle= {Record of the Project MAC Conf. on Conc.Syst.
			and Par.Comp., {W}oods Hole, {M}ass.},
		Year= 1970,
		Address= {New York},
		Publisher= {ACM},
		Pages= {119--127}}
% Contains proof that stacks are sometimes necessary.
@ARTICLE{
		Str71,
		Author= {Strong, Jr., H.R.},
		Title= {Translating recursion equations into flowcharts},
		Journal= jcss,
		Volume= 5,
		Pages= {254--285},
		Year= 1971}
@ARTICLE{
		Str75,
		Author= {H.R.A. Strong and A. Maggiolo-Schettini and B.A. Rosen},
		Title= {Recursion Structure Simplification},
		Journal= sicomp,
		Volume= 4, Number= 3,
		Year= 1975,
		Pages= {307--320}}
@ARTICLE{
		Wal73,
		Author= {Walker, S.A. and Strong, H.R.},
		Title= {Characterizations of flowchartable recursions},
		Journal= jcss,
		Volume= 7,
		Pages= {404--447},
		Year= 1973}
--
Eerke Boiten
Department of Informatics (STOP Project), K.U.Nijmegen
Toernooiveld, 6525 ED Nijmegen, The Netherlands
Tel. +31-80-652236.	Email: eerke@cs.kun.nl