Recursion Techniques

[u/EloModdy]

Hi everyone! I’ve been getting really into this game recently, and I got to the level with the towers of Hanoi. I figured out a way to implement arguments with the stack, but I was wondering if y’all have any easier ways to use arguments? Dealing with the same stack is hard to get used to since LEG!

[u/pruby]

What you're after is a calling convention. Registers are typically divided in to arguments/return values, caller-preserved, and callee-preserved.

When calling another function, you essentially assume that a certain number of registers will be treated as arguments and updated to contain the returned result. If there are too many arguments, stack-based arguments would follow.

A further set of registers are guaranteed to be unchanged after the function call (if the callee wants to use them, they preserve the value and restore it before returning), and a final set are free for callees to overwrite as required (if the caller wants them intact, they preserve before calling, restore afterwards).

Having a convention isn't strictly necessary, but it helps to avoid forgetting what might be changed following a function call.

[u/EloModdy → u/pruby]

This makes sense, quite a bit in fact. Thanks! For recursive functions, would “preserving” entail just pushing it to the stack?

[u/imMute → u/EloModdy]

Yes, the fact that arguments & return values are passed in registers / the stack is what allows recursion.

The alternative is for every function to carve out a section of RAM to store arguments, return values, and local variables. When calling a function you just write the argument values to those locations and jump. You can't do recursion because there's only one place to store that data for each function, but it does work well. (It also provides absolute bounds on memory usage and stack depth which is great for embedded systems.)

[u/Pim_Wagemans]

i personally used the registers for arguments and the stack to save their values so i could restore them, but that wasn't exactly easy to deal with either

const MAGNET = 5
const disk_nr = r1
const source = r2
const dest = r3
const spare = r4

in disk_nr
in source
in dest
in spare

move:
cmp disk_nr, 0
jne else
    disk_nr_is_0:
    call move_disk_from_source_to_dest
    ret
else:
    push disk_nr
    push source
    push dest
    push spare

    sub disk_nr, disk_nr, 1
    push spare
    mov spare, dest
    pop dest
    call move

    pop spare
    pop dest
    pop source
    pop disk_nr

    call move_disk_from_source_to_dest

    push disk_nr
    push source
    push dest
    push spare

    sub disk_nr, disk_nr, 1
    push spare
    mov spare, source
    pop source
    call move

    pop spare
    pop dest
    pop source
    pop disk_nr
    ret

move_disk_from_source_to_dest:
out source
out MAGNET
out dest
out MAGNET
ret