Mutual recursion: Difference between revisions
Content added Content deleted
(add Tailspin solution) |
Not a robot (talk | contribs) (add 8080 assembly version) |
||
Line 18: | Line 18: | ||
then state this rather than give a solution by other means). |
then state this rather than give a solution by other means). |
||
<br><br> |
<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}}== |
=={{header|ABAP}}== |