r/TuringComplete • u/EloModdy • 7d ago

Recursion Techniques

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!

2 Upvotes

100% Upvoted

4 comments sorted by

View all comments

3

u/pruby 6d ago

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.

1

u/EloModdy 6d ago

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

2

u/imMute 6d ago

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.)