AMOS PD CD/amospdcd.iso/401-425/apd415/recursion.doc

Text File | 1978-01-21 | 22KB | 550 lines

============================================================================

                        *  RECURSION  - SIMES 1992 *

============================================================================


                                INTRODUCTION
                                ============

   Recursion is simply the name used to describe a programming technique
used by many programers. A recursive procedure is simply a procedure that calls
itself.


   Recursion is a vitally important topic as it allows the performing of many
calculations with the minimum of coding. By allowing a procedure to call
itself it is possible to produce staggering graphical effects, solve complex
mathematical problems, perform various searches and sorts on dynamic data
structures such as TREES and LISTS.



                                  THE STACK
                                  =========

   TO FULLY UNDERSTAND RECURSION IT IS NECESSARY TO UNDERSTAND THE STACK.


   In simple terms a stack is an area of memory where data can be temporarly
stored. Data is added to the 'TOP' of a STACK and is also removed from the
'TOP'. In other words the LAST DATA ITEM IN IS THE FIRST DATA ITEM OUT.
This is known as a LIFO structure (Last In First Out). A good way to
visualise this is to put a pack of cards on the table. To get a particular
card you must remove all the cards above it, to add a card you simply place
it on the top of the pile.


   A common application of a stack is to store the return addresses
(sometimes called link values) for procedure calls along with variable values.
Whenever you call a procedure in your AMOS program the RETURN address is
placed on 'TOP' of the STACK. If a second subroutine is then called from the
first subroutine then its RETURN address is also placed on the 'TOP' of the
stack and so on. When your procedure ends the program obtains the CORRECT
RETURN ADDRESS by getting it from the 'TOP' of the stack. This will continue
until such time as the return address to the main program is encountered.


   It is important to realise that when a procedure ends you are returned to
the line of code directly after the original procedure call and execution of
your program then continues (think about this as its crutial to recursion)
from that point e.g.


          > code
          > code
          > call SET_SCREEN  ; Call to procedure (return address on stack)
          > code             ; Execution continues here
          > code



                           RECURSION AND AMOS
                           ==================


   I haven't spoken to Francois or anyone about this but I have a sneaky
suspicion that AMOS wasn't actually designed to allow for recursion. I say
this because there is as far as I know no way to increase the size of the
available stack (from AMOS). Every time a procedure is called X amount of available
stack space is used, this means that after a certain number of recursive
calls you will get an OUT OF STACK SPACE (0): error message. Using the
SET BUFFER n command will help to aliviate the problem, but only slightly so
don't plan to do your next major project in AMOS using recursion unless you
want to play with the system libraries via the built library calls (AMOS
manual page 287) or by using machine code.




                            RECURSION EXAMPLES
                            ==================


    Enough banter lets concider some examples. I will show you 2 examples of
recursive procedures the first will work with text the second with numbers
and you will find the code for both on the disk called RECURSION1.AMOS &
RECURSION2.AMOS. You will also find a program called MAZE.AMOS on the disk
for you to play with once you have grasped the fundamentals of recursion.


                                 EXAMPLE R1
                                 ==========


   Although AMOS provides a command to reverse a string of characters
[T$=FLIP$(N$)], lets concider how we could do the same without using the
AMOS command and by using recursion instead. Here is some pseudo code.......


        > CALL PROCEDURE MAIN
        > END PROGRAM


        > PROCEDURE MAIN
        > SHARING STRINGS TEST$,NEW$
            > OPEN A LOWRES SCREEN 320 * 200 WITH 2 COLOURS
            > CALL PROCEDURE SET_SCREEN
            > SET TEST$ = "EVIL RATS"
            > SET NEW$  = ""
            > OUTPUT TO SCREEN "ORIGINAL STRING WAS "
            > OUTPUT TO SCREEN VALUE IN TEST$
            ----------------------------------------------------
            > CALL PROCEDURE BACKWARDS[1] (PASSING A VALUE OF 1)
            ----------------------------------------------------
            > OUTPUT TO SCREEN "REVERSED STRING IS  "
            > OUTPUT TO SCREEN VALUE IN NEW$
            > OUTPUT TO SCREEN "PRESS A KEY TO END"
            > WAIT FOR KEY PRESS
        > END PROCEDURE MAIN


        > PROCEDURE BACKWARDS[COUNT]
        > SHARING STRINGS TEST$,NEW$
            > IF COUNT IS LESS THAN LENGTH OF TEST$ THEN
                > CALL PROCEDURE BACKWARDS[COUNT + 1]    * RECURSIVE CALL *
            > END IF
            > SET NEW$=NEW$+THE COUNT'th CHARACTER OF TEST$
        > END PROCEDURE BACKWARDS[COUNT]


        > PROCEDURE SET_SCREEN
            > STOP COLOUR FLASHING
            > ERASE MOUSE POINTER
            > ERASE CURSOR
            > CLEAR THE SCREEN TO COLOUR 0
            > SET COLOUR 1 = TO WHITE
        > END PROCEDURE SET_SCREEN


   Ok that was fairly painless, I'm not going to concider the procedures
MAIN or SET_SCREEN as they are routine stuff and if you can't follow them
then you are way over your head trying to understand recursion.


   The first call to the procedure BACKWARDS is from the procedure Main and
I have highlighted it with ---- characters both above and below the relevant
line.


   We enter the BACKWARDS procedure for the 1st time passing the value of
1 to the variable COUNT. The code then tests to see if COUNT < the length of
TEST$ if it is then a RECURSIVE CALL is made to BACKWARDS passing the
current value of COUNT + 1. Each RECURSIVE CALL results in return addresses
etc being saved on the STACK (see page 1). Once COUNT = the length of TEST$
(in this case 9) the IF construct is skipped and NEW$ is set to = NEW$ + the
9th character of TEST$ i.e NEW$="S". The next line of code encountered is an
END PROCEDURE statement.


   At this point the STACK is checked to get the relevant RETURN ADDRESS and
any variable values. The ADDRESS on the 'TOP' of the STACK is to the END IF
in the procedure BACKWARDS and the value of the variable COUNT is 8. The
NEW$ instruction is again performed this time with the value of 8, resulting
in NEW$="ST" this continues until count becomes 1 and we retrieve the return
address of the procedure MAIN at which point the complete string will be
reversed in NEW$.


   You will find the code to perform this task on the disk under the title
RECURSION1.AMOS. I recomend that you un-comment the follow command at the
beginning of the BACKWARDS procedure and step through the code a line at a
time to see exactly what is happening.


                              EXAMPLE R2
                              ==========


   This time I'm going to show you how to print numbers backwards from 15 to
0. Don't forget that both the previous example and this example are for
demonstration purposes and I would not recomend using recursion to do this
under normal circumstances. Here is some pseudo code.


        > CALL PROCEDURE MAIN
        > END PROGRAM


        > PROCEDURE MAIN
            > OPEN A LOWRES SCREEN 320 * 200 WITH 2 COLOURS
            > CALL PROCEDURE SET_SCREEN
            > OUTPUT TO SCREEN "COUNTING BACKWARDS FROM 15 TO 0"
            > OUTPUT TO SCREEN "-------------------------------"
            ----------------------------------------------------
            > CALL PROCEDURE BACKCOUNT[0] (PASSING A VALUE OF 0)
            ----------------------------------------------------
            > OUTPUT TO SCREEN "PRESS A KEY TO END"
            > WAIT FOR KEY PRESS
        > END PROCEDURE MAIN


        > PROCEDURE BACKCOUNT[COUNT]
            > IF COUNT IS LESS THAN 15 THEN
                > CALL PROCEDURE BACKCOUNT[COUNT + 1]    * RECURSIVE CALL *
            > END IF
            > OUTPUT TO SCREEN COUNT
        > END PROCEDURE BACKCOUNT[COUNT]


        > PROCEDURE SET_SCREEN
            > STOP COLOUR FLASHING
            > ERASE MOUSE POINTER
            > ERASE CURSOR
            > CLEAR THE SCREEN TO COLOUR 0
            > SET COLOUR 1 = TO WHITE
        > END PROCEDURE SET_SCREEN


   And there you go. The 2 examples are fairly similar and if you understood
the previous example then you will have no trouble understanding this
example. Once again the code for this example is on the disk and is called
RECURSION2.AMOS. If you are having trouble understanding this example re-
read the explination of the previous example and remove the ' by the follow
command in RECURTION2.AMOS BACKCOUNT procedure and step through the code.


   I would like to have gone into this further but time is pressing so I
will leave it at this point. I hope to include a better tutorial in issue 4
of Peter Hickmans Totally Amos Magazine so if your stuck get a copy of that
otherwise write to me at the usual address and I will try to help.



                        MAZE.AMOS HOW IT WORKS
                        ======================


   MAZE.AMOS is an example of what it is possible to achieve using
recursion. The idea is :-


     1] There exists a maze of size 10 by 10 units.

     2] The maze is completely surrounded by a wall.

     3] There is a start symbol (S) and a finish symbol (F) the coordinates
        of which are entered by you. Legal range is from 2-9

     5] The program must :-

          A] Get from the start symbol to the finish symbol showing the
             route taken.

          B] Your program can only go via a legal route.

          C] If your program has to retrace its steps then a backtracking symbol
             should be displayed.

          D] If you can not get to the finish symbol your program should
             indicate that the maze can not be solved. To achieve this
             enter 4,5 for the Finish coordinate.


   Run the program MAZE.AMOS to get a clear idea of what is happening and
get a listing of the program so you can follow through the code.


   Once again I'm going to concentrait on the recursive procedure
TRACK[ROWS,_COLS]. One important point you should realise is that the maze
is held in memory in the form of an array called MAZE$, lets look at some
pseudo code for the procedure TRACK[ROWS, _COLS].


         > PROCEDURE TRACK[ROWS, _COLS]
         > SHARING MAZE$()
             '
             ' ================================================
             '         TRY GOING UP FROM CURRENT POSITION
             ' ================================================
             ' ************************************************
             > IF MAZE$(ROWS-1,_COLS) = "." AND NOT SOLVED THEN
                 > IF ROWS -1 = 1 THEN
                     > SET POSY = 63
                 > ELSE
                     > SET POSY = (((ROWS-2)*13)+63)
                 > END IF
                 > IF _COLS = 1 THEN
                     > SET POSX = 8
                 > ELSE
                     > SET POSX = (((_COLS-1)*13)+8)
                 > END IF
                 > PUT BOB ON SCREEN AT POSX, POSY USING IMAGE 1
                 > SET MAZE$(ROWS-1, _COLS) = "O"
                 > CALL PROCEDURE TRACK[ROWS-1, _COLS]
             > ELSE
                 > IF MAZE$(ROWS -1, _COLS) = "F" THEN
                     > SET SOLVED = TRUE
                 > END IF
             > END IF
             '*************************************************
             ' ================================================
             '        TRY GOING RIGHT FROM CURRENT POSITION
             ' ================================================
             '
             > IF MAZE$(ROWS,_COLS+1) = "." AND NOT SOLVED THEN
                 > IF ROWS = 1 THEN
                     > SET POSY = 63
                 > ELSE
                     > SET POSY = (((ROWS-1)*13)+63)
                 > END IF
                 > IF _COLS+1 = 1 THEN
                     > SET POSX = 8
                 > ELSE
                     > SET POSX = (((_COLS)*13)+8)
                 > END IF
                 > PUT BOB ON SCREEN AT POSX, POSY USING IMAGE 2
                 > SET MAZE$(ROWS, _COLS) = "O"
                 > CALL PROCEDURE TRACK[ROWS, _COLS+1]
             > ELSE
                 > IF MAZE$(ROWS, _COLS+1) = "F" THEN
                     > SET SOLVED = TRUE
                 > END IF
             > END IF
             '
             ' ================================================
             '      TRY GOING DOWN FROM CURRENT POSITION
             ' ================================================
             '
             > IF MAZE$(ROWS+1, _COLS)="." AND NOT SOLVED THEN
                 > IF ROWS +1 = 1 THEN
                     > SET POSY = 63
                 > ELSE
                     > SET POSY = (((ROWS)*13)+63)
                 > END IF
                 > IF _COLS = 1 THEN
                     > SET POSX = 8
                 > ELSE
                     > SET POSX = (((_COLS-1)*13)+8)
                 > END IF
                 > PUT BOB ON SCREEN AT POSX, POSY USING IMAGE 3
                 > SET MAZE$(ROWS+1, _COLS) = "O"
                 > CALL PROCEDURE TRACK[ROWS+1, _COLS]
             > ELSE
                 > IF MAZE$(ROWS +1, _COLS) = "F" THEN
                     > SET SOLVED = TRUE
                 > END IF
             > END IF
             '
             ' ================================================
             '      TRY GOING LEFT FROM CURRENT POSITION
             ' ================================================
             '
             > IF MAZE$(ROWS, _COLS-1)="." AND NOT SOLVED THEN
                 > IF ROWS = 1 THEN
                     > SET POSY = 63
                 > ELSE
                     > SET POSY = (((ROWS-1)*13)+63)
                 > END IF
                 > IF _COLS-1 = 1 THEN
                     > SET POSX = 8
                 > ELSE
                     > SET POSX = (((_COLS-2)*13)+8)
                 > END IF
                 > PUT BOB ON SCREEN AT POSX, POSY USING IMAGE 4
                 > SET MAZE$(ROWS, _COLS-1) = "O"
                 > CALL PROCEDURE TRACK[ROWS, _COLS-1]
             > ELSE
                 > IF MAZE$(ROWS, _COLS-1) = "F" THEN
                     > SET SOLVED = TRUE
                 > END IF
             > END IF
             ' ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
             ' ================================================
             '      BLOCKED SO BACKTRACK AND LEAVE X BEHIND
             ' ================================================
             '
             > IF MAZE$(ROWS, _COLS)<>"F" THEN
                 > IF MAZE$(ROWS,_COLS) <> "S" AND NOT SOLVED THEN
                     > WAIT 20
                     > IF ROWS = 1 THEN
                         > SET POSY = 63
                     > ELSE
                         > SET POSY = (((ROWS-1)*13)+63)
                     > END IF
                     > IF _COLS-1 = 1 THEN
                         > SET POSX = 8
                     > ELSE
                         > SET POSX = (((_COLS-1)*13)+8)
                     > END IF
                     > PUT BOB ON SCREEN AT POSX, POSY USING IMAGE 7
                 > ELSE
                     > IF MAZE$(ROWS, _COLS-1) = "S" AND NOT SOLVED THEN
                         > DISPLAY "MAZE CAN'T BE SOLVED" BOB AT 56,206 IMAGE 7
                         > WAIT 20
                     > END IF
                 > END IF
             > END IF
             '~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
         > END PROCEDURE TRACK[ROWS, _COLS]


   At first glance this appears to be very complex, but in actual fact its
NOT (trust me!). First of all notice that the procedure is broken up into 5
distinct parts. The first 4 parts deal with deciding if it is possible to go
in 1 of 4 possible directions (up, right, down, left) relative to the
current position. The 5th part of the procedure deals with what to do when
a dead end is encountered i.e how to backtrack leaving an 'X'.


   I will deal with the direction sections first and will concentrait on the
first section outlined above and below with ****** characters understand
this section and all 4 sections can be understood.


   The first instruction Wait 20 simply slows the program down so we can see
whats going on otherwise it's all over before it began comment it out in the
code and see what I mean.


   The 1st If ELSE construct asks if the character 1 row up and in the same
column from where we currently are is a '.' (refer to example 1)


   If this expression evaluates to true (i.e the character is a '.') then
the second part of the if is evaluated. This states AND NOT SOLVED. I
previously set SOLVED to FALSE so this expression will always evaluate to
TRUE until such time as SOLVED is set to TRUE. But wait what about the AND
well a logical AND evaluates to TRUE if both halves of the expression are
true. (see example 2 AND function)


   The 2nd & 3rd IF ELSE conditions are used to workout where to position the
bobs on the screen. Guess what you can figure this bit out... hint
63=starting Y coordinate, 8 = starting X coordinate, 13=width of a bob,
ROWS are equivalent to POSX, _COLS are equivalent to POSY.


   The instruction MAZE$(ROWS-1, _COLS)="O" places an "O" in the array MAZE$
in place of the '.' character. This is done so that we know where we have
been.


   The next instruction is the RECURSIVE CALL. We call the procedure again
passing the value of ROWS-1, _COLS into the procedure heading variables so
this time ROWS, COLS is called with 2,1 (using example 1 S values).


   If the first IF condition had evaluated to FALSE then the ELSE would
have been performed by default. This has a nested If condition that sets
SOLVED to TRUE if the end (donated by the F character) has been found.
Otherwise the 2nd of the direction sections is tried, then the third and so
on. If all directions fail then the 5th section of code comes into play.


   The 5th section of the code (marked ~~~~ above and below) deals with
backtracking. Backtracking occurs when we can't go in any direction other
than that from which we came. There are 2 IF conditions here (we should only
have 1 but AMOS seems to have a few bugs in this area.) that test to see if
the current position is NOT an "S" or an "F" character and that SOLVED is
FALSE (NOT TRUE). This being the case then we wait 20 again calculate the
bob position and display it the bob bing an 'X' character.


                       NOW THINK ABOUT THIS!!!!!


   We then hit the ELSE which is ignored as are the 3 END IF statements
(so far so good) the END PROC statement then turns up. No we DON'T return to
the main code, this is a recursive program so there is a load of RETURN
ADDRESSES and VARIABLE values on the STACK. The RETURN ADDRESS and VARIABLE
values (ROWS, _COLS) that are on the top of the STACK are POPPED (correct term for
removed from the STACK complimented by PUSHED which means added to the STACK) and
and the program returns to the line of code after the RECURSIVE CALL and
continues with the previous values of ROWS and _COLS which will be 1 square
back from the dead end. I can hear the quick among you saying "but what
stops the program from going back there again?" well remember the 4
direction sections? The code is entered if a '.'character is found and before
its left the the '.' character is changed to a 'O' character which prevents
the program from going back to that location again, got it.


   Should the initial IF conditions not be met then the ELSE is performed by
default. This has a nested IF which checks to see if the current character
we are on is an 'S'. If this is the case then we have backtracked all the
way to the beginning of the maze which means the maze can't be solved a
message is displayed to say this and the END PROC statement is encountered,
this time however when the RETURN ADDRESS is POPPED from the STACK it is the
address of the MAIN code and the program ends.



                              EXAMPLE 1
                              =========


                 COLUMNS
                 =======
                                      WHERE WE ARE (USING S AS START POINT)
          1 2 3 4 5 6 ETC -->

       1  X X X X X X X X X X X      (ROWS,_COLS)   = 3,3 = 'S'
       2  X . . . . . . . . . X
       3  X . S . . . . . . . X      (ROWS-1,_COLS) = 2,1 = UP
ROWS   4  X . . . . X X X . . X
====   5  X X . X . X X X . X X      (ROWS,_COLS+1) = 3,4 = RIGHT
       6  X . . . . X . . . . X
       7  X . . . X . . F . . X      (ROWS+1,_COLS) = 4,3 = DOWN
       8  X X . . . . . . . . X
       9  X X X X X X X X X X X      (ROWS,_COLS-1) = 3,2 = LEFT



                               EXAMPLE 2
                               =========


                             BOOLEAN LOGIC
                             =============

           A&B = VARIABLES : F= RESULT : 0 = FALSE : 1 = TRUE


         AND                  OR                NOT

      A | B | F            A | B | F            A | F
      --|---|--            --|---|--            --|--
      0 | 0 | 0            0 | 0 | 0            0 | 1
      --|---|--            --|---|--            --|--
      0 | 1 | 0            0 | 1 | 1            1 | 0
      --|---|--            --|---|--
      1 | 0 | 0            1 | 0 | 1
      --|---|--            --|---|--
      1 | 1 | 1            1 | 1 | 1
      --|---|--            --|---|--


    That is your lot for this time, but if you need help then write to the
address in the code and I will try to help.


                   HAVE FUN AND REMEMBER......

                   NO MATTER WHERE YOU GO.....THERE YOU ARE!


                               SIMES.

PS - Sorry about the spelling but I simply don't have time to check this.