algorithm - 没有栈帧代码重复的递归转换

Question

我有以下伪代码:

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;
}

我需要把它变成一个普通的(例如，没有递归调用)。到目前为止，我不知道如何优雅地做到这一点。正在关注this answer 我看到我必须构建整个堆栈帧，它们基本上是代码重复(即我将一次又一次地放置相同的代码，但返回地址不同)。

或者我尝试了像 these suggestions 这样的东西- 哪里有一个短语

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.

但我不明白在内部循环发生的情况下如何识别“工作”。

所以，我的问题是上面的所有示例都提供了“可以轻松识别工作”的情况，因为函数内部没有控制指令。我理解编译级别递归背后的概念，但我想避免的是代码重复。所以，

我的问题:如何处理上述伪代码的转换，这并不意味着模拟堆栈帧的代码重复？

Answer 1

它看起来像是一种算法，用于降低嵌套数据结构(列表的列表)并将其展平为单个列表。如果问题中有这样的简单描述就好了。

要做到这一点，您需要跟踪多个索引/迭代器/游标，每个索引/迭代器/游标都位于您下降的每一层。递归实现通过使用调用堆栈来实现。非递归实现需要 manually-implemented stack data structure您可以在其中推送/弹出内容。

由于您不必在调用堆栈上保存上下文(寄存器)和返回地址，只需保存实际的迭代器(例如数组索引)，这样可以更加节省空间。

当您遍历 Y 的结果并需要调用 X 或 Z 时，将当前状态压入堆栈。分支回到 foreach 的开头，并在新实体上调用 Y。当你到达一个循环的末尾时，如果有旧状态，弹出旧状态，并在该循环的中间拾取。