递归函数循环和堆栈 [英] Recursive function to loop and stack

问题描述

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

It's well known all recursive functions can be written using just a single loop and a stack. Although this conversion can be criticized to be ugly or less readable, its main use is obviously to avoid smashing the heap.

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

There are natural ways to convert simple recursive functions into loops. For instance, take the simple tail-recursion elimination using an accumulator. So far, I have not seen yet a definitive answer for this question.

至少对我来说，有时将递归函数转换为提供堆栈的循环似乎是不可思议的事情.例如，考虑为

At least to me, sometimes it seems black magic to convert such recursive functions into loops provided a stack. For instance, think of writing a non-recursive version for

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

这个问题的重点是:

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

推荐答案

可行性(100％):

从此处，我们知道任何递归函数可以转换为迭代(进入循环)，但您需要自己使用堆栈来保持状态.

From here, we know that any recursive function can be converted to iterate (into a loop) but you need to use a stack yourself to keep the state.

---

操作方法(通常):

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

You can check out the article How to replace recursive functions using stack and while-loop to avoid the stack-overflow, which gives examples and steps (10 steps/rules) on how to convert recursive functions to stack and while-loop. See the following part for real example.

示例:

以下面的递归函数为例:

Take the following recursive function as an example:

// 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条规则/步骤(详细信息显示在注释中)后，您将获得:

After applying the 10 rules/steps introduced in the article (details shown in comments), you will get:

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

---

顺便说一句，上面的文章是CodeProject的竞赛<2012年7月最佳C++文章>的获奖者，所以应该是值得信赖的.:)

---

BTW, the above article is the Prize winner in Competition <Best C++ article of July 2012> of CodeProject, so it should be trust-able. :)

这篇关于递归函数循环和堆栈的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！