music

OSdata.com

reentry and recusrion

summary

    This subchapter looks at renetry and recursion.

free computer programming text book project table of contents If you like the idea of this project, then please donate some money. more information on donating

stub section

    This subchapter is a stub section. It will be filled in with instructional material later. For now it serves the purpose of a place holder for the order of instruction.

    Professors are invited to give feedback on both the proposed contents and the propsed order of this text book. Send commentary to Milo, PO Box 1361, Tustin, California, 92781, USA.

reentry and recursion

    This subchapter looks at reentry and recursion.

man vs. boy

    In July 1964 Donald Knuth published a test to determine how well a particular compiler handled recursion and non-local references in ALGOL-60.

    His stated goal: “There are quite a few ALGOL60 translators in existence which have been designed to handle recursion and non-local references properly, and I thought perhaps a little test-program may be of value. Hence I have written the following simple routine, which may separate the “man-compilers” from the “boy-compilers”.”

    Knuth’s test program:

    begin
      real procedure A (k, x1, x2, x3, x4, x5);
      value k; integer k;
      begin
        real procedure B;
        begin k:= k - 1;
            B:= A := A(k, B, x1, x2, x3, x4);
        end;
        if k <= 0 then A:= x4 + x5 else B;
      end;
      outreal (A (10, 1, -1, 01, 1, 0));
    end;

    This program creates a tree of B call frames that refer to each other and the A call frames, each with its own copy of k that is changed every time the associated B is called. Knuth wrote in his original paper that the answer was -121. The correct answer is -67.

    The three difficult features tested are nested function definitions, function references, and constant/function dualism. An inadequate compiler may become confused and access the wrong call frames.

other

   “12. Recursion is the root of computation since it trades description for time.” —Alan Perlis, Epigrams on Programming, ACM’s SIGPLAN Notices Volume 17, No. 9, September 1982, pages 7-13

chapter contents

• eight queens

There is a temporary stoppage in work on this project because the author is once again homeless. This is a very worthy project that can benefit tens of millions of poor students at a very low cost (hundreds of dollars a month) and a banner ad for the sponsor could lead to millions of dollars of income. If a business is interested in supporting this project, please see project for details.