APPENDIX: Recursive Procedure Calls
Updated: Jan 22, 2006

Please consider this code based on a user test program:

=====ricorre.bas
$AppType CONSOLE: $TypeCheck ON
declare sub ricorre (dai as integer)

sub ricorre
defint f
if dai < 10 then
  f = dai + 1
  ricorre f
  print f
end if
end sub

ricorre 0
pause
=====ricorre.bas

Variable f is "local".  The compiler Symbol Table will list it as "ricorref",
a concatenation of the procedure name and the source code variable name "f".

In HotBasic, variable f is not a temporary stack location but rather a general
dimensioned item.  As such, code *outside* the procedure could conceivably
reference this value of f by using "ricorref".

ricorre.bas prints 10, 10, etc; although you might expect it to print 10, 9,
... , 1 instead.  What is wrong?  Each recurrent call (re-entrance) into the
procedure may overwrite f.  The solution:

=====ricorre1.bas
$AppType CONSOLE: $TypeCheck ON
declare sub ricorre (dai as integer)

sub ricorre
defint f
push f
if dai < 10 then
  f = dai + 1
  ricorre f
  print f
end if
pop f
end sub

ricorre 0
pause
=====ricorre1.bas

Now the general rule:  If a procedure wants to access data after a recursive
call (to itself), it saves that data first *before* calling the procedure again
recursively which may overwrite it and restores it after the call.

Thus, for recursive procedures, usually the first item of business on entry is
to save values that might be needed in the procedure code after the recursive
call.

Typically, the last item of business for such a procedure is to restore the
values before its end.  Thus, when the procedure resumes after the recursive
call, all data needed from this point to the end of the procedure is the same
as it was before the call to itself.

Therefore, *all* code which might cause an exit from the procedure must GOTO
the common end-point where values are restored.  Thus, all PUSH statements (or
equivalent) are matched with a POP operation.

Note that a recursive procedure call might be conditional.  In short, recursive
procedures are written so they behave the same regardless of whether or not
there was a recursive call in an particular call instance.

Above we use the stack; but PUSH and POP work only for 2- and 4-byte values
like f above.  A number of techniques may be used to save and restore other
values such as STRING and DOUBLE.

A STRING example:

  Declare SUB PushStr(str1 As STRING)
  Declare FUNCTION PopStr As STRING

  'now we make a "string stack" array and its pointer spSTK
  DIM strSTK(24) As STRING, spSTK As LONG

  SUB PushStr(str1 As STRING)
  INC(spSTK): strSTK(spSTK)=str1
  END SUB

  FUNCTION PopStr
  RESULT=strSTK(spSTK): DEC(spSTK)
  END FUNCTION

Please note that STRING array strSTK() is our "string stack" designed to hold
up to 24 strings of maximum length of 256 bytes each -- the default for
As STRING without [*n] syntax specifying an alternate maximum.

Also, SUB PushStr does not check for "stack overflow" where stack pointer
spSTK might be greater than 24.

These factors may be considered when you might create your own STRING stack.
For other variable types, such as DOUBLE, the code above may be modified to
create PushDbl() and PopDbl procedures.

Now that we know how to do it, let us hasten to add that recursive procedure
calls are suggested only for simple situations because of limited application
stack space (used in the PUSH and POP statements).

Application-created stacks, used in PushStr() and PopStr above, may be designed
to hold larger numbers of values in order to achieve deeper levels of recursion.

Indeed, for more complex situations, *simulation* of recurive calls is better
than actually doing recursive calls.  Through simulation one may better handle
large blocks of data and/or deeper levels of recursion.

Example:  game situations -- chess, war games, etc, where the "value" of a
potential game move needs to be evaluated multiple times in view of an array of
potential opponent moves looking ahead "into the future". In such cases, one
would simulate recursion rather than actually do it.

For deep levels of recursion or when large amounts of data are involved, an
entire hard drive may be required to hold the "temporary simulated stack" data.

Of course, simulating recursion is natural, when it comes to computing where
almost everything is simulated.  Unforturnately,

  PRINT "$1,000,000.00"

only simulates one million dollars with pixels on a screen.  Alas, I would
rather have the real thing!

Copyright 2006 James J Keene PhD
Original Publication: Jan 21, 2006