[Back to TUTOR SWAG index] [Back to Main SWAG index] [Original]

                            Turbo Pascal for DOS Tutorial
                                 by Glenn Grotzinger
              Part 13: Recursion; system unit commands not covered yet.
                     copyright(c) 1995-96 by Glenn Grotzinger

    There were 2 simple problems presented...The first one...

    program part12_1;

      const
        maxstacksize = 500;

      type
        stack = record
          elements: array[1..maxstacksize] of char;
          capacity: byte;
        end;

      var
        thestack: stack;
        i: byte;
        ch: char;

      procedure startstack(var thestack: stack);
        begin
          with thestack do
            capacity := 0;
        end;

      procedure place(var thestack: stack; element: char);
        begin
          with thestack do
            begin
              if capacity = maxstacksize then
                writeln('**ERROR**  Trying to place element on full stack!')
              else
                begin
                  inc(capacity);
                  elements[capacity] := element;
                end;
            end;
        end;

      procedure remove(var thestack: stack; var element: char);
        begin
          with thestack do
            begin
              if capacity = 0 then
                writeln('**ERROR**  Trying to remove element from empty stack!')
              else
                begin
                  element := elements[capacity];
                  dec(capacity);
                end;
            end;
        end;

     begin
       randomize;
       startstack(thestack);
       write('Enter a string: ');
       while ch <> #10 do
         begin
           read(ch);
           place(thestack, ch);
         end;
       writeln;
       writeln;
       write('The string reversed is: ');
       while thestack.capacity <> 0 do
         begin
           remove(thestack, ch);
           write(ch);
         end;
     end.
    And now the second one...

    program part12_2; uses crt;

      const
        maxqueuesize = 50;

      type
        queue = record
          elements: array[1..maxqueuesize] of integer;
          front, back: integer;
          count: integer;
        end;

      procedure startqueue(var thequeue: queue);
        begin
          with thequeue do
            begin
              front := 1;
              back := maxqueuesize;
              count := 0;
            end;
        end;

      procedure incqueue(var thenum: integer);
        begin
          if thenum = maxqueuesize then
            thenum := 1
          else
            inc(thenum);
        end;

      procedure place(var thequeue: queue; element: integer);
        begin
          with thequeue do
            if count = maxqueuesize then
              writeln('**ERROR** Trying to place element in full queue.')
            else
              begin
                elements[back] := element;
                incqueue(back);
                inc(count);
              end;
        end;

      procedure remove(var thequeue: queue; var element: integer);
        begin
          with thequeue do
            if count = 0 then
              writeln('**ERROR** Trying to remove element from empty queue.')
            else
              begin
                element := elements[front];
                incqueue(front);
                dec(count);
              end;
        end;

      var
        thequeue: queue;
        int, count: integer;

      begin
        randomize;
        startqueue(thequeue);
        clrscr;
        while thequeue.count <> maxqueuesize do
          begin
            int := random(1000) + 1;
            if int <= 50 then
              place(thequeue, int);
            inc(count);
          end;
        while thequeue.count <> 0 do
          begin
            remove(thequeue, int);
            write(int, ' ');
            if thequeue.count mod 10 = 0 then
              writeln;
          end;

        writeln(count, ' numbers generated from 1-1000 to get these 50 ',
                       'numbers from 1-50');
      end.

    Forward
    =======
    Very useful to defeat the fact with the compiler that a function has to be
    defined above another function in order to use the first function in that
    second function.  Above the function that it needs to be in, say something
    like:

    function a(var input: integer): string; forward;

    Then on down below in the code, you need to go ahead and define the
    procedure or function entirely, with code.  For the header, you would
    use something like this:

    function a;

    Doing this would accomplish being able to use a function defined after
    a code call of the function for some purpose.  Successive recursion using
    two seperate functions (a calls b; b calls a; and so on and so forth),
    would be one example of having to use a forward.

    The $M compiler directive
    =========================
    I described the $M compiler directive back in part 8.  Please review it
    there.  Basically, the first number of the compiler directive is the
    program stack size.  It is very important.  The default, if the $M is not
    defined is 16K.  The maximum it can be defined to is 64K.  You may have to
    use this compiler directive to increase the stack size so a recursion may
    complete.  If the stack is filled, a runtime 202 error occurs.

    Recursion
    =========
    Recursion, to put it simply, is the execution of a function or procedure
    directly within that same function or procedure.  It is hard, sometimes,
    logically to see use of recursion, but when you see a thoroughly repetitive
    action, recursion could be used.

    Recursion should be used with a procedure which basically has a small
    number or NO parameters, since the recursion places a new occurrence of
    the procedure on the stack, along with those variables.  It is quite
    possible for a procedure to recurse itself upwards of thousands of times.
    Therefore, you could easily run out of memory in the stack in running your
    program.

    Basically, in logic, recursion is the repetition of a procedure as a regular
    or irregular loop by calling the procedure inside of the procedure, with
    some regulated terminating code.

    NOTE: Recursion must be done with relative caution in Pascal.  It is
    really, REALLY easy to shoot oneself in the foot, literally, by use
    of recursion.  It has it's advantages, but since Pascal is unlimited
    by how, and why you use recursion, versus other languages, which may
    limit it or not allow it all together.

    As an example, we will look at taking a factorial of a number.  Basically,
    to use an example, 4! (factorial) is 4 X 3 X 2 X 1.  Algebraically, we
    could see a factorial (n!) as n X (n-1) X (n-2) X (n-3)...(n - (n+1)).
    Let's try looking at a code example that does it...after that, I will
    explain the process in detail that goes behind how it works.  It's a
    simple, elegant one line set of code in a function that does all the
    multiplications for any number we put in there.

    I will try my best to explain what exactly is going on here in this
    example of recursion.  That, I find, is the hardest thing to see in
    the concept of how recursion works, is because it is hard to
    conceptualize how the variables and functions work, in a manner that
    is understandable.

    In all of the books I have read, I have not seen an adequate description
    of the actual logic and action of recursion -- enough to allow people to
    understand the idea of what is going on.  Most teachers I've heard of and
    talked to, just say what I have already said to this point, and shy away
    from actually requiring written code using recursion, or explaining code
    using recursion to enable people to truly understand what is going on.

    I seek to change those observed facts, by trying to fully explain this
    example below, so people may be able to understand them sufficiently.
    I hope this explanation could be the best people have ever seen, and
    I *definitely* want e-mail and feedback on how well I do in explaining
    the concepts of what is going on (via showing all variable changes at
    all points, and order of execution of the code), because it is one of
    the hardest concepts in programming that I have come across in
    understanding.  (I will also ask for input like this in the part I write
    later on readdressing pointers)

    program example_of_recursion;

      function factorial(a: longint): longint;
        var
          c: longint;
        begin
    {1}   c := 1;
    {2}   if a > 1 then {
    {3}     c := a * factorial(a-1);
    {4}   factorial := c;
        end;

      begin
        writeln(factorial(4));
      end.
    to explain the path of logic in this program in calling the function
    factorial with regard to the variables, the biggest problem, I think,
    with understanding recursion -- if you don't understand the main body
    of the program, something is definitely wrong with you! :>  Line #'s
    are placed in {}'s above this paragraph, and below this paragraph.

       { call to factorial }
       {1} a = 4             c = 1
       {2} 4 > 1 = true
       {3} c = 4 * factorial(3);
          { call to factorial }
          {1} a = 3             c = 1
          {2} 3 > 1 = true
          {3} c = 3 * factorial(2);
             { call to factorial }
             {1} a = 2             c = 1
             {2} 2 > 1 = true
             {3} c = 2 * factorial(1);
                { call to factorial }
                {1} a = 1             c = 1
                {2} 1 > 1 = false (so the chain of calls ends...)
                {3} skipped because 2 is false.
                {4} c = 1; factorial function is 1.
                { end call to factorial }
             {4} c = (2 * 1) = 2; factorial function is 2.
             { end call to factorial }
          {4} c = (3 * 2) = 6; factorial function is 6.
          { end call to factorial }
       {4} c = (4 * 6) = 24; factorial function is 24.
       { **FINAL** termination of factorial -- return of value 24 }

    If you check the code, the final value is correct.  4! = 24.  Basically,
    with the layout I used, you can see especially also, why memory (stack
    space allocated for procedure and functions specifically) runs out
    quick, and why I say to keep the parameters and local variables for that
    matter to a minimum....

    Recursion can be used in procedures, as well as functions, for any
    repetitive action.  They are just like the function call above, which
    recursed when or until an action became true.

    To be able to extend for example, the part 8 dir clone to list and search
    for files (list all files in all dirs), we would need to add another
    boolean variable to get permission to run through all dirs encountered.
    We can re-call the directory list procedure with a regulating if variable
    of it being a directory.

    For more practice (I won't post the solution for these ones), you may wish
    to do this.  As another practice, you may wish to try and recode an integer
    power function (the "simplistic" power function) that I included in my
    solution to part 7's programming problem to use recursion.

    Practice Programming Problem #13
    ================================
    Code a program in Pascal and entirely Pascal that will make a catalog of
    the additive size of all files in all dirs on a drive specified on the
    command-line to a text file named FILESLST.TXT.

    Sample output
    -------------
    c:\>sizelist c:

    Drive: C
    C:                       131,123
    C:\DOS                 5,231,131
    ...                     ...
    C:\UTIL                3,212,985
    C:\UTIL\ACAD             131,123
                       =============
                         527,212,122

    Notes:
    1) The additive end of the listing (under the ='s) is the total size of
    the files on the drive.  You may use the function offered by the DOS
    unit to check yourself in your addition.
    2) The spacing is not exact above.  Make it look SIMILIAR to what I have
    above, but make it reasonably attractive...
    3) Use a forward.
    4) Be sure to check to be sure the drive is specified EXACTLY like above.
    5) Please use recursion for going through the drive (actually, recursion
    is probably the best way to do this).  But, be sure you put the directories
    in the order listed above.
    6) Sizes of subdirectories are not counted in the size of a main directory.
    7) Be sure to error-check the command-line.

    Next Time
    =========
    We will discuss the functions of the CRT unit.  Be sure to write comments,
    encouragements, problems, errors, to ggrotz@2sprint.net.

[Back to TUTOR SWAG index] [Back to Main SWAG index] [Original]