Re: need help Recursion and iteration...


[Prev][Next][Index][Thread]

Re: need help Recursion and iteration...



The following header lines retained to affect attribution:
|From: "Tim Dixon" <tdixon@fwi.com>
|To: "Randolph J. Herber" <herber@DCDRJH.FNAL.GOV>
|Subject: Re:      Re: need help Recursion and iteration...
|Date: Fri, 8 Jan 1999 11:29:21 -0500
|       charset="iso-8859-1"

|All computer programs are executed sequentially at the machine level.

        This is true.

|All (finite) recursion can be unwound to reflect this sequence of
     ^^^^^^^^
|operations.

        This is true.  But, the original question was not about
        finite recursion.

|Therefore: All recursive computer programs may be written in a sequential
|(iterative) form.

        This is false.  All finite recursive programs may be written
                            ------
        in a sequential form by evaluating the function at all legal
        inputs, forming a table, searching that table (which requires
        only finite time) and reporting success and a value if found,
        otherwise failure.  The original question and your statement
        is about all recursive programs, including infinite.
                 ---                               --------

        There exist functions whose definition can not be expressed
        as a series of loops.  The definition of the function must
        be expressed in recursive form.  A Turing machine (a.k.a.
        finite state automaton with an infinite tape) can operate
        on the represention of that definition and use the infinite
        tape to record the intermediate recursion to generate a
        ``unwrapped'' series of step.  This is what makes your
        first two statements correct.  The fact that functions exist
        which can not have the functions inherent recursion reduced
        to loops, in the general case of all legal inputs, is what
        makes your third statement false.

|Recursion is not one of the basic operations of computer science.  See
|Knuth's work.

        At the level of Turing machines, this is correct and that is
        what Dr. Donald E. Knuth's work states.  What it does not
        state is that all functions can be stated in finite information
        without using recursion and an interpreter of that recursion.

|Mathematically, some functions may not be guaranteed to work recursively for
|infinite cases, but computer programs are necessarily finite.

        The control table of a Turing machine is a computer program.
        The problem is that, in the general case with functions
        whose definition is stored on the Turing machine's tape
        along with the possibly infinite recursion stack representation
        requires a recursive definition and an interpreter of that
        recursion as part of the Turing machine so that the function's
        definition itself would be of finite size.

        Ackermann's function is an example of a function which requires
        such a treatment.

        Note that infinite requires infinite memory to store the
        recursion record (``stack'') and no actual computer has
        such a memory.  Nonetheless, a recursive representation
        of the function may be a compact, effective representation
        over a table-driven or the equivalent code-expanded forms.

|Tim Dixon         tdixon@fwi.com        http://www2.fwi.com/~tdixon
|"I hoped that You would write to me a message in the stars, as if the
|stars themselves were not enough."  -- from  a Pam Thum song

Maybe this will help you:  I earned a BA in mathematics from the University
of Iowa in 1972 from course work done between fall of 1964 to fall of 1969.
I had missed one core course, not major related, when I had to enter military
service because of the selective service (``draft'') for Vietnam.  I completed
that course in spring of 1972 and was awarded my degree in summer 1972.  I
took basically all the master's level computer science and had started on the
doctorate level material for that degree.  Among that material was a course
on the theory of automata which covered this point among others.  As I
remember, I earned an A in that course.

Randolph J. Herber, herber@dcdrjh.fnal.gov, +1 630 840 2966, CD/CDFTF PK-149F,
Mail Stop 318, Fermilab, Kirk & Pine Rds., PO Box 500, Batavia, IL 60510-0500,
USA.  (Speaking for myself and not for US, US DOE, FNAL nor URA.)  (Product,
trade, or service marks herein belong to their respective owners.)

|-----Original Message-----
|From: Randolph J. Herber <herber@DCDRJH.FNAL.GOV>
|To: CALC-TI@LISTS.PPP.TI.COM <CALC-TI@LISTS.PPP.TI.COM>
|Date: Friday, January 08, 1999 11:28 AM
|Subject: Re: need help Recursion and iteration...

|>In article <75nj88$o88$1@nnrp1.dejanews.com>,
|> <werner_huysegoms@my-dejanews.com> wrote:
|>>In article <367d657d.20892851@news1.qc.sympatico.ca>,
|>>  bmorrissNOSPAM@sympatico.ca (Benoit Morrissette) wrote:

|>>>  But there
|>>> exists some classes of algorythmic problems that can be solved
|>>> only through recursion ( graphs and trees ).

|>        He's right.

|>>Er.. no.  Every recursive program may be written in iterative form.
|>>It's not always trivial (as with the factorial), but it can be done.

|>        He's wrong.

|>Ackermann's function is a counterexample.

|>int A(int x, int y)
|>{
|>        if(x == 0) return y + 1;
|>        else if(y == 0) return A(x-1,1);
|>        else return A(x-1,A(x,y-1));
|>}

|>See also:  http://www.astro.virginia.edu/~eww6n/math/AckermannFunction.html

|>>> And in many
|>>> cases, recursion leads to programs that are more readable,
|>>> easier to debug and faster to write at the cost of using
|>>> more memory and taking more time to run.

|>>I second that.

|>>Best Regards,
|>>Werner Huysegoms
|>>Reply-To: werner.huysegoms@dgx11.cec.be
|>>remove the x before replying

|>>-----------== Posted via Deja News, The Discussion Network ==----------
|>>http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own

|>Randolph J. Herber, herber@dcdrjh.fnal.gov, +1 630 840 2966, CD/CDFTF
|PK-149F,
|>Mail Stop 318, Fermilab, Kirk & Pine Rds., PO Box 500, Batavia, IL
|60510-0500,
|>USA.  (Speaking for myself and not for US, US DOE, FNAL nor URA.)
|(Product,
|>trade, or service marks herein belong to their respective owners.)