home   |   stacks treatise index   |   1. Intro: stack basics   |   2. subroutine return addresses & nesting   |   3. interrupts   |   4. virtual stacks   |   5. stack addressing   |   6. passing parameters   |   7. inlined data   |   8. RPN operations   |   9. RPN efficiency   |   10. 65c02 added instructions   |   11. synth instructions w/ RTS/RTI/JSR   |   12. where-am-I routines   |   13. synthesizing 65816 stack instructions   |   14. local variables, environments   |   15. recursion   |   16. enough stack space?   |   17. forming program structures   |   18. stack potpourri   |   19. further reading   |   A: StackOps.ASM   |   B: 816StackOps.ASM   |   Appendix C



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              ; Now get the n-2 term
       JSR  FIBO        ; and calculate the number for it (recursing here).
       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

Don't forget the ,X after the references to local names.  The subroutine is 34 bytes long and uses no RAM except the hardware stack.  Limit the input in this case to 13, because for simplicity, the output is only 8-bit, and the 13th Fibonacci term is 233, the highest one that can be expressed in 8 bits.  (Yes, for so few, we could more efficiently just use a look-up table of pre-calculated answers, here and with FACT (factorial) below; but the purpose is to show recursion.)  If we used two or more bytes for answers, we could go into higher terms without running out of stack space, but it does use a lot, and you do have to be careful of that when doing recursion.  The 6502 has way more than enough stack space for most normal applications—but we might say recursion is not normal.  :D  The 65816 can go further, not only because of its 16-bit stack pointer, but you can get twice as many bits of output (16) with an even shorter subroutine because of the 16-bit accumulator and the native stack-relative addressing modes, no longer needing to use X.

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'.

Again, there's no looping specified.  Total length is 25 bytes (not counting data-stack subroutines which are in Appendix A), and it does not use any RAM except the stacks.  Limit the input in this case to 8, as I did not do a double-precision output but instead kept it at 16-bit (a single ZP data-stack cell), and 9! needs more than 16 bits to represent.  8! is 40,320, and 9! is 362,880.

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