Find limit of recursion: Difference between revisions
added section for Z80 Assembly
(Find limit of recursion in XBasic) |
Puppydrum64 (talk | contribs) (added section for Z80 Assembly) |
||
Line 3,247:
Segmentation fault (core dumped)
</pre>
=={{header|Z80 Assembly}}==
Unlike the 6502, the Z80 has a 16-bit stack pointer that is fully relocatable. Therefore, the limit of recursion technically depends on how much RAM you have, but for the purposes of this task we'll define it as so:
The maximum number of instructions that have a <code>push</code> effect (including <code>push</code>, <code>call</code>, <code>rst</code>, etc.),before RAM that was not intended to be part of the stack area (i.e. the heap) becomes clobbered. For this task we'll assume that interrupts are disabled, and no hardware exists that would generate an NMI. (Both of those operations put return addresses on the stack and can do so at any time during our code execution so for simplicity we'll ignore them.
To give the maximum limit, we'll say that there is only one variable (we need one to store the stack pointer), and the entire address space of the CPU exists and is in RAM (i.e. 64k of RAM, including the beginning vector table, program code, and stack space, no address mirroring. Also we'll assume there is no "video memory" or anything not intended for a specific purpose.) A byte count of each line of code is also provided.
<lang z80>org &0000
LD SP,&FFFF ;3 bytes
loop:
or a ;1 byte, clears the carry flag
ld (&0024),sp ;4 bytes
ld hl,(&0024) ;3 bytes
push af ;1 byte
ld bc,(&0024) ;4 bytes
sbc hl,bc ;4 bytes
jr z,loop ;2 bytes
jr * ;2 bytes
;address &0024 begins here
word 0 ;placeholder for stack pointer</lang>
This is the minimum amount of code I can come up with that can check for the limit. (Note that this code has no way to display the results of the test to the user, so on real hardware the limit of recursion is much less, but for an emulator this will suffice.) The concept here is relatively simple. Do the following in a loop:
* Store the stack pointer into memory.
* Load it into HL.
* Push a value. This will cause the real stack pointer to decrement and the pushed value will be written to memory.
* After the push, load from the same memory location into BC. If we haven't reached the limit of recursion, HL = BC.
* The <code>CP</code> instruction only compares the accumulator to an 8 bit register, so to compare HL to BC we actually have to subtract them. If the result is zero, they were the same to begin with.
* If they're different, then the act of pushing AF clobbered the stack pointer we backed up in step 1. This means recursion is at its limit, so quit looping and halt the CPU.
=={{header|zkl}}==
| |||