4 ms·
There are two approaches described - one a further extension of the other. The first approach still relies on a call stack (but not parameters or locals). Inste
by barrkel 12y ago
There are two approaches described - one a further extension of the other. The first approach still relies on a call stack (but not parameters or locals). Instead of calling a function like this:
f(x) =
// ...
f(x + 1)
It's called like this:
f =
x = x + 1
f()
x = x - 1
The return address from the function call references the code that undoes modification to global state (all locals and parameters have static storage when there is no recursion support), rather than relying on copies of parameters being made as in a modern language.
The second is an extension of the first, using goto and labels instead of function calls, but it only works if you don't need to distinguish between different call sites. If the recursive function only ever calls itself in one place, and the mutation it needs to make in order to "recurse" is always the same (so it can be consistently undone), then the call stack can be eliminated too.