“System.StackOverflowException”类型的未经处理的异常在 mscorlib.dll 中发生

桃扇骨 2022-09-22 15:56 155阅读 0赞

摘要：我们经常会用到递归函数，但是如果递归深度太大时，往往导致栈溢出。而递归深度往往不太容易把握，所以比较安全一点的做法就是：**用循环代替递归。**文章最后的原文里面讲了如何用10步实现这个过程，相当精彩。本文翻译了这篇文章，并加了自己的一点注释和理解。

1.   简介
2.  模拟函数的目的
3.  递归和模拟函数的优缺点
4.  用栈和循环代替递归的10个步骤
5.  替代过程的几个简单例子
6.  更多的例子
7.  结论
8.  参考
9.  协议

1 简介

一般我们在进行排序(比如归并排序)或者树操作时会用到递归函数。但是如果递归深度达到一定程度以后，就会出现意想不到的结果比如堆栈溢出。虽然有很多有经验的开发者都知道了如何用循环函数或者栈加while循环来代替递归函数，以防止栈溢出，但我还是想分享一下这些方法，这或许会对初学者有很大的帮助。

2 模拟函数的目的

如果你正在使用递归函数，并且没有控制递归调用，而栈资源又比较有限，调用层次过深的时候就可能导致栈溢出/堆冲突。模拟函数的目的就是在堆中开辟区域来模拟栈的行为，这样你就能控制内存分配和流处理，从而避免栈溢出。如果能用循环函数来代替效果会更好，这是一个比较需要时间和经验来处理的事情，出于这些原因，这篇文章为初学者提供了一个简单的参考，怎样使用循环函数来替代递归函数，以防止栈溢出？

3 递归函数和模拟函数的优缺点

递归函数：

优点：算法比较直观。可以参考文章后面的例子

缺点：可能导致栈溢出或者堆冲突

你可以试试执行下面两个函数(后面的一个例子)，IsEvenNumber(递归实现)和IsEvenNumber(模拟实现)，他们在头文件"MutualRecursion.h"中声明。你可以将传入参数设定为10000，像下面这样：

#include "MutualRecursion.h" 
    
    bool result = IsEvenNumberLoop(10000); // 成功返回
    
    bool result2 = IsEvenNumber(10000);     // 会发生堆栈溢出

有些人可能会问：如果我增加栈的容量不就可以避免栈溢出吗？好吧，这只是暂时的解决问题的办法，如果调用层次越来越深，很有可能会再次发生溢出。

模拟函数：

优点：能避免栈溢出或者堆冲突错误，能对过程和内存进行更好的控制

缺点：算法不是太直观，代码难以维护

4 用栈和循环代替递归的10个步骤

第一步

1 定义一个新的结构体Snapshot，用于保存递归结构中的一些数据和状态信息

2 在Snapshot内部需要包含的变量有以下几种：

A 一般当递归函数调用自身时，函数参数会发生变化。所以你需要包含变化的参数，引用除外。比如下面的例子中，参数n应该包含在结构体中，而retVal不需要。

void SomeFunc(int n, int &retVal);

B 阶段性变量"stage"(通常是一个用来转换到另一个处理分支的整形变量)，详见第六条规则

C 函数调用返回以后还需要继续使用的局部变量(一般在二分递归和嵌套递归中很常见)

代码：

![ExpandedBlockStart.gif][]

![复制代码][copycode.gif]

1 // Recursive Function "First rule" example
     2 int SomeFunc(int n, int &retIdx)
     3 {
     4    ...
     5    if(n>0)
     6    {
     7       int test = SomeFunc(n-1, retIdx);
     8       test--;
     9       ...
    10       return test;
    11    }
    12    ...
    13    return 0;
    14 }
    15 
    16 
    17 // Conversion to Iterative Function
    18 int SomeFuncLoop(int n, int &retIdx)
    19 {
    20     // (First rule)
    21     struct SnapShotStruct {
    22        int n;        // - parameter input
    23        int test;     // - local variable that will be used 
    24                      //     after returning from the function call
    25                      // - retIdx can be ignored since it is a reference.
    26        int stage;    // - Since there is process needed to be done 
    27                      //     after recursive call. (Sixth rule)
    28     };
    29     ...
    30 }

![复制代码][copycode.gif]

第二步

1 在函数的开头创建一个局部变量，这个值扮演了递归函数的返回函数角色。它相当于为每次递归调用保存一个临时值，因为C++函数只能有一种返回类型，如果递归函数的返回类型是void，你可以忽略这个局部变量。如果有缺省的返回值，就应该用缺省值初始化这个局部变量。

![ExpandedBlockStart.gif][]

![复制代码][copycode.gif]

1 // Recursive Function "Second rule" example
     2 int SomeFunc(int n, int &retIdx)
     3 {
     4    ...
     5    if(n>0)
     6    {
     7       int test = SomeFunc(n-1, retIdx);
     8       test--;
     9       ...
    10       return test;
    11    }
    12    ...
    13    return 0;
    14 }
    15 
    16 // Conversion to Iterative Function
    17 int SomeFuncLoop(int n, int &retIdx)
    18 {
    19      // (First rule)
    20     struct SnapShotStruct {
    21        int n;        // - parameter input
    22        int test;     // - local variable that will be used 
    23                      //     after returning from the function call
    24                      // - retIdx can be ignored since it is a reference.
    25        int stage;    // - Since there is process needed to be done 
    26                      //     after recursive call. (Sixth rule)
    27     };
    28 
    29     // (Second rule)
    30     int retVal = 0;  // initialize with default returning value
    31 
    32     ...
    33     // (Second rule)
    34     return retVal;
    35 }

![复制代码][copycode.gif]

第三步

创建一个栈用于保存“Snapshot”结构体类型变量

![ExpandedBlockStart.gif][]

![复制代码][copycode.gif]

1 // Recursive Function "Third rule" example
     2 
     3 // Conversion to Iterative Function
     4 int SomeFuncLoop(int n, int &retIdx)
     5 {
     6      // (First rule)
     7     struct SnapShotStruct {
     8        int n;        // - parameter input
     9        int test;     // - local variable that will be used 
    10                      //     after returning from the function call
    11                      // - retIdx can be ignored since it is a reference.
    12        int stage;    // - Since there is process needed to be done 
    13                      //     after recursive call. (Sixth rule)
    14     };
    15 
    16     // (Second rule)
    17     int retVal = 0;  // initialize with default returning value
    18 
    19     // (Third rule)
    20     stack<SnapShotStruct> snapshotStack;
    21     ...
    22     // (Second rule)
    23     return retVal;
    24 }

![复制代码][copycode.gif]

第四步

创建一个新的”Snapshot”实例，然后将其中的参数等初始化，并将“Snapshot”实例压入栈

![ExpandedBlockStart.gif][]

![复制代码][copycode.gif]

1 // Recursive Function "Fourth rule" example
     2 
     3 // Conversion to Iterative Function
     4 int SomeFuncLoop(int n, int &retIdx)
     5 {
     6      // (First rule)
     7     struct SnapShotStruct {
     8        int n;        // - parameter input
     9        int test;     // - local variable that will be used 
    10                      //     after returning from the function call
    11                      // - retIdx can be ignored since it is a reference.
    12        int stage;    // - Since there is process needed to be done 
    13                      //     after recursive call. (Sixth rule)
    14     };
    15 
    16     // (Second rule)
    17     int retVal = 0;  // initialize with default returning value
    18 
    19     // (Third rule)
    20     stack<SnapShotStruct> snapshotStack;
    21 
    22     // (Fourth rule)
    23     SnapShotStruct currentSnapshot;
    24     currentSnapshot.n= n;          // set the value as parameter value
    25     currentSnapshot.test=0;        // set the value as default value
    26     currentSnapshot.stage=0;       // set the value as initial stage
    27 
    28     snapshotStack.push(currentSnapshot);
    29 
    30     ...
    31     // (Second rule)
    32     return retVal;
    33 }

![复制代码][copycode.gif]

第五步

写一个while循环，使其不断执行直到栈为空。在while循环的每一次迭代过程中，弹出”Snapshot“对象。

![ExpandedBlockStart.gif][]

![复制代码][copycode.gif]

1 // Recursive Function "Fifth rule" example
     2 
     3 // Conversion to Iterative Function
     4 int SomeFuncLoop(int n, int &retIdx)
     5 {
     6      // (First rule)
     7     struct SnapShotStruct {
     8        int n;        // - parameter input
     9        int test;     // - local variable that will be used 
    10                      //     after returning from the function call
    11                      // - retIdx can be ignored since it is a reference.
    12        int stage;    // - Since there is process needed to be done 
    13                      //     after recursive call. (Sixth rule)
    14     };
    15     // (Second rule)
    16     int retVal = 0;  // initialize with default returning value
    17     // (Third rule)
    18     stack<SnapShotStruct> snapshotStack;
    19     // (Fourth rule)
    20     SnapShotStruct currentSnapshot;
    21     currentSnapshot.n= n;          // set the value as parameter value
    22     currentSnapshot.test=0;        // set the value as default value
    23     currentSnapshot.stage=0;       // set the value as initial stage
    24     snapshotStack.push(currentSnapshot);
    25     // (Fifth rule)
    26     while(!snapshotStack.empty())
    27     {
    28        currentSnapshot=snapshotStack.top();
    29        snapshotStack.pop();
    30        ...
    31     }
    32     // (Second rule)
    33     return retVal;
    34 }

![复制代码][copycode.gif]

第六步

1.  将当前阶段一分为二(针对当前只有单一递归调用的情形)。第一个阶段代表了下一次递归调用之前的情况，第二阶段代表了下一次递归调用完成并返回之后的情况(返回值已经被保存，并在此之前被累加)。
2.  如果当前阶段有两次递归调用，就必须分为3个阶段。阶段1：第一次调用返回之前，阶段2：阶段1执行的调用过程。阶段3：第二次调用返回之前。
3.  如果当前阶段有三次递归调用，就必须至少分为4个阶段。
4.  依次类推。

![ExpandedBlockStart.gif][]

![复制代码][copycode.gif]

1 // Recursive Function "Sixth rule" example
     2 int SomeFunc(int n, int &retIdx)
     3 {
     4    ...
     5    if(n>0)
     6    {
     7       int test = SomeFunc(n-1, retIdx);
     8       test--;
     9       ...
    10       return test;
    11    }
    12    ...
    13    return 0;
    14 }
    15 
    16 // Conversion to Iterative Function
    17 int SomeFuncLoop(int n, int &retIdx)
    18 {
    19      // (First rule)
    20     struct SnapShotStruct {
    21        int n;        // - parameter input
    22        int test;     // - local variable that will be used 
    23                      //     after returning from the function call
    24                      // - retIdx can be ignored since it is a reference.
    25        int stage;    // - Since there is process needed to be done 
    26                      //     after recursive call. (Sixth rule)
    27     };
    28     // (Second rule)
    29     int retVal = 0;  // initialize with default returning value
    30     // (Third rule)
    31     stack<SnapShotStruct> snapshotStack;
    32     // (Fourth rule)
    33     SnapShotStruct currentSnapshot;
    34     currentSnapshot.n= n;          // set the value as parameter value
    35     currentSnapshot.test=0;        // set the value as default value
    36     currentSnapshot.stage=0;       // set the value as initial stage
    37     snapshotStack.push(currentSnapshot);
    38     // (Fifth rule)
    39     while(!snapshotStack.empty())
    40     {
    41        currentSnapshot=snapshotStack.top();
    42        snapshotStack.pop();
    43        // (Sixth rule)
    44        switch( currentSnapshot.stage)
    45        {
    46        case 0:
    47           ...      // before ( SomeFunc(n-1, retIdx); )
    48           break; 
    49        case 1: 
    50           ...      // after ( SomeFunc(n-1, retIdx); )
    51           break;
    52        }
    53     }
    54     // (Second rule)
    55     return retVal;
    56 }

![复制代码][copycode.gif]

第七步

根据阶段变量stage的值切换到相应的处理流程并处理相关过程。

![ExpandedBlockStart.gif][]

![复制代码][copycode.gif]

1 // Recursive Function "Seventh rule" example
     2 int SomeFunc(int n, int &retIdx)
     3 {
     4    ...
     5    if(n>0)
     6    {
     7       int test = SomeFunc(n-1, retIdx);
     8       test--;
     9       ...
    10       return test;
    11    }
    12    ...
    13    return 0;
    14 }
    15 
    16 // Conversion to Iterative Function
    17 int SomeFuncLoop(int n, int &retIdx)
    18 {
    19      // (First rule)
    20     struct SnapShotStruct {
    21        int n;        // - parameter input
    22        int test;     // - local variable that will be used 
    23                      //     after returning from the function call
    24                      // - retIdx can be ignored since it is a reference.
    25        int stage;    // - Since there is process needed to be done 
    26                      //     after recursive call. (Sixth rule)
    27     };
    28 
    29     // (Second rule)
    30     int retVal = 0;  // initialize with default returning value
    31 
    32     // (Third rule)
    33     stack<SnapShotStruct> snapshotStack;
    34 
    35     // (Fourth rule)
    36     SnapShotStruct currentSnapshot;
    37     currentSnapshot.n= n;          // set the value as parameter value
    38     currentSnapshot.test=0;        // set the value as default value
    39     currentSnapshot.stage=0;       // set the value as initial stage
    40 
    41     snapshotStack.push(currentSnapshot);
    42 
    43     // (Fifth rule)
    44     while(!snapshotStack.empty())
    45     {
    46        currentSnapshot=snapshotStack.top();
    47        snapshotStack.pop();
    48 
    49        // (Sixth rule)
    50        switch( currentSnapshot.stage)
    51        {
    52        case 0:
    53           // (Seventh rule)
    54           if( currentSnapshot.n>0 )
    55           {
    56              ...
    57           }
    58           ...
    59           break; 
    60        case 1: 
    61           // (Seventh rule)
    62           currentSnapshot.test = retVal;
    63           currentSnapshot.test--;
    64           ...
    65           break;
    66        }
    67     }
    68     // (Second rule)
    69     return retVal;
    70 }

![复制代码][copycode.gif]

第八步

如果递归有返回值，将这个值保存下来放在临时变量里面，比如retVal。当循环结束时，这个临时变量的值就是整个递归处理的结果。

![ExpandedBlockStart.gif][]

![复制代码][copycode.gif]

1 // Recursive Function "Eighth rule" example
     2 int SomeFunc(int n, int &retIdx)
     3 {
     4    ...
     5    if(n>0)
     6    {
     7       int test = SomeFunc(n-1, retIdx);
     8       test--;
     9       ...
    10       return test;
    11    }
    12    ...
    13    return 0;
    14 }
    15 
    16 // Conversion to Iterative Function
    17 int SomeFuncLoop(int n, int &retIdx)
    18 {
    19      // (First rule)
    20     struct SnapShotStruct {
    21        int n;        // - parameter input
    22        int test;     // - local variable that will be used 
    23                      //     after returning from the function call
    24                      // - retIdx can be ignored since it is a reference.
    25        int stage;    // - Since there is process needed to be done 
    26                      //     after recursive call. (Sixth rule)
    27     };
    28     // (Second rule)
    29     int retVal = 0;  // initialize with default returning value
    30     // (Third rule)
    31     stack<SnapShotStruct> snapshotStack;
    32     // (Fourth rule)
    33     SnapShotStruct currentSnapshot;
    34     currentSnapshot.n= n;          // set the value as parameter value
    35     currentSnapshot.test=0;        // set the value as default value
    36     currentSnapshot.stage=0;       // set the value as initial stage
    37     snapshotStack.push(currentSnapshot);
    38     // (Fifth rule)
    39     while(!snapshotStack.empty())
    40     {
    41        currentSnapshot=snapshotStack.top();
    42        snapshotStack.pop();
    43        // (Sixth rule)
    44        switch( currentSnapshot.stage)
    45        {
    46        case 0:
    47           // (Seventh rule)
    48           if( currentSnapshot.n>0 )
    49           {
    50              ...
    51           }
    52           ...
    53           // (Eighth rule)
    54           retVal = 0 ;
    55           ...
    56           break; 
    57        case 1: 
    58           // (Seventh rule)
    59           currentSnapshot.test = retVal;
    60           currentSnapshot.test--;
    61           ...
    62           // (Eighth rule)
    63           retVal = currentSnapshot.test;
    64           ...
    65           break;
    66        }
    67     }
    68     // (Second rule)
    69     return retVal;
    70 }

![复制代码][copycode.gif]

第九步

如果递归函数有“return”关键字，你应该在while循环里面用“continue”代替。如果return了一个返回值，你应该在循环里面保存下来(步骤8)，然后return。大部分情况下，步骤九是可选的，但是它能帮助你避免逻辑错误。

![ExpandedBlockStart.gif][]

![复制代码][copycode.gif]

1 // Recursive Function "Ninth rule" example
     2 int SomeFunc(int n, int &retIdx)
     3 {
     4    ...
     5    if(n>0)
     6    {
     7       int test = SomeFunc(n-1, retIdx);
     8       test--;
     9       ...
    10       return test;
    11    }
    12    ...
    13    return 0;
    14 }
    15 
    16 // Conversion to Iterative Function
    17 int SomeFuncLoop(int n, int &retIdx)
    18 {
    19      // (First rule)
    20     struct SnapShotStruct {
    21        int n;        // - parameter input
    22        int test;     // - local variable that will be used 
    23                      //     after returning from the function call
    24                      // - retIdx can be ignored since it is a reference.
    25        int stage;    // - Since there is process needed to be done 
    26                      //     after recursive call. (Sixth rule)
    27     };
    28     // (Second rule)
    29     int retVal = 0;  // initialize with default returning value
    30     // (Third rule)
    31     stack<SnapShotStruct> snapshotStack;
    32     // (Fourth rule)
    33     SnapShotStruct currentSnapshot;
    34     currentSnapshot.n= n;          // set the value as parameter value
    35     currentSnapshot.test=0;        // set the value as default value
    36     currentSnapshot.stage=0;       // set the value as initial stage
    37     snapshotStack.push(currentSnapshot);
    38     // (Fifth rule)
    39     while(!snapshotStack.empty())
    40     {
    41        currentSnapshot=snapshotStack.top();
    42        snapshotStack.pop();
    43        // (Sixth rule)
    44        switch( currentSnapshot.stage)
    45        {
    46        case 0:
    47           // (Seventh rule)
    48           if( currentSnapshot.n>0 )
    49           {
    50              ...
    51           }
    52           ...
    53           // (Eighth rule)
    54           retVal = 0 ;
    55           
    56           // (Ninth rule)
    57           continue;
    58           break; 
    59        case 1: 
    60           // (Seventh rule)
    61           currentSnapshot.test = retVal;
    62           currentSnapshot.test--;
    63           ...
    64           // (Eighth rule)
    65           retVal = currentSnapshot.test;
    66 
    67           // (Ninth rule)
    68           continue;
    69           break;
    70        }
    71     }
    72     // (Second rule)
    73     return retVal;
    74 }

![复制代码][copycode.gif]

第十步

为了模拟下一次递归函数的调用，你必须在当前循环函数里面再生成一个新的“Snapshot”结构体作为下一次调用的快照，初始化其参数以后压入栈，并“continue”。如果当前调用在执行完成后还有一些事情需要处理，那么更改它的阶段状态“stage”到相应的过程，并在new Snapshot压入之前，把本次的“Snapshot”压入。

![ExpandedBlockStart.gif][]

![复制代码][copycode.gif]

1 // Recursive Function "Tenth rule" example
     2 int SomeFunc(int n, int &retIdx)
     3 {
     4    ...
     5    if(n>0)
     6    {
     7       int test = SomeFunc(n-1, retIdx);
     8       test--;
     9       ...
    10       return test;
    11    }
    12    ...
    13    return 0;
    14 }
    15 
    16 // Conversion to Iterative Function
    17 int SomeFuncLoop(int n, int &retIdx)
    18 {
    19      // (First rule)
    20     struct SnapShotStruct {
    21        int n;        // - parameter input
    22        int test;     // - local variable that will be used 
    23                      //     after returning from the function call
    24                      // - retIdx can be ignored since it is a reference.
    25        int stage;    // - Since there is process needed to be done 
    26                      //     after recursive call. (Sixth rule)
    27     };
    28     // (Second rule)
    29     int retVal = 0;  // initialize with default returning value
    30     // (Third rule)
    31     stack<SnapShotStruct> snapshotStack;
    32     // (Fourth rule)
    33     SnapShotStruct currentSnapshot;
    34     currentSnapshot.n= n;          // set the value as parameter value
    35     currentSnapshot.test=0;        // set the value as default value
    36     currentSnapshot.stage=0;       // set the value as initial stage
    37     snapshotStack.push(currentSnapshot);
    38     // (Fifth rule)
    39     while(!snapshotStack.empty())
    40     {
    41        currentSnapshot=snapshotStack.top();
    42        snapshotStack.pop();
    43        // (Sixth rule)
    44        switch( currentSnapshot.stage)
    45        {
    46        case 0:
    47           // (Seventh rule)
    48           if( currentSnapshot.n>0 )
    49           {
    50              // (Tenth rule)
    51              currentSnapshot.stage = 1;            // - current snapshot need to process after
    52                                                    //     returning from the recursive call
    53              snapshotStack.push(currentSnapshot);  // - this MUST pushed into stack before 
    54                                                    //     new snapshot!
    55              // Create a new snapshot for calling itself
    56              SnapShotStruct newSnapshot;
    57              newSnapshot.n= currentSnapshot.n-1;   // - give parameter as parameter given
    58                                                    //     when calling itself
    59                                                    //     ( SomeFunc(n-1, retIdx) )
    60              newSnapshot.test=0;                   // - set the value as initial value
    61              newSnapshot.stage=0;                  // - since it will start from the 
    62                                                    //     beginning of the function, 
    63                                                    //     give the initial stage
    64              snapshotStack.push(newSnapshot);
    65              continue;
    66           }
    67           ...
    68           // (Eighth rule)
    69           retVal = 0 ;
    70           
    71           // (Ninth rule)
    72           continue;
    73           break; 
    74        case 1: 
    75           // (Seventh rule)
    76           currentSnapshot.test = retVal;
    77           currentSnapshot.test--;
    78           ...
    79           // (Eighth rule)
    80           retVal = currentSnapshot.test;
    81           // (Ninth rule)
    82           continue;
    83           break;
    84        }
    85     }
    86     // (Second rule)
    87     return retVal;
    88 }

![复制代码][copycode.gif]

5 替代过程的几个简单例子

以下几个例子均在vs2008环境下开发，主要包含了：

（1）线性递归

![ExpandedBlockStart.gif][]

![复制代码][copycode.gif]

1 #ifndef __LINEAR_RECURSION_H__
      2 #define __LINEAR_RECURSION_H__
      3 
      4 #include <stack>
      5 using namespace std;
      6 
      7 /**
      8 * \brief 求n的阶乘
      9 * \para 
     10 * \return 
     11 * \note result = n! 递归实现
     12 */
     13 int Fact(long n)
     14 {
     15     if(0>n)
     16         return -1;
     17     if(0 == n)
     18         return 1;
     19     else
     20     {
     21         return ( n* Fact(n-1));
     22     }
     23 } 
     24 
     25 /**
     26 * \brief 求n的阶乘
     27 * \para 
     28 * \return 
     29 * \note result = n! 循环实现
     30 */
     31 int FactLoop(long n)
     32 {
     33     // (步骤1)
     34     struct SnapShotStruct // 快照结构体局部声明 
     35     {
     36         long inputN;      // 会改变的参数
     37                           // 没有局部变量
     38         int stage;        // 阶段变量用于快照跟踪
     39     } ;
     40 
     41     // (步骤2)
     42     int returnVal;        // 用于保存当前调用返回值  
     43 
     44     // (步骤3)
     45     stack<SnapShotStruct> snapshotStack;
     46 
     47     // (步骤4)
     48     SnapShotStruct currentSnapshot;
     49     currentSnapshot.inputN=n;
     50     currentSnapshot.stage=0; // 阶段变量初始化
     51 
     52     snapshotStack.push(currentSnapshot);  
     53 
     54     // (步骤5)
     55     while(!snapshotStack.empty())  
     56     {     
     57         currentSnapshot=snapshotStack.top();         
     58         snapshotStack.pop();       
     59 
     60         // (步骤6)
     61         switch(currentSnapshot.stage)
     62         {
     63             // (步骤7)
     64         case 0:
     65             if(0>currentSnapshot.inputN)
     66             {
     67                 // (步骤8 & 步骤9)
     68                 returnVal = -1;
     69                 continue;
     70             }
     71             if(0 == currentSnapshot.inputN)
     72             {
     73                 // (步骤8 & 步骤9)
     74                 returnVal = 1;     
     75                 continue;
     76             }
     77             else
     78             {
     79                 // (步骤10)
     80 
     81                 // 返回 ( n* Fact(n-1)); 分为2步： 
     82                 // (第一步调用自身，第二步用返回值乘以当前n值)
     83                 // 这里我们拍下快照.
     84                 currentSnapshot.stage=1; // 当前的快照表示正在被处理，并等待自身调用结果返回，所以赋值为1 
     85 
     86                 snapshotStack.push(currentSnapshot);
     87 
     88                 // 创建一个新的快照，用于调用自身
     89                 SnapShotStruct newSnapshot;
     90                 newSnapshot.inputN= currentSnapshot.inputN -1 ; // 初始化参数 
     91                                                                  
     92                 newSnapshot.stage = 0 ;                         // 从头开始执行自身，所以赋值stage==0 
     93                                                                 
     94                 snapshotStack.push(newSnapshot);
     95                 continue;
     96 
     97             }
     98             break;
     99             // (步骤7)
    100         case 1:
    101 
    102             // (步骤8)
    103 
    104             returnVal = currentSnapshot.inputN * returnVal;
    105 
    106             // (步骤9)
    107             continue;
    108             break;
    109         }
    110     }
    111     
    112     // (步骤2)
    113     return returnVal;
    114 }   
    115 #endif //__LINEAR_RECURSION_H__

![复制代码][copycode.gif]

（2）二分递归

![ExpandedBlockStart.gif][]

![复制代码][copycode.gif]

1 #ifndef __BINARY_RECURSION_H__
      2 #define __BINARY_RECURSION_H__
      3 
      4 #include <stack>
      5 using namespace std;
      6 
      7 /**
      8 * \function FibNum
      9 * \brief 求斐波纳契数列
     10 * \para 
     11 * \return 
     12 * \note 递归实现
     13 */
     14 int FibNum(int n)
     15 {
     16     if (n < 1)
     17         return -1;
     18     if (1 == n || 2 == n)
     19         return 1;
     20 
     21     // 这里可以看成是
     22     //int addVal = FibNum( n - 1);
     23     // addVal += FibNum(n - 2);
     24     // return addVal;
     25     return FibNum(n - 1) + FibNum(n - 2);                             
     26 } 
     27 /**
     28 * \function FibNumLoop
     29 * \brief 求斐波纳契数列
     30 * \para 
     31 * \return 
     32 * \note 循环实现
     33 */
     34 int FibNumLoop(int n)
     35 {
     36     // (步骤1)
     37     struct SnapShotStruct // 快照结构体局部声明 
     38     {
     39         int inputN;       // 会改变的参数
     40         int addVal;       // 局部变量
     41         int stage;        // 阶段变量用于快照跟踪
     42 
     43     };
     44 
     45     // (步骤2)
     46     int returnVal;        // 用于保存当前调用返回值
     47 
     48     // (步骤3)
     49     stack<SnapShotStruct> snapshotStack;
     50 
     51     // (步骤4)
     52     SnapShotStruct currentSnapshot;
     53     currentSnapshot.inputN=n;
     54     currentSnapshot.stage=0; // 阶段变量初始化
     55 
     56     snapshotStack.push(currentSnapshot);
     57 
     58     // (步骤5)
     59     while(!snapshotStack.empty())
     60     {
     61         currentSnapshot=snapshotStack.top();
     62         snapshotStack.pop();
     63 
     64         // (步骤6)
     65         switch(currentSnapshot.stage)
     66         {
     67             // (步骤7)
     68         case 0:
     69             if(currentSnapshot.inputN<1)
     70             {
     71                 // (步骤8 & 步骤9)
     72                 returnVal = -1;
     73                 continue;
     74             }
     75             if(currentSnapshot.inputN == 1 || currentSnapshot.inputN == 2 )
     76             {
     77                 // (步骤8 & 步骤9)
     78                 returnVal = 1;
     79                 continue;
     80             }
     81             else
     82             {
     83                 // (步骤10)
     84 
     85                 // 返回 ( FibNum(n - 1) + FibNum(n - 2)); 相当于两步
     86                 // (第一次调用参数是 n-1, 第二次调用参数 n-2)
     87                 // 这里我们拍下快照，分成2个阶段
     88                 currentSnapshot.stage=1;                        // 当前的快照表示正在被处理，并等待自身调用结果返回，所以赋值为1 
     89 
     90                 snapshotStack.push(currentSnapshot);
     91 
     92                 // 创建一个新的快照，用于调用自身
     93                 SnapShotStruct newSnapshot;
     94                 newSnapshot.inputN= currentSnapshot.inputN -1 ; //初始化参数 FibNum(n - 1)
     95 
     96                 newSnapshot.stage = 0 ;                         
     97                 snapshotStack.push(newSnapshot);
     98                 continue;
     99 
    100             }
    101             break;
    102             // (步骤7)
    103         case 1:
    104 
    105             // (步骤10)
    106 
    107             currentSnapshot.addVal = returnVal;
    108             currentSnapshot.stage=2;                         // 当前的快照正在被处理，并等待的自身调用结果，所以阶段变量变成2
    109 
    110             snapshotStack.push(currentSnapshot);
    111 
    112             // 创建一个新的快照，用于调用自身
    113             SnapShotStruct newSnapshot;
    114             newSnapshot.inputN= currentSnapshot.inputN - 2 ; // 初始化参数 FibNum(n - 2)
    115             newSnapshot.stage = 0 ;                          // 从头开始执行，阶段变量赋值为0 
    116                                                              
    117             snapshotStack.push(newSnapshot);
    118             continue;
    119             break;
    120         case 2:
    121             // (步骤8)
    122             returnVal = currentSnapshot.addVal + returnVal;  // actual addition of ( FibNum(n - 1) + FibNum(n - 2) )
    123 
    124             // (步骤9)
    125             continue;
    126             break;
    127         }
    128     }  
    129 
    130     // (步骤2)
    131     return returnVal;
    132 }
    133   
    134 
    135 #endif //__BINARY_RECURSION_H__

![复制代码][copycode.gif]

（3）尾递归

![ExpandedBlockStart.gif][]

![复制代码][copycode.gif]

1 #ifndef __TAIL_RECURSION_H__
     2 #define __TAIL_RECURSION_H__
     3 
     4 #include <stack>
     5 using namespace std;
     6 
     7 /**
     8 * \function FibNum2
     9 * \brief 2阶裴波那契序列
    10 * \para
    11 * \return
    12 * \note 递归实现  f0 = x, f1 = y, fn=fn-1+fn-2,   n=k,k+1,...
    13 */ 
    14 int FibNum2(int n, int x, int y)
    15 {   
    16     if (1 == n)    
    17     {
    18         return y;
    19     }
    20     else    
    21     {
    22         return FibNum2(n-1, y, x+y);
    23     }
    24 }
    25 /**
    26 * \function FibNum2Loop
    27 * \brief 2阶裴波那契序列
    28 * \para
    29 * \return
    30 * \note 循环实现 在尾递归中, 递归调用后除了返回没有任何其它的操作, 所以在变为循环时，不需要stage变量
    31 */ 
    32 int FibNum2Loop(int n, int x, int y)
    33 {
    34     // (步骤1)
    35     struct SnapShotStruct 
    36     {
    37         int inputN;    // 会改变的参数
    38         int inputX;    // 会改变的参数
    39         int inputY;    // 会改变的参数
    40                        // 没有局部变量
    41     };
    42 
    43     // (步骤2)
    44     int returnVal;
    45 
    46     // (步骤3)
    47     stack<SnapShotStruct> snapshotStack;
    48 
    49     // (步骤4)
    50     SnapShotStruct currentSnapshot;
    51     currentSnapshot.inputN = n;
    52     currentSnapshot.inputX = x;
    53     currentSnapshot.inputY = y;
    54 
    55     snapshotStack.push(currentSnapshot);
    56 
    57     // (步骤5)
    58     while(!snapshotStack.empty())
    59     {
    60         currentSnapshot=snapshotStack.top();
    61         snapshotStack.pop();
    62 
    63         if(currentSnapshot.inputN == 1)
    64         {
    65             // (步骤8 & 步骤9)
    66             returnVal = currentSnapshot.inputY;
    67             continue;
    68         }
    69         else
    70         {
    71             // (步骤10)
    72 
    73             // 创建新快照
    74             SnapShotStruct newSnapshot;
    75             newSnapshot.inputN= currentSnapshot.inputN -1 ; // 初始化，调用( FibNum(n-1, y, x+y) )
    76             newSnapshot.inputX= currentSnapshot.inputY;
    77             newSnapshot.inputY= currentSnapshot.inputX + currentSnapshot.inputY;
    78             snapshotStack.push(newSnapshot);
    79             continue;
    80         }
    81     }
    82     // (步骤2)
    83     return returnVal;
    84 } 
    85 
    86 #endif //__TAIL_RECURSION_H__

![复制代码][copycode.gif]

（4）互递归

![ExpandedBlockStart.gif][]

![复制代码][copycode.gif]

1 #ifndef __MUTUAL_RECURSION_H__
      2 #define __MUTUAL_RECURSION_H__
      3 #include <stack>
      4 using namespace std;
      5 
      6 bool IsEvenNumber(int n);//判断是否是偶数
      7 bool IsOddNumber(int n);//判断是否是奇数
      8 bool isOddOrEven(int n, int stage);//判断是否是奇数或偶数
      9 
     10 /****************************************************/
     11 //互相调用的递归实现
     12 bool IsOddNumber(int n)
     13 {
     14     // 终止条件
     15     if (0 == n)
     16         return false;
     17     else
     18         // 互相调用函数的递归调用
     19         return IsEvenNumber(n - 1);
     20 }
     21 
     22 bool IsEvenNumber(int n)
     23 {
     24     // 终止条件
     25     if (0 == n)
     26         return true;
     27     else
     28         // 互相调用函数的递归调用
     29         return IsOddNumber(n - 1);
     30 } 
     31 
     32 
     33 /*************************************************/
     34 //互相调用的循环实现
     35 bool IsOddNumberLoop(int n)
     36 {
     37     return isOddOrEven(n , 0);
     38 }
     39 
     40 bool IsEvenNumberLoop(int n)
     41 {
     42     return isOddOrEven(n , 1);
     43 }
     44 
     45 bool isOddOrEven(int n, int stage)
     46 {
     47     // (步骤1)
     48     struct SnapShotStruct
     49     {
     50         int inputN;       // 会改变的参数
     51         int stage;
     52                           // 没有局部变量
     53     };
     54 
     55     // (步骤2)
     56     bool returnVal;       
     57 
     58     // (步骤3)
     59     stack<SnapShotStruct> snapshotStack;
     60 
     61     // (步骤4)
     62     SnapShotStruct currentSnapshot;
     63     currentSnapshot.inputN = n;
     64     currentSnapshot.stage = stage;
     65 
     66     snapshotStack.push(currentSnapshot);
     67 
     68     // (步骤5)
     69     while(!snapshotStack.empty())
     70     {
     71         currentSnapshot=snapshotStack.top();
     72         snapshotStack.pop();
     73 
     74         // (步骤6)
     75         switch(currentSnapshot.stage)
     76         {
     77             // (步骤7)
     78             // bool IsOddNumber(int n)
     79         case 0:
     80             // 终止条件
     81             if (0 == currentSnapshot.inputN)
     82             {
     83                 // (步骤8 & 步骤9)
     84                 returnVal = false;
     85                 continue;
     86             }
     87             else
     88             {
     89                 // (步骤10)
     90 
     91                 // 模拟互调用的递归调用
     92 
     93                 // 创建新的快照
     94                 SnapShotStruct newSnapshot;
     95                 newSnapshot.inputN= currentSnapshot.inputN - 1; // 初始化参数 
     96                 // 调用 ( IsEvenNumber(n - 1) )
     97                 newSnapshot.stage= 1;
     98                 snapshotStack.push(newSnapshot);
     99                 continue;
    100             }
    101 
    102             break;
    103             // (步骤7)
    104             // bool IsEvenNumber(int n)
    105         case 1:
    106             // 终止条件
    107             if (0 == currentSnapshot.inputN)
    108             {
    109                 // (步骤8 & 步骤9)
    110                 returnVal = true;
    111                 continue;
    112             }
    113             else
    114             {
    115                 // (步骤10)
    116 
    117                 // 模拟互调用的递归调用
    118 
    119                 // 创建新的快照
    120                 SnapShotStruct newSnapshot;
    121                 newSnapshot.inputN= currentSnapshot.inputN - 1; // 
    122                 // calling itself ( IsEvenNumber(n - 1) )
    123                 newSnapshot.stage= 0;
    124                 snapshotStack.push(newSnapshot);
    125                 continue;
    126             }
    127             break;
    128         }
    129 
    130     }
    131     // (步骤2)
    132     return returnVal;
    133 }  
    134 
    135 #endif //__MUTUAL_RECURSION_H__

![复制代码][copycode.gif]

（5）嵌套递归

![ExpandedBlockStart.gif][]

![复制代码][copycode.gif]

1 #ifndef __NESTED_RECURSION_H__
      2 #define __NESTED_RECURSION_H__
      3 #include <stack>
      4 using namespace std;
      5 
      6 int Ackermann(int x, int y)
      7 {
      8     // 终止条件
      9     if (0 == x)
     10     {
     11         return y + 1;
     12     }   
     13     // 错误处理条件
     14     if (x < 0  ||  y < 0)
     15     {
     16         return -1;
     17     }  
     18     // 线性方法的递归调用 
     19     else if (x > 0 && 0 == y) 
     20     {
     21         return Ackermann(x-1, 1);
     22     }
     23     // 嵌套方法的递归调用
     24     else
     25     {
     26         //可以看成是：
     27         // int midVal = Ackermann(x, y-1);
     28         // return Ackermann(x-1, midVal);
     29         return Ackermann(x-1, Ackermann(x, y-1));
     30     }
     31 }
     32 
     33 
     34 
     35 int AckermannLoop(int x, int y)
     36 {
     37     // (步骤1)
     38     struct SnapShotStruct 
     39     {
     40         int inputX;       // 会改变的参数
     41         int inputY;       // 会改变的参数
     42         int stage;
     43                           // 没有局部变量
     44     };
     45 
     46     // (步骤2)
     47     int returnVal;        
     48 
     49     // (步骤3)
     50     stack<SnapShotStruct> snapshotStack;
     51 
     52     // (步骤4)
     53     SnapShotStruct currentSnapshot;
     54     currentSnapshot.inputX = x;
     55     currentSnapshot.inputY = y;
     56     currentSnapshot.stage = 0;
     57 
     58     snapshotStack.push(currentSnapshot);
     59 
     60     // (步骤5)
     61     while(!snapshotStack.empty())
     62     {
     63         currentSnapshot=snapshotStack.top();
     64         snapshotStack.pop();
     65 
     66         // (步骤6)
     67         switch(currentSnapshot.stage)
     68         {
     69             // (步骤7)
     70         case 0:
     71             // 终止条件
     72             if(currentSnapshot.inputX == 0)
     73             {
     74                 // (步骤8 & 步骤9)
     75                 returnVal = currentSnapshot.inputY + 1;
     76                 continue;             // 这里必须返回
     77             }
     78             // 错误处理条件        
     79             if (currentSnapshot.inputX < 0  ||  currentSnapshot.inputY < 0)
     80             {
     81                 // (步骤8 & 步骤9)
     82                 returnVal = -1;
     83                 continue;             // 这里必须返回
     84             }  
     85             // 线性方法的递归调用 
     86             else if (currentSnapshot.inputX > 0 && 0 == currentSnapshot.inputY) 
     87             {
     88                 // (步骤10)
     89 
     90                 // 创建新快照
     91                 SnapShotStruct newSnapshot;
     92                 newSnapshot.inputX= currentSnapshot.inputX - 1; // 参数设定 calling itself ( Ackermann(x-1, 1) )
     93                 newSnapshot.inputY= 1;                          // 参数设定 calling itself ( Ackermann(x-1, 1) )
     94                 newSnapshot.stage= 0;
     95                 snapshotStack.push(newSnapshot);
     96                 continue;
     97             }
     98             // Recursive call by Nested method
     99             else
    100             {
    101                 // (步骤10)
    102 
    103                 currentSnapshot.stage=1;                       
    104                 snapshotStack.push(currentSnapshot);
    105 
    106                 // 创建新快照
    107                 SnapShotStruct newSnapshot;
    108                 newSnapshot.inputX= currentSnapshot.inputX;        //参数设定calling itself ( Ackermann(x, y-1) )
    109                 newSnapshot.inputY= currentSnapshot.inputY - 1; //参数设定calling itself ( Ackermann(x, y-1) )
    110                 newSnapshot.stage = 0;
    111                 snapshotStack.push(newSnapshot);
    112                 continue;
    113             }
    114             break;
    115         case 1:
    116             // (步骤10)
    117 
    118             // 创建新快照
    119             SnapShotStruct newSnapshot;
    120             newSnapshot.inputX= currentSnapshot.inputX - 1;   // 设定参数calling itself ( Ackermann(x-1,  Ackermann(x, y-1)) )
    121             newSnapshot.inputY= returnVal;                    // 设定参数calling itself ( Ackermann(x-1,  Ackermann(x, y-1)) )
    122             newSnapshot.stage = 0;
    123             snapshotStack.push(newSnapshot);
    124             continue;
    125             break;
    126         }
    127     }
    128     // (步骤2)
    129     return returnVal;
    130 }     
    131 #endif //__NESTED_RECURSION_H__

![复制代码][copycode.gif]

测试代码：

![ExpandedBlockStart.gif][]

![复制代码][copycode.gif]

1 #include <tchar.h>
     2 #include "BinaryRecursion.h"
     3 #include "LinearRecursion.h"
     4 #include "MutualRecursion.h"
     5 #include "NestedRecursion.h"
     6 #include "TailRecursion.h"
     7 
     8 
     9 int _tmain(int argc,_TCHAR argv[] )
    10 {
    11     // Binary Recursion
    12     int result = FibNum(10);
    13     int result2 = FibNumLoop(10);
    14 
    15     printf("FibNum(10) = %d\n",result);
    16     printf("FibNumLoop(10) = %d\n",result2);
    17 
    18 
    19     // Linear Recursion
    20     result = Fact(10);
    21     result2 = FactLoop(10);
    22 
    23     printf("Fact(10) = %d\n",result);
    24     printf("FactLoop(10) = %d\n",result2);
    25 
    26 
    27     // Tail Recursion
    28     result = FibNum2(10,5,4);
    29     result2 = FibNum2Loop(10,5,4);
    30 
    31     printf("FibNum2(10,5,4) = %d\n",result);
    32     printf("FibNumLoop2(10,5,4) = %d\n",result2);
    33 
    34 
    35     // Mutual Recursion
    36     bool bResult = IsOddNumber(10);
    37     bool bResult2 = IsOddNumberLoop(10);
    38 
    39     bool bResult3 = IsEvenNumber(10);
    40     bool bResult4 = IsEvenNumberLoop(10);
    41 
    42     printf("IsOddNumber(10) = %d\n",(int)bResult);
    43     printf("IsOddNumberLoop(10) = %d\n",(int)bResult2);
    44     printf("IsEvenNumber(10) = %d\n",(int)bResult3);
    45     printf("IsEvenNumberLoop(10) = %d\n",(int)bResult4);
    46 
    47 
    48     // Nested Recursion
    49     result = Ackermann(3,2);
    50     result2 = AckermannLoop(3,2);
    51 
    52     printf("Ackermann(3,2) = %d\n",result);
    53     printf("AckermannLoop(3,2) = %d\n",result2);
    54 
    55     while(1){}
    56     return 0;
    57 }

![复制代码][copycode.gif]

6 更多的例子

*  [epQuickSort.h][]
 *  [epMergeSort.h][]
 *  [epKAryHeap.h][]
 *  [epPatriciaTree.h][]

7 结论

我的结论就是在c/c++或者Java代码中，尽量避免用递归。但是正如你看到的，递归容易理解，但是容易导致栈溢出。虽然循环版本的函数不会增加代码可读性和提升性能，但是它能有效的避免冲突或未定义行为。正如我开头所说，我的做法通常是在代码中写两份代码，一份递归，一份循环的。前者用于理解代码，后者用于实际的运行和测试用。如果你对于自己代码中使用这两种代码的利弊很清楚，你可以选择你自己的方式

[ExpandedBlockStart.gif]: /images/20220721/c5c899a618644004952b2a53c3810acb.png
[copycode.gif]: /images/20220721/73f3f00e8b164b30927a730a0dc6254f.png
[epQuickSort.h]: https://github.com/juhgiyo/EpLibrary/blob/gh-pages/EpLibrary2.0/EpFoundation/Headers/epQuickSort.h
[epMergeSort.h]: https://github.com/juhgiyo/EpLibrary/blob/gh-pages/EpLibrary2.0/EpFoundation/Headers/epMergeSort.h
[epKAryHeap.h]: https://github.com/juhgiyo/EpLibrary/blob/gh-pages/EpLibrary2.0/EpFoundation/Headers/epKAryHeap.h
[epPatriciaTree.h]: https://github.com/juhgiyo/EpLibrary/blob/gh-pages/EpLibrary2.0/EpFoundation/Headers/epPatriciaTree.h