Find limit of recursion: Difference between revisions
Add 8080 assembly
(Added Wren) |
Not a robot (talk | contribs) (Add 8080 assembly) |
||
Line 8:
Find the limit of recursion.
<br><br>
=={{header|8080 Assembly}}==
The 8080 was the first Intel processor to support a stack in RAM. (Its predecessor, the 8008,
had an on-die call stack that was limited to 7 levels.) This means it was the first one on which
recursive calls could be somewhat practical. It also set the convention that the machine stack grows
downward into memory (i.e., the topmost item on the stack is one word below the second one, etc.),
which is still true on modern Intel processors.
However, it has no support for any kind of memory protection. If the stack grows too large, it will
simply overwrite other data or code, and the program will crash. This means it is up to the programmer
to take care that this does not happen. Below are two ways of finding out the maximum recursion limit
without crashing the program. (Note that they will give slightly different answers on the same system,
as one program is slightly bigger than the other, leaving a little less room for the stack.)
===Using a stack guard===
One way of doing this is by using a stack guard (also known as a stack sentinel). The technique is to
store a word of data just beyond the last byte of memory that the program wants to use. When you do
a recursive call, you first check if it is still intact. If it isn't, the next call will overwrite
something important, so in that case, the stack is full. This way, a stack overflow can be caught
at run-time, at the cost of some overhead per call.
<lang 8080asm> org 100h
lxi b,0 ; BC holds the amount of calls
call recur ; Call the recursive routine
;;; BC now holds the maximum amount of recursive calls one
;;; can make, and the stack is back to the beginning.
;;; Print the value in BC to the console. The stack is freed by ret
;;; so push and pop can be used.
;;; Make number into ASCII string
lxi h,num
push h
mov h,b
mov l,c
lxi b,-10
dgt: lxi d,-1
clcdgt: inx d
dad b
jc clcdgt
mov a,l
adi 10+'0'
xthl
dcx h
mov m,a
xthl
xchg
mov a,h
ora l
jnz dgt
;;; Use CP/M routine to print the string
pop d
mvi c,9
call 5
rst 0
;;; Recursive routine
recur: inx b ; Count the call
lxi d,-GUARD ; See if the guard is intact (stack not full)
lhld guard ; (subtract the original value from the
dad d ; current one)
mov a,h ; If so, the answer should be zero
ora l
cz recur ; If it is, do another recursive call
ret ; Return
;;; Placeholder for numeric output
db '00000'
num: db '$'
;;; The program doesn't need any memory after this location,
;;; so all memory beyond here is free for use by the stack.
;;; If the guard is overwritten, the stack has overflowed.
GUARD: equ $+2 ; Make sure it is not a valid return address
guard: dw GUARD</lang>
{{out}}
<pre>27034</pre>
(Value will differ depending on system, CP/M version, memory size, etc.)
===Calculating the value===
If all you need to know is how much room there is beforehand, it's possible to
just calculate the value. The 8080 processor decides where the stack is depending
on the <code>SP</code> (stack pointer) register, which always points to the
location of the topmost stack item (or, if the stack is considered 'empty',
it is just outside the stack).
Therefore, if you take the address of the highest byte of memory that your
program is actually using, and subtract this from <code>SP</code>, you get the
amount of free stack memory, in bytes. Because a stack item is two bytes
(addresses are 16 bits), if you then divide it by 2, you get the maximum amount
of calls you can make before the stack is full (and would overwrite your program).
<lang 8080asm> org 100h
lxi h,-top ; Subtract highest used location from stack pointer
dad sp
xra a ; This gives bytes, but a call takes two bytes;
ora h ; so HL should be divided by two to give the actual
rar ; number.
mov h,a
mov a,l
rar
mov l,a
;;; The number of free stack words is now in HL, output it
lxi d,num
push d
lxi b,-10
dgt: lxi d,-1
clcdgt: inx d
dad b
jc clcdgt
mov a,l
adi 10+'0'
xthl
dcx h
mov m,a
xthl
xchg
mov a,h
ora l
jnz dgt
;;; Use CP/M routine to print the string
pop d
mvi c,9
call 5
rst 0
;;; Placeholder for numeric output
db '00000'
num: db '$'
;;; The program does not need any memory beyond this point.
;;; This means anything from this place up to SP is free for the
;;; stack.
top: equ $ </lang>
{{out}}
<pre>27039</pre>
(Value will differ depending on system, CP/M version, memory size, etc.)
=={{header|ACL2}}==
| |||