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