music programming text book

reentry and recusrion


    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.


    YACC (Yet Another Compiler Compiler) is an early tool from UNIX used to generate parsers for “little languages”.

    Brian Kernighan said:

    Certainly for language development, yacc was an enormous influence. Speaking personally, I would never gotten off the ground doing language work without it, because for whatever reason, I wasn’t any good at writing recursive descent parsers. I always had trouble with precedence and associativity.
    With yacc you didn’t have to think about that. You could write down a grammar that made sense, and then you could say “This is the precedence and the associativity, and here’s how you handle ugly cases like unary operators that are spelled the same as binary operators.” All of those things were so much easier. Just the existence of that tool made it possible to think about doing things from a language point of view that otherwise would have been too hard.

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:

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

    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.


   “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

free music player coding example

    Coding example: I am making heavily documented and explained open source code for a method to play music for free — almost any song, no subscription fees, no download costs, no advertisements, all completely legal. This is done by building a front-end to YouTube (which checks the copyright permissions for you).

    View music player in action:

    Create your own copy from the original source code/ (presented for learning programming).

return to table of contents
free downloadable college text book

view text book
HTML file

Because I no longer have the computer and software to make PDFs, the book is available as an HTML file, which you can convert into a PDF.

previous page next page
previous page next page

free computer programming text book project

Building a free downloadable text book on computer programming for university, college, community college, and high school classes in computer programming.

If you like the idea of this project,
then please donate some money.

send donations to:
PO Box 1361
Tustin, California 92781

Supporting the entire project:

    If you have a business or organization that can support the entire cost of this project, please contact Pr Ntr Kmt (my church)

more information on donating

Some or all of the material on this web page appears in the
free downloadable college text book on computer programming.


Made with Macintosh

    This web site handcrafted on Macintosh computers using Tom Bender’s Tex-Edit Plus and served using FreeBSD .

Viewable With Any Browser

    †UNIX used as a generic term unless specifically used as a trademark (such as in the phrase “UNIX certified”). UNIX is a registered trademark in the United States and other countries, licensed exclusively through X/Open Company Ltd.

    Names and logos of various OSs are trademarks of their respective owners.

    Copyright © 2010, 2012 Milo

    Created: November 8, 2010

    Last Updated: June 16, 2012

return to table of contents
free downloadable college text book

previous page next page
previous page next page