Xref: utzoo comp.edu:3696 uw.general:1949
Path: utzoo!attcan!uunet!samsung!dali.cs.montana.edu!milton!Tomobiki-Cho!mrc
From: mrc@Tomobiki-Cho.CAC.Washington.EDU (Mark Crispin)
Newsgroups: comp.edu,uw.general
Subject: Re: Recursion Summary
Message-ID: <9898@milton.u.washington.edu>
Date: 25 Oct 90 06:30:45 GMT
References: <1990Oct23.211651.10227@contact.uucp> <9868@milton.u.washington.edu> <9882@milton.u.washington.edu> <9893@milton.u.washington.edu>
Sender: news@milton.u.washington.edu
Distribution: na
Organization: Mendou Zaibatsu, Tomobiki-Cho, Butsumetsu-Shi
Lines: 34

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.

Too bad that so much CS is "theory" and not much "practice".

It is misleading to claim that "any recursive solution can also be
done in a nonrecursive algorithm without exception."  Tail recursion
in a single routine translates neatly into a nonrecursive algorithm.

However, in some cases the only nonrecursive way to implement an
algorithm involves, in effect, emulating recursion.  These are
algorithms which have significant intermediate state which is needed
after the recursive call completes.  This requires a stack, or at
least a vector, and control logic for two iterations.  Let's not
forget algorithms in which the recursion takes place several routines
deep (foo->bar->zap->rag->foo).

Matters are further complicated in a multi-tasking environment, where
a particular routine must be reentrant and hence cannot use any global
variables.  Here, a stack is mandatory.  You don't even need multiple
processes; co-routines will do just fine.

The bottom line is: you can do without recursion, but in some cases
the iterative equivalent can not be practically implemented.

 _____   | ____ ___|___   /__ Mark ("Gaijin") Crispin  "Gaijin! Gaijin!"
 _|_|_  -|- ||   __|__   /  / R90/6 pilot, DoD #0105   "Gaijin ha doko?"
|_|_|_|  |\-++-  |===|  /  /  Atheist & Proud          "Niichan ha gaijin."
 --|--  /| ||||  |___|    /\  (206) 842-2385/543-5762  "Chigau.  Gaijin ja nai.
  /|\    | |/\| _______  /  \ MRC@CAC.Washington.EDU    Omae ha gaijin darou"
 / | \   | |__|  /   \  /    \"Iie, boku ha nihonjin." "Souka. Yappari gaijin!"
Hee, dakedo UNIX nanka wo tsukatte, umaku ikanaku temo shiranai yo.