530
fff00070ff23fe008033300f4af
^7%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

            ^7{6U N D E R S T A N D I N G  R E C U R S I O N{

                   ^6 A TUTORIAL BY SIMON NICHOLL.

^7%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

^6 Note  from  the  Editor!   The  ()  after a Procedure name should be
^6square  brackets,  this  is not an error, we use square brackets as a
^6control  code  inside  TA,  so  we  had to change them to () to avoid
^6confusing the program!

^7%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

^2                            INTRODUCTION

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

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

^2                              THE STACK

^2TO FULLY UNDERSTAND RECURSION IT IS NECESSARY TO UNDERSTAND THE STACK

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

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

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


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


^2                         RECURSION AND AMOS

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


^2                         RECURSION EXAMPLES

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


^2                             EXAMPLE R1

^1   Although AMOS provides a command to reverse a string of characters
^1(T$=FLIP$(N$)), let's consider how we could do the same without using
^1the AMOS command and by using recursion instead.  Here is some pseudo
^1code.......


^4        > CALL PROCEDURE MAIN
^4        > END PROGRAM

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


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


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


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

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

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


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

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


^2                             EXAMPLE R2

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

^4  > CALL PROCEDURE MAIN
^4  > END PROGRAM

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

^4  > PROCEDURE BACKCOUNT(COUNT)
^4      > IF COUNT IS LESS THAN 15 THEN
^4          > CALL PROCEDURE BACKCOUNT(COUNT + 1))   * RECURSIVE CALL *
^4      > END IF
^4      > OUTPUT TO SCREEN COUNT
^4  > END PROCEDURE BACKCOUNT(COUNT)

^4  > PROCEDURE SET_SCREEN
^4      > STOP COLOUR FLASHING
^4      > ERASE MOUSE POINTER
^4      > ERASE CURSOR
^4      > CLEAR THE SCREEN TO COLOUR 0
^4      > SET COLOUR 1 = TO WHITE
^4  > END PROCEDURE SET_SCREEN
     
^1   And  there  you  go.  The 2 examples are fairly similar and if you
^1understood  the  previous  example  then  you  will  have  no trouble
^1understanding  this example.  Once again the code for this example is
^1on the disk and is called RECURSION2.AMOS.  If you are having trouble
^1understanding  this  example  re-read the explanation of the previous
^1example  and  remove  the  ' by the follow command in RECURTION2.AMOS
^1BACKCOUNT procedure and step through the code.

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


^2                      MAZE.AMOS - HOW IT WORKS

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


^11. There exists a maze of size 10 by 10 units.

^12. The maze is completely surrounded by a wall.

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

^15. The program must :-

^1  a) Get from the start symbol to the finish symbol showing the route
^1     taken.

^1  b) Your program can only go via a legal route.

^1  c) If  your  program  has to retrace its steps then a backtracking
^1     symbol should be displayed.

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

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

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


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


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

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

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

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

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

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

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

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

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

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

^3                      NOW THINK ABOUT THIS!!!!!

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

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

^3                              EXAMPLE 1

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

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



^2                               EXAMPLE 2
    

^2                             BOOLEAN LOGIC

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


^4         AND                  OR                NOT
     
^4      A | B | F            A | B | F            A | F
^4      --|---|--            --|---|--            --|--
^4      0 | 0 | 0            0 | 0 | 0            0 | 1
^4      --|---|--            --|---|--            --|--
^4      0 | 1 | 0            0 | 1 | 1            1 | 0
^4      --|---|--            --|---|--
^4      1 | 0 | 0            1 | 0 | 1
^4      --|---|--            --|---|--
^4      1 | 1 | 1            1 | 1 | 1
^4      --|---|--            --|---|--


^7%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

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


^2                   HAVE FUN AND REMEMBER......

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


^3                               SIMES.

^7%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\