|
|
Recursion is the process of looping over a
certain area of code repeatedly, until the loop is "broken" out of when
a certain condition is met. For instance, if you wanted some code
to perform a certain action eight times, you could write a recursive algorithm
to execute the same code that many times, rather than writing out the code
segment eight seperate times.
This next block of code will use the b register
as a counter. When B becomes 0, the loop will terminate.
ld b,8
;let's run the loop 8 times
add_hl_de_loop:
;label the place where you want the recursion to begin
add hl,de
;the action of the loop ... we want to perform this action 8 times
dec b
;decrement b; set the zero flag if it becomes zero, reset it otherwise
jr nz,add_hl_de_loop ;continue
the until B becomes zero
The result of this is that DE is added to HL eight times. From there it continues executing on the next line of code. But a recursive loop can also be structured as call; as a call it will be capable of inputting the number of recursions. Here, for instance, is a call that will do the same as above, only it will additionally input the number of recursions in B:
add_hl_de:
;the name of this call
add hl,de
;the recursive action
dec b
;decrement the counter (inputted -- at most 255)
ret z
;return from the call when B reaches 0
jr add_hl_de
;if B is not 0, keep looping
Now DE was added to HL B number of times. If HL was initially zero, then the effect of this call was to multiply DE by B, storing the result to HL. Since the Z80 has no multiplication instruction, recursion of this kind is employed often, even though in most cases it is very slow. Later on, I may show you a faster algorithm for multiplication.
Two instructions that are useful in manipulating
counters: inc and dec, or increment and decrement. The operand of
this instruction can be a register or indirect address (<inc a>, <dec
(hl)>) or a register pair (<inc de>, <dec ix>). Incrementing
and decrementing of the first kind will set the zero and sign flags according
to the result of the active operand. The carry flag will always be
reset. For example, with 0 in E, <dec e> will reset the zero flag,
reset the carry, and set the sign flag. Inc and dec of a register
pair, however, has no affect on any of the flags.
Now that you understand two important instructions
that I've so far neglected, we can move one step further, combining the
decrement instruction into another instruction specialized for recursion
called djnz. Djnz (decrement, jump if not zero) will decrement the
B register and then make an absolute jump to the provided label unless
B becomes zero. djnz label Here's the first loop again,
modified to use djnz:
ld b,8
;initialize counter to loop 8 times
add_hl_de_loop:
add hl,de
djnz add_hl_de_loop ;decrement
B, continue once B is zero
This is an obviously useful instruction, and it shows why B should be the primary register to use as a counter.
A counter is one method of controlling recursion, but really anything that sets a flag can be checked and used to break a recursive loop. If you want to break the loop when A becomes $3c, then <sub $3c> will set the zero flag and break the loop. There is one fundamental problem with this, however; <sub $3c> destroys the content of the A register, making it impossible to do any recursion of this kind, bringing us into the depths of contact with yet another extremely important instruction: cp, or the compare instruction. It does the same as the sub instruction -- subtract the operand from the A register and set the approiate flags -- but with one important difference: it doesn't affect the contents of the A register, but it does set the flags as though a subtraction took place. If A is 22 when <cp 22> is executed, then the zero flag will be set and the sign and carry flags reset. If A is 21 when <cp 22> is executed, then the zero flag will be reset and the sign and carry flags will be set. If A is 23 when <cp 22> is executed, then all flags will be reset. In this way, cp can be used to test greater than and less than operations. If A is greater than the operand, all flags are reset; if A is equal to the operand, only the sign flag is set; if A is less than the operand, the sign and carry flags are set and the zero flag reset. Here is an example:
cp d
;compare A to D
jr z,d_equal_to_a
;z is only set when D is equal to A
jr c,d_greater_than_a ;c
is only set when D is greater than A
jr nc,d_less_than_a
;nc means D is less than or equal to A, but we already checked z
You could use the P and M conditions in the place
of NC and C, but you would have to change the relative jump to an absolute
jump.
So, as an example, here is the chess square problem
from the last section solved using recursion and the compare instruction.
This method is slower because it has to loop several times.
square_info:
and %111111
;the square can't be more than 63
ld b,0
;intialize the number of accumulated rows as 0
sub_loop:
sub 8
;subtract 1 row
inc b
;the number of times the loop is run will represent the row
cp 8
;when A becomes less than 8, break the loop
jr nc,sub_loop
;is A still greater than or equal to 8? then continue looping
ld c,a
;the remainder in A is the column; put it into C
xor b
;is the square black?
and %1
ret
Loops can also be nested within each other; one loop, the inner loop, will execute as many times as required times the number of times as the outer loop is required to execute. Here is an example of a nested loop (in the form of a call) that delays the processor for exactly five seconds:
timer5:
ld e,$35
;outer loop to run $35 times
j60:
ld b,$ff
;first inner loop to run $ff times
j61:
ld d,$ff
;second inner loop to run $ff times
j62:
dec d
;dec second inner counter
jp nz,j62
;check it for zero
dec b
;dec first inner counter
jp nz,j61
;check for zero
dec e
;dec outer counter
jp nz,j60
;check for zero
ret
This routine uses a nested loop within a nested loop, using three counters -- B,D and E -- to keep track of current number of loops. The effect of this routine is that the elapsed time from <ld e,$35> to <ret> will be exactly five seconds. Adjusting the value put into E in the first instruction will vary the number of seconds that the processor delays -- the greater the number, the longer it will delay.
Here are some more instructions that you might not
find useful right away, except in a few circumstances. These are
the shift and rotate instructions. As you saw in the previous section,
I used <srl b> to divide B by two. Shift right logically (srl)
shifts all the bits in the operand one to the right, copying bit 0 into
the carry flag; in binary this produces the same result as dividing the
operand by two, with any remainder recorded by the carry flag. So
then, any division by the power of two can quickly be done using srl.
It would take four srl instructions to divide by 16.
The only problem with this, however, is that you
can't shift negative numbers to a negative result because of how the sign
bits are set up. There is another instruction you can use, though,
called sra (shift right arthmeticly). Sra will not change the sign
bit as it shifts right, nor will it shift the sign bit; so, when C is -44
<sra c> will have the result of -22 in C with the carry flag reset (-45
in C followed by <sra c> will result in -22 in C with the carry flag
set). Both srl and sra will set the zero flag if the result is zero
and set the sign flag if the result is negative.
Shifting left is similar and can be accomplished
using the instruction sla (shift left arithmeticly). As you would
expect, this multiplies the operand by two, by shifting all bits of the
operand left and moving bit 7 into the carry flag. When multiplying
the A register by two, though, you should always use <add a,a> because
it does the same and is one byte shorter. If the byte addressed by
IX contains 3, then <sla (ix)> will change that byte to 6, resetting
the carry, zero and sign flags.
Rotation instructions rotate the operand: rather than destroying bit 0 as when shifting right, rotating right will move that lost bit around into bit 7. A second type of rotate can also occur, called rotating through the carry: rotating right through the carry will move bit 0 only to the carry flag, also moving the old carry flag into bit 7. Here's a short sumarry of rotate instructions:
rl operand - rotate operand left through the carry
flag; 2 bytes
rla - rotate the accumulator (register A) left through
the carry flag; 1 byte
rlc operand - rotate operand left through bit 7;
2 bytes
rlca - rotate the accumulator left through bit 7; 1 byte
rr operand - rotate operand right through the carry
flag; 2 bytes
rra - rotate the accumulator right through the carry flag;
1 byte
rrc operand - rotate operand right through bit
7; 2 bytes
rrca - rotate the accumulator right through bit 7; 1 byte
All rotation instructions only affect the carry flag.