循环和堆栈的递归函数

Question

众所周知，所有递归函数都可以仅使用单个循环和堆栈来编写。虽然这种转换可能会被批评为丑陋或可读性差，但它的主要用途显然是为了避免粉碎堆。

有很自然的方法可以将简单的递归函数转换为循环。例如，使用累加器进行简单的尾递归消除。到目前为止，我还没有看到这个问题的明确答案。

至少对我来说，有时将这种递归函数转换为提供堆栈的循环似乎是黑魔法。例如，考虑为

f(n) = n,                    if n <= 1
f(n) = f(n-1) + f(n-2) + 1,  if n > 1

这个问题的核心是：

• 是否有一种清晰的通用方法可以将递归函数转换为循环 + 堆栈？

Answer 1

可行性（100%）：

从这里，我们知道任何递归函数都可以转换为迭代（进入循环），但您需要自己使用堆栈来保持状态。

如何做到这一点（一般）：

您可以查看文章如何使用堆栈和 while 循环替换递归函数以避免堆栈溢出，其中提供了有关如何将递归函数转换为堆栈和 while 循环的示例和步骤（10 个步骤/规则）。请参阅以下部分的实际示例。

例子：

以下面的递归函数为例：

// Recursive Function "First rule" example
int SomeFunc(int n, int &retIdx)
{
    ...
        if(n>0)
        {
            int test = SomeFunc(n-1, retIdx);
            test--;
            ...
                return test;
        }
        ...
            return 0;
} 

应用本文中介绍的 10 个规则/步骤（详细信息见评论）后，您将获得：

// Conversion to Iterative Function
int SomeFuncLoop(int n, int &retIdx)
{
    // (First rule)
    struct SnapShotStruct {
        int n;        // - parameter input
        int test;     // - local variable that will be used 
        //     after returning from the function call
        // - retIdx can be ignored since it is a reference.
        int stage;    // - Since there is process needed to be done 
        //     after recursive call. (Sixth rule)
    };
    // (Second rule)
    int retVal = 0;  // initialize with default returning value
    // (Third rule)
    stack<SnapShotStruct> snapshotStack;
    // (Fourth rule)
    SnapShotStruct currentSnapshot;
    currentSnapshot.n= n;          // set the value as parameter value
    currentSnapshot.test=0;        // set the value as default value
    currentSnapshot.stage=0;       // set the value as initial stage
    snapshotStack.push(currentSnapshot);
    // (Fifth rule)
    while(!snapshotStack.empty())
    {
        currentSnapshot=snapshotStack.top();
        snapshotStack.pop();
        // (Sixth rule)
        switch( currentSnapshot.stage)
        {
        case 0:
            // (Seventh rule)
            if( currentSnapshot.n>0 )
            {
                // (Tenth rule)
                currentSnapshot.stage = 1;            // - current snapshot need to process after
                //     returning from the recursive call
                snapshotStack.push(currentSnapshot);  // - this MUST pushed into stack before 
                //     new snapshot!
                // Create a new snapshot for calling itself
                SnapShotStruct newSnapshot;
                newSnapshot.n= currentSnapshot.n-1;   // - give parameter as parameter given
                //     when calling itself
                //     ( SomeFunc(n-1, retIdx) )
                newSnapshot.test=0;                   // - set the value as initial value
                newSnapshot.stage=0;                  // - since it will start from the 
                //     beginning of the function, 
                //     give the initial stage
                snapshotStack.push(newSnapshot);
                continue;
            }
            ...
                // (Eighth rule)
                retVal = 0 ;

            // (Ninth rule)
            continue;
            break; 
        case 1: 
            // (Seventh rule)
            currentSnapshot.test = retVal;
            currentSnapshot.test--;
            ...
                // (Eighth rule)
                retVal = currentSnapshot.test;
            // (Ninth rule)
            continue;
            break;
        }
    }
    // (Second rule)
    return retVal;
} 

顺便说一句，上面的文章是Prize winner in Competition <Best C++ article of July 2012>CodeProject 的，所以应该是可信的。:)