Mutual recursion: Difference between revisions
add 8080 assembly version
(add Tailspin solution) |
Not a robot (talk | contribs) (add 8080 assembly version) |
||
Line 18:
then state this rather than give a solution by other means).
<br><br>
=={{header|8080 Assembly}}==
The 8080 processor has built-in support for recursion, at the instruction level.
The processor keeps a <em>stack pointer</em>, called <code>SP</code>,
which is a 16-bit register that can be set by the program to point anywhere in the address space.
The stack pointer points to the topmost word on the stack. The stack grows downward into memory:
when a word is pushed onto the stack, the SP is decremented by 2, and the word written
at the new location. When a word is popped from the stack, it is read from the location the
SP is pointing to, and afterwards the SP is incremented by 2.
The instruction set includes a <code>call</code> instruction, which pushes the location of the
next instruction onto the stack, and then jumps to the given location. Its counterpart is the
<code>ret</code> instruction, which pops a location from the stack and jumps there.
There are also <code>push</code> and <code>pop</code> instructions, to push and
pop the values of register
pairs on and off the stack directly. This can be used, among other things, to save 'local variables'
in a recursive routine, as the code below does.
<lang 8080asm> org 100h
jmp test
;;; Implementation of F(A).
F: ana a ; Zero?
jz one ; Then set A=1
mov b,a ; Otherwise, set B=A,
push b ; And put it on the stack
dcr a ; Set A=A-1
call F ; Set A=F(A-1)
call M ; Set A=M(F(A-1))
pop b ; Retrieve input value
cma ; (-A)+B is actually one cycle faster
inr a ; than C=A;A=B;A-=B, and equivalent
add b
ret
one: mvi a,1 ; Set A to 1,
ret ; and return.
;;; Implementation of M(A).
M: ana a ; Zero?
rz ; Then keep it that way and return.
mov b,a
push b ; Otherwise, same deal as in F,
dcr a ; but M and F are called in opposite
call M ; order.
call F
pop b
cma
inr a
add b
ret
;;; Demonstration code.
test: lhld 6 ; Set stack pointer to highest usable
sphl ; memory.
;;; Print F([0..15])
lxi d,fpfx ; Print "F: "
mvi c,9
call 5
xra a ; Start with N=0
floop: push psw ; Keep N
call F ; Get value for F(N)
call pdgt ; Print it
pop psw ; Restore N
inr a ; Next N
cpi 16 ; Done yet?
jnz floop
;;; Print M([0..15])
lxi d,mpfx ; Print "\r\nM: "
mvi c,9
call 5
xra a ; Start with N=0
mloop: push psw ; same deal as above
call M
call pdgt
pop psw ; Restore N
inr a
cpi 16
jnz mloop
rst 0 ; Explicit exit, we got rid of system stack
;;; Print digit and space
pdgt: adi '0' ; ASCII
mov e,a
mvi c,2
call 5
mvi e,' ' ; Space
mvi c,2
jmp 5 ; Tail call optimization
fpfx: db 'F: $'
mpfx: db 13,10,'M: $'</lang>
{{out}}
<pre>F: 1 1 2 2 3 3 4 5 5 6 6 7 8 8 9 9
M: 0 0 1 2 2 3 4 4 5 6 6 7 7 8 9 9</pre>
=={{header|ABAP}}==
| |||