Xref: utzoo comp.edu:3701 uw.general:1951
Path: utzoo!attcan!uunet!samsung!dali.cs.montana.edu!milton!uw-beaver!uw-june!mikew
From: mikew@cs.washington.edu (Mike Williamson)
Newsgroups: comp.edu,uw.general
Subject: Re: Recursion Summary
Message-ID: <13510@june.cs.washington.edu>
Date: 25 Oct 90 17:01:06 GMT
References: <1990Oct23.211651.10227@contact.uucp> <9868@milton.u.washington.edu> <9882@milton.u.washington.edu> <9893@milton.u.washington.edu> <9898@milton.u.washington.edu>
Reply-To: mikew@june.cs.washington.edu (Mike Williamson)
Distribution: na
Organization: University of Washington, Computer Science, Seattle
Lines: 49

In article <9898@milton.u.washington.edu> mrc@Tomobiki-Cho.CAC.Washington.EDU (Mark Crispin) writes:
>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.
>
> [...]
>

The more Mr. Crispin posts, the more clear it becomes that he's a
little bit confused.  It is absolutely, positively, NOT "misleading to
claim that 'any recursive solution can also be done in a nonrecursive
algorithm without exception'".  This is, in fact, exactly the case for
any "recursive" program that is being executed on a digital computer.

Recursive function theory is a mathematical formalism for describing a
certain class of functions, that was introduced in the early part
of this century.  (In fact, the use of the term "recursive" predates
the existence of computers.)  The class of general recursive functions
is very large, and does indeed include functions that cannot be
computed by a Turing machine.  However, for these functions there is
no known effective decision procedure, so I am sure that these are not
what Mr. Crispin had in mind.  It was subsequently proven that an
important subclass of recursive functions, the "partial recursive
functions", are exactly equivalent to those functions that can be
computed by a Turing machine.  Within this class of functions lies
every program that is written for, and executed on, modern digital
computers. 

As several others have pointed out (including Mr. Crispin himself), a
modern digital computer does not actually compute recursively; it
merely emulates recursion through clever use of it's internal store.
Through the magic of high-level language compilers, we may use a
recursive sytax to denote our algorithms, but at the machine language
level, it's all done sequentially.

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

The bottom line is: you do do without recursion, because in all cases
the iterative equivalent is what is actually performed by the hardware.

-Mike