A subroutine can be recursive, meaning that it can call itself, even over and over.  Obviously some condition will have to be reached so the subroutine will not endlessly call itself (and overflow the stack), but instead unwind itself out of many levels of nesting, and end.  When the criteria are met, it will start executing RTS's, instead of more JSR's to itself.

Each nested level of subroutine can have its own variables, even though the names are the same.  Take for example the Fibonacci ("fee-bow-nah-chee") function, which is used in economics, pseudorandom number generators, sorting and searching algorithms, and audio data file compression.  Recursion is not the only way to calculate a Fibonacci term; but although recursion is typically used for more-advanced programming applications, some smaller subroutines can be be simplified if recursion is used, and FIBO is presented here as an example of how it is done.

fiboIO:    SETL $103    ; For clarity, give names to the locals.
fiboTemp:  SETL $102    ; (Record of X will be at $101,X.)


FIBO:  CMP  #2          ; Test the input.
       BCC  end         ; If it's 0 or 1, so is the output, so just end.
                        ; This prevents endless nesting, too.  Otherwise,
       PHA              ; create local variable fiboIO, and store A there.
       PHA              ; Create another local variable byte, fiboTemp.
                        ; (Its initial value doesn't matter.)
       PHX              ; Push X too, to protect the calling routines.
       TSX              ; Prepare X to use for stack-relative addressing.

       DEA              ; Get the n-1 term
       JSR  FIBO        ; and calculate the number for it (recursing here)
       STA  fiboTemp,X  ; and store its result in local variable fiboTemp.

       LDA  fiboIO,X
       DEA
       DEA              ; Now get the n-2 term
       JSR  FIBO        ; and calculate the number for it (recursing here).
       CLC
       ADC  fiboTemp,X  ; Add those two together, and
       STA  fiboIO,X    ; store the answer.  Don't forget the ",X"!
                        ; Note that there is no looping.
       PLX              ; Restore X for the calling routines.
       PLA              ; Pull fiboTemp off the stack and discard it.
       PLA              ; Pull the answer (fiboIO) off the stack into A.
end:   RTS
 ;-------------

The factorial function can also be defined recursively by the equations 0! = 1 and, for all n > 0, n! = n((n-1)!).  This time we'll do it with a ZP data stack of 16-bit cells:

fact1: LDA  2,X         ; Get the 2nd-to-top stack cell (low byte only).
       BEQ  f1          ; If it's 0, just return.

       JSR  OVER        ; Get a copy of n
       JSR  STAR        ; and multiply the subproduct by it.

       DEC  2,X         ; Decrement n
       JSR  fact1       ; and do it again.
f1:    RTS
 ;-------------

FACT:  JSR  ONE         ; Put a 1 on the data stack as initial subproduct.
       JSR  fact1       ; Call fact1 which will call itself until finished.
       JMP  NIP         ; (JSR, RTS)  Get rid of the n'.
 ;------------------        

Binary searches (which work similar to successive approximation in A/D converters) and splay trees are a couple of other common applications of recursion.  As explained in the last section on local variables and environments, the most complex thing I've used recursion for was the full-featured text editor I wrote for my HP-71 computer which allowed local variables and environments but did not do multitasking or multithreading.  The recursion was not on a small subroutine in it, but rather that you could call the text editor itself from inside the text editor, to open another text file, and another and another, etc., then close files and back out of the nesting and go back to other files still open in the background, still with their full status undisturbed, sitting there waiting.




14. local variables, environments <--Previous   |   Next--> 16. enough stack space?

last updated Aug 15, 2015