Recursion transformation without stack frames code repetitions

Question

I have the following pseudo-code:

function X(data, limit, level = 0)
{
    result = [];
    foreach (Y(data, level) as entity) {
        if (level < limit) {
            result = result + X(entity, limit, level + 1);
        } else {
            //trivial recursion case:
            result = result + Z(entity);
        }
    }
    return result;
}

which I need to turn into a plain (e.g. without recursive calls). So far I'm out of ideas regarding how to do that elegantly. Following this answer I see that I must construct the entire stack frames which are basically the code repetitions (i.e. I will place same code again and again with different return addresses).

Or I tried stuff like these suggestions - where there is a phrase

1. Find a recursive call that’s not a tail call.
2. Identify what work is being done between that call and its return statement.

But I do not understand how can the "work" be identified in the case when it is happening from within internal loop.

So, my problem is that all examples above are providing cases when the "work can be easily identified" because there are no control instructions from within the function. I understand the concept behind recursion on a compilation level, but what I want to avoid is code repetition. So,

My question: how to approach transformation of the pseudo-code above which does not mean code repetitions for simulating stack frames?

Answer 1

It looks like an algorithm to descend a nested data structure (lists of lists) and flatten it out into a single list. It would have been good to have a simple description like that in the question.

To do that, you need to keep track of multiple indices / iterators / cursors, one at each level that you've descended through. A recursive implementation does that by using the call stack. A non-recursive implementation will need a manually-implemented stack data structure where you can push/pop stuff.

Since you don't have to save context (registers) and a return address on the call stack, just the actual iterator (e.g. array index), this can be a lot more space efficient.

When you're looping over the result of Y and need to call X or Z, push the current state onto the stack. Branch back to the beginning of the foreach, and call Y on the new entity. When you get to the end of a loop, pop the old state if there is any, and pick up in the middle of that loop.