!lm12
!rm75
Another Recursive Macro...........................Lee Meador

Last month I sent Bob a recursive macro definition that he put in the AAL for everyone to see.  In case you have forgotten what recursive means, let me explain it somewhat.  If you have a macro thatcalls itself under certain conditions, that macro is called 'recursive'.  It's kind of like the plastic cup I had when I was little.  There was a picture on the cup of a little bear sitting in a high-chair.  The bear was holding a plastic cup and on the cup was a picture of a little bear in a high-chair holding a plastic cup with a picture of a bear in a high-chair holding a cup with a picture of a bear......

I always used to wonder how many bears there were and how big the littlest one was.  Now, when we are using recursion in our macros we want to be sure we know that there is a last little bear -- a last call -- a way of leaving the lowest level of recursion.  Otherwise (since each recursive call uses up some memory/stack space) we will soon run out of room to store the return information and BOOM goes the assembly.

My macro uses the principle of 'divide and conquer' to allocate a chosen number of bytes all of which hold the value we want them to have.  We might use this macro with a table of 128 bytes.  All non-alphabetic characters (codes $0 to $40, plus assorted others) will have the value $FF in their corresponding bytes in the table.  All alphabetics will have a number indicating their relative frequency in English text.  We could set up the table with lines and lines of hex strings for all the non-alphabetics.  Or we could let the program filter out the alphabetics and use a shorter table.  But for the sake of the example let us assume we need the program to be as fast as possible and memory space is no object.
Here is the macro definition I came up with:

!lm17
.MA DB          Macro name is "DB"
.DO ]1<2        If only one left,
.DA ]2             generate a data byte
.ELSE           If more than one left,
>DB ]1/2,]2        call DB for half of them,
>DB ]1+1/2,]2      and call DB again for the other half
.FIN
.EM
!lm12

Here is the table I talked about:
!lm17

>DB $41,#$FF   65 bytes filled with $FF
.HS 00000000   upper case (fill in your own frequencies)
......
>DB 5,#$FF     5 bytes filled with $FF
.HS 00000000   lower case
......
>DB 5,#$FF     5 bytes filled with $FF
!np
!lm12

Here is a sample program to use such a table:

!lm17
LDA CHARACTER.BYTE    get character
TAY
LDA TABLE,Y           get frequency
......                and then you have to use it
!lm12

The macro calls itself to set up half of the area desired and then calls itself again to set up the other half.  The adding of one to the second call makes sure that both odd and even values for the first parameter will work.  If the call only needs one byte to be set up then a .DA is used to take care of it.  That provides the end of the little bears -- when the first parameter is one.

When I needed a macro like this my first idea was to have each recursive call take care of one byte and then call itself to take care of the rest.  If the macro was called with zero repetitions then nothing would be done except end the macro.  The problem with that method is the amount of stack space used as the recursion goes to very deep levels.  The method used in the example will only recurse, for example, 8 levels to generate 127 bytes of data.

By the way, notice that you must put the pound sign (#) on the second parameter if you want to generate single bytes.  Leaving it off will generate two-byte values of data.  I chose that method to make the macro more flexible.  You might want to put the pound sign (#) inside the macro to make it safer in case you always want to generate single bytes of data.  Also, you can use calculated values like #'F+$80 to generate tables of some character value.

The assembly of recursive macros produces quite a few extra lines in the listing, so after checking it out you will probably want to turn off the listing of the macro expansion with ".LIST MOFF".  Here is a sample listing with the macro expansion listing on:

<listing here>
