Xref: utzoo comp.edu:3705 uw.general:1953
Path: utzoo!attcan!lsuc!xenitec!maytag!watdragon!spurge!ccplumb
From: ccplumb@spurge.uwaterloo.ca (Colin Plumb)
Newsgroups: comp.edu,uw.general
Subject: Re: Recursion Summary
Message-ID: <1990Oct25.145621.13691@watdragon.waterloo.edu>
Date: 25 Oct 90 14:56:21 GMT
References: <1990Oct23.211651.10227@contact.uucp> <9868@milton.u.washington.edu> <9882@milton.u.washington.edu> <9893@milton.u.washington.edu>
Sender: daemon@watdragon.waterloo.edu (Owner of Many System Processes)
Distribution: na
Organization: University of Waterloo
Lines: 69

In article <9893@milton.u.washington.edu> iho@akbar.UUCP (Il Oh) writes:
> Doesn't this essentially prove my point?  That any recursive solution can
> be also done in a nonrecursive algorithm without exception?  If I remember
> my computing theory class, Turing machines are not capable of recursion.

Turing machines are fully capable of recursion.  Nobody has found a buildable
machine which is fundamentally more capable that a Turing machine, i.e. to the
best of my knowledge, my own brain is Turing-equivalent (although it would take
a *damn* fast Turing machine and very clever software!).

The difference between recursion and iteration is the FIFO stack nature
of recursion.  Both are a loop, repeatedly executing the same
instructions in various contexts (i.e. variable bindings).  Iteration
uses only one context, overwriting the old with the new.  Recursion
remembers old contexts, arbitrarily many (although usually not, in
practice, infinitely), to get back to them later.

For example, Quicksort:

quicksort(array, low, high)
{
	if (high-low <= 1)
		return;
	mid = partition(array, low, high);
	quicksort(array, low, mid-1);
	quicksort(array, mid+1, high);
}

During the first call the quicksort, you must remember the values of
mid and high for the second call.  Thus, you must ensure that the first
call does not store its mid and high in the same place as the parent.
This can be done by storing the parent's mid and high somewhere and
keeping the child's in the same absolute location (shallow binding), or
by keeping the child's variables somewhere else (deep binding, more or
less).

It is often useful to write problems in recursive form even when
iteration could be used.  The second call to quicksort above is an
example.  It could be replaced by "low = mid+1; goto start;", but
that's messy.  Some languages provide tail recursion optimisation,
where they notice that no further references to the caller's context
will be made, so there is no need to save it.

It is awkward to express recursion in terms of iteration, and error-prone
(the details of managing a stack are usually best left hidden), while
it is quite easy to implement iteration in terms of recursion, and if
tail recursion optimisation is available, it is just as efficient.

Thus there is a tendency in recent languages to not implement iteration
at all.  In Scheme, for (i = 1; i < 10; i++) printf("Hello, world!\n");
would be written (directly, not using the convenient shorthands) as:

(let foo ((i 1))
     (if (< i 10)
         ((print "Hello, world!\n")
          (foo (+ i 1)))
))

(I'm doing this from memory... there may be syntax errors.)

In other words, let foo be a function with initial value i = 1.
If i < 10, print "Hello, world!\n" and call foo with i+1.
Otherwise, return.

Recursion is so useful that most computers use reentrant procedure-calling
conventions, so it works in the straightforward way, but some old computers
did things like patch the final jump in a routine, so it took more care.
-- 
	-Colin