optimization - 优化对数据结构的递归调用

Question

是否有一种算法可以将高度递归函数优化为对数据结构的迭代？例如，给定以下函数...

// template <typename T> class BSTNode is defined somewhere else
// It's a generic binary search tree.
template <typename T, typename R>
void in_order(BSTNode<T>* root, R (*routine)(T))
{
    if (root)
    {
        in_order(root->leftChild);
        routine(root->data);
        in_order(root->rightChild);
    }
}

...是否有可能将其优化成...

// template <typename> class Stack is defined somewhere else
// It's a generic LIFO array (aka stack).

template <typename T, typename R>
void in_order(BSTNode<T>* root, R (*routine)(T))
{
    if (!root) return;

    Stack<BSTNode*> stack;
    stack.push(NULL);

    line1:
    while (root->leftChild)
    {
        stack.push(root);
        root = root->leftChild;
    }

    line2:
    routine(root->data);
    if (root->rightChild)
    {
        root = root->rightChild;
        goto line1;
    }

    else if (root = stack.pop())
        goto line2;
}

(当然，区别在于，后者不是填充调用栈，而是填充堆中的另一个栈。)

---

编辑:我指的是可以由编译器执行的算法，因此我不必手动优化它。

Answer 1

是的，你可以做到这一点。

但是，除了可能会耗尽非常深的树的堆栈空间之外，这里没有“优化”。如果您需要提高速度，请考虑 threading your trees相反。