Xref: utzoo comp.edu:3707 uw.general:1955
Path: utzoo!attcan!lsuc!watmath!maytag!watdragon!rose!bpdickson
From: bpdickson@rose.uwaterloo.ca (Brian Dickson)
Newsgroups: comp.edu,uw.general
Subject: Re: Recursion Summary
Message-ID: <1990Oct25.160014.17216@watdragon.waterloo.edu>
Date: 25 Oct 90 16:00:14 GMT
References: <1990Oct23.211651.10227@contact.uucp> <9868@milton.u.washington.edu> <9882@milton.u.washington.edu>
Sender: daemon@watdragon.waterloo.edu (Owner of Many System Processes)
Distribution: na
Organization: University of Waterloo
Lines: 32

In article <9882@milton.u.washington.edu> mrc@Tomobiki-Cho.CAC.Washington.EDU (Mark Crispin) writes:
>In article <9868@milton.u.washington.edu> iho@akbar.UUCP (Il Oh) writes:
>>Correction.  _Anything_ (not almost) that can be done recursively can be done
>>iteratively.
>
>Sorry, this is not at all correct!
>
>Recursion is nothing more a reentrant subroutine call.

Error #1: reentrant subroutine call == recursion

Example: inexperienced FORTRAN programmer writes recursive program,
	wonders why weird things happen. (I observed this one.) :-(

>What I think you are thinking of are compilers which are smart enough
>to recognize tail-recursion and to generate iterative instead of
>recursive code.

No, the discussion is the equivalence of 2 programs performing the same
task, one via recursion, the other via iteration. The equivalence can
be demonstrated by program-controlled stack-equivalent code, whereby
the users program performs all of the state-saving and restoration
of variables' states, as well as depth of "recursion" being emulated.
This can be shown as equivalent on all machines with space-allocation
of a sort, independent of manner of physical stack representation and
OS/compiler controled state-preservation. This equivalence should be obvious.
The question of whether the programs do the same thing is reduced to whether
the programs will, at a given level of "recursion", have the same state of
variables, and execute the same set of instructions (excluding the "recursion"
step, obviously), and the answer is by definition of our construction, yes.

Brian Dickson