循环include，如何破 - C++当前位置:& &&&循环include，如何破循环include，如何破&&网友分享于：&&浏览：100次循环include，怎么破？代码示意如下：
#pragma&once
#include&"b.h"
&&&&class&AA&{
#pragma&once
#include&"a.h"
&&&&void&f(A::AA*&p);
编译告诉我，A不是有效的类名或命名空间。
------解决方案--------------------必须&前向声明Class------解决方案--------------------A.cpp中&先
b成员使用指针形式------解决方案--------------------貌似看楼主写的
两个都想相互前置申明的吧！
嵌套类，一层一个::的访问------解决方案--------------------a.h&里面包含b.h,&其他不变.
#pramma&once
&&void&f(AA&*p);
&&VS2008通过了，你试试。
&&手机发的，不知道打错没。------解决方案--------------------cpp里只包含A.h&我的能用------解决方案--------------------头文件中用指针代替对象------解决方案--------------------你为什么而定义AA.
如果你只是想只有AA能访问它，你可以把他设为私有。
如果你想其他文件的能访问它，你大可单独定义，A的公有局部类AA和他本身没有一毛钱的关系。
AA的名字只在当前作用域是可见的。
我能想到的能实现的方法只能是在A或当前作用域的类里面定义AA类型的成员，然后传给f函数。------解决方案--------------------刚试了下，结果是：
&&局部类只有在局部使用！------解决方案--------------------未规范标准的错误------解决方案--------------------//A.h
class&AA{}
#include&"A.h"
#include&"B.h"
#include&"a.h"
void&f(A::AA*&p);&
#include&"A.h"
#include&"B.h"
..... 共&2&页:
12345678910
12345678910
12345678910 上一篇：下一篇：文章评论相关解决方案 12345678910 Copyright & &&版权所有c/c++（35）
摘要：我们经常会用到递归函数，但是如果递归深度太大时，往往导致栈溢出。而递归深度往往不太容易把握，所以比较安全一点的做法就是：用循环代替递归。文章最后的原文里面讲了如何用10步实现这个过程，相当精彩。本文翻译了这篇文章，并加了自己的一点注释和理解。
模拟函数的目的
递归和模拟函数的优缺点
用栈和循环代替递归的个步骤
替代过程的几个简单例子
更多的例子
　　一般我们在进行排序比如归并排序或者树操作时会用到递归函数。但是如果递归深度达到一定程度以后，就会出现意想不到的结果比如堆栈溢出。虽然有很多有经验的开发者都知道了如何用循环函数或者栈加循环来代替递归函数，以防止栈溢出，但我还是想分享一下这些方法，这或许会对初学者有很大的帮助。
2&模拟函数的目的
　　如果你正在使用递归函数，并且没有控制递归调用，而栈资源又比较有限，调用层次过深的时候就可能导致栈溢出堆冲突。模拟函数的目的就是在堆中开辟区域来模拟栈的行为，这样你就能控制内存分配和流处理，从而避免栈溢出。如果能用循环函数来代替效果会更好，这是一个比较需要时间和经验来处理的事情，出于这些原因，这篇文章为初学者提供了一个简单的参考，怎样使用循环函数来替代递归函数，以防止栈溢出？
3 递归函数和模拟函数的优缺点
　　递归函数：
　　优点：算法比较直观。可以参考文章后面的例子
　　缺点：可能导致栈溢出或者堆冲突
　　你可以试试执行下面两个函数(后面的一个例子)，IsEvenNumber(递归实现和模拟实现，他们在头文件"MutualRecursion.h"中声明。你可以将传入参数设定为10000，像下面这样：
#include "MutualRecursion.h"
bool result = IsEvenNumberLoop(10000); // 成功返回
bool result2 = IsEvenNumber(10000);
// 会发生堆栈溢出
&有些人可能会问：如果我增加栈的容量不就可以避免栈溢出吗？好吧，这只是暂时的解决问题的办法，如果调用层次越来越深，很有可能会再次发生溢出。
&　　模拟函数：
　　优点：能避免栈溢出或者堆冲突错误，能对过程和内存进行更好的控制
　　缺点：算法不是太直观，代码难以维护
4 用栈和循环代替递归的10个步骤
1&定义一个新的结构体，用于保存递归结构中的一些数据和状态信息
2&在内部需要包含的变量有以下几种：
　　A&一般当递归函数调用自身时，函数参数会发生变化。所以你需要包含变化的参数，引用除外。比如下面的例子中，参数应该包含在结构体中，而不需要。
void SomeFunc(int n, int &retVal);
　　B&阶段性变量"stage")，详见第六条规则
　　C&函数调用返回以后还需要继续使用的局部变量一般在二分递归和嵌套递归中很常见
1 // Recursive Function "First rule" example
2 int SomeFunc(int n, int &retIdx)
int test = SomeFunc(n-1, retIdx);
17 // Conversion to Iterative Function
18 int SomeFuncLoop(int n, int &retIdx)
// (First rule)
struct SnapShotStruct {
// - parameter input
// - local variable that will be used
after returning from the function call
// - retIdx can be ignored since it is a reference.
// - Since there is process needed to be done
after recursive call. (Sixth rule)
1&在函数的开头创建一个局部变量，这个值扮演了递归函数的返回函数角色。它相当于为每次递归调用保存一个临时值，因为函数只能有一种返回类型，如果递归函数的返回类型是，你可以忽略这个局部变量。如果有缺省的返回值，就应该用缺省值初始化这个局部变量。
1 // Recursive Function "Second rule" example
2 int SomeFunc(int n, int &retIdx)
int test = SomeFunc(n-1, retIdx);
16 // Conversion to Iterative Function
17 int SomeFuncLoop(int n, int &retIdx)
// (First rule)
struct SnapShotStruct {
// - parameter input
// - local variable that will be used
after returning from the function call
// - retIdx can be ignored since it is a reference.
// - Since there is process needed to be done
after recursive call. (Sixth rule)
// (Second rule)
int retVal = 0;
// initialize with default returning value
// (Second rule)
return retV
创建一个栈用于保存&&结构体类型变量
1 // Recursive Function "Third rule" example
3 // Conversion to Iterative Function
4 int SomeFuncLoop(int n, int &retIdx)
// (First rule)
struct SnapShotStruct {
// - parameter input
// - local variable that will be used
after returning from the function call
// - retIdx can be ignored since it is a reference.
// - 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& snapshotS
// (Second rule)
return retV
创建一个新的&&实例，然后将其中的参数等初始化，并将&&实例压入栈
1 // Recursive Function "Fourth rule" example
3 // Conversion to Iterative Function
4 int SomeFuncLoop(int n, int &retIdx)
// (First rule)
struct SnapShotStruct {
// - parameter input
// - local variable that will be used
after returning from the function call
// - retIdx can be ignored since it is a reference.
// - 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& snapshotS
// (Fourth rule)
SnapShotStruct currentS
currentSnapshot.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);
// (Second rule)
return retV
写一个循环，使其不断执行直到栈为空。在循环的每一次迭代过程中，弹出&&对象。
1 // Recursive Function "Fifth rule" example
3 // Conversion to Iterative Function
4 int SomeFuncLoop(int n, int &retIdx)
// (First rule)
struct SnapShotStruct {
// - parameter input
// - local variable that will be used
after returning from the function call
// - retIdx can be ignored since it is a reference.
// - 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& snapshotS
// (Fourth rule)
SnapShotStruct currentS
currentSnapshot.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();
// (Second rule)
return retV
将当前阶段一分为二针对当前只有单一递归调用的情形。第一个阶段代表了下一次递归调用之前的情况，第二阶段代表了下一次递归调用完成并返回之后的情况返回值已经被保存，并在此之前被累加。
如果当前阶段有两次递归调用，就必须分为个阶段。阶段：第一次调用返回之前，阶段：阶段执行的调用过程。阶段：第二次调用返回之前。
如果当前阶段有三次递归调用，就必须至少分为个阶段。
依次类推。
1 // Recursive Function "Sixth rule" example
2 int SomeFunc(int n, int &retIdx)
int test = SomeFunc(n-1, retIdx);
16 // Conversion to Iterative Function
17 int SomeFuncLoop(int n, int &retIdx)
// (First rule)
struct SnapShotStruct {
// - parameter input
// - local variable that will be used
after returning from the function call
// - retIdx can be ignored since it is a reference.
// - 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& snapshotS
// (Fourth rule)
SnapShotStruct currentS
currentSnapshot.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)
// before ( SomeFunc(n-1, retIdx); )
// after ( SomeFunc(n-1, retIdx); )
// (Second rule)
return retV
根据阶段变量stage的值切换到相应的处理流程并处理相关过程。
1 // Recursive Function "Seventh rule" example
2 int SomeFunc(int n, int &retIdx)
int test = SomeFunc(n-1, retIdx);
16 // Conversion to Iterative Function
17 int SomeFuncLoop(int n, int &retIdx)
// (First rule)
struct SnapShotStruct {
// - parameter input
// - local variable that will be used
after returning from the function call
// - retIdx can be ignored since it is a reference.
// - 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& snapshotS
// (Fourth rule)
SnapShotStruct currentS
currentSnapshot.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)
// (Seventh rule)
if( currentSnapshot.n&0 )
// (Seventh rule)
currentSnapshot.test = retV
currentSnapshot.test--;
// (Second rule)
return retV
如果递归有返回值，将这个值保存下来放在临时变量里面，比如。当循环结束时，这个临时变量的值就是整个递归处理的结果。
1 // Recursive Function "Eighth rule" example
2 int SomeFunc(int n, int &retIdx)
int test = SomeFunc(n-1, retIdx);
16 // Conversion to Iterative Function
17 int SomeFuncLoop(int n, int &retIdx)
// (First rule)
struct SnapShotStruct {
// - parameter input
// - local variable that will be used
after returning from the function call
// - retIdx can be ignored since it is a reference.
// - 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& snapshotS
// (Fourth rule)
SnapShotStruct currentS
currentSnapshot.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)
// (Seventh rule)
if( currentSnapshot.n&0 )
// (Eighth rule)
retVal = 0 ;
// (Seventh rule)
currentSnapshot.test = retV
currentSnapshot.test--;
// (Eighth rule)
retVal = currentSnapshot.
// (Second rule)
return retV
如果递归函数有&&关键字，你应该在循环里面用&&代替。如果了一个返回值，你应该在循环里面保存下来步骤，然后。大部分情况下，步骤九是可选的，但是它能帮助你避免逻辑错误。
1 // Recursive Function "Ninth rule" example
2 int SomeFunc(int n, int &retIdx)
int test = SomeFunc(n-1, retIdx);
16 // Conversion to Iterative Function
17 int SomeFuncLoop(int n, int &retIdx)
// (First rule)
struct SnapShotStruct {
// - parameter input
// - local variable that will be used
after returning from the function call
// - retIdx can be ignored since it is a reference.
// - 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& snapshotS
// (Fourth rule)
SnapShotStruct currentS
currentSnapshot.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)
// (Seventh rule)
if( currentSnapshot.n&0 )
// (Eighth rule)
retVal = 0 ;
// (Ninth rule)
// (Seventh rule)
currentSnapshot.test = retV
currentSnapshot.test--;
// (Eighth rule)
retVal = currentSnapshot.
// (Ninth rule)
// (Second rule)
return retV
为了模拟下一次递归函数的调用，你必须在当前循环函数里面再生成一个新的&&结构体作为下一次调用的快照，初始化其参数以后压入栈，并&&。如果当前调用在执行完成后还有一些事情需要处理，那么更改它的阶段状态&&到相应的过程，并在压入之前，把本次的&&压入。
1 // Recursive Function "Tenth rule" example
2 int SomeFunc(int n, int &retIdx)
int test = SomeFunc(n-1, retIdx);
16 // Conversion to Iterative Function
17 int SomeFuncLoop(int n, int &retIdx)
// (First rule)
struct SnapShotStruct {
// - parameter input
// - local variable that will be used
after returning from the function call
// - retIdx can be ignored since it is a reference.
// - 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& snapshotS
// (Fourth rule)
SnapShotStruct currentS
currentSnapshot.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)
// (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 newS
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);
// (Eighth rule)
retVal = 0 ;
// (Ninth rule)
// (Seventh rule)
currentSnapshot.test = retV
currentSnapshot.test--;
// (Eighth rule)
retVal = currentSnapshot.
// (Ninth rule)
// (Second rule)
return retV
5 替代过程的几个简单例子
以下几个例子均在vs2008环境下开发，主要包含了：
（1）线性递归
1 #ifndef __LINEAR_RECURSION_H__
2 #define __LINEAR_RECURSION_H__
4 #include &stack&
5 using namespace
8 * \brief 求n的阶乘
10 * \return
11 * \note result = n! 递归实现
13 int Fact(long n)
return -1;
if(0 == n)
return ( n* Fact(n-1));
26 * \brief 求n的阶乘
27 * \para
28 * \return
29 * \note result = n! 循环实现
31 int FactLoop(long n)
// (步骤1)
struct SnapShotStruct // 快照结构体局部声明
long inputN;
// 会改变的参数
// 没有局部变量
// 阶段变量用于快照跟踪
// (步骤2)
int returnV
// 用于保存当前调用返回值
// (步骤3)
stack&SnapShotStruct& snapshotS
// (步骤4)
SnapShotStruct currentS
currentSnapshot.inputN=n;
currentSnapshot.stage=0; // 阶段变量初始化
snapshotStack.push(currentSnapshot);
// (步骤5)
while(!snapshotStack.empty())
currentSnapshot=snapshotStack.top();
snapshotStack.pop();
// (步骤6)
switch(currentSnapshot.stage)
// (步骤7)
if(0&currentSnapshot.inputN)
// (步骤8 & 步骤9)
returnVal = -1;
if(0 == currentSnapshot.inputN)
// (步骤8 & 步骤9)
returnVal = 1;
// (步骤10)
// 返回 ( n* Fact(n-1)); 分为2步：
// (第一步调用自身，第二步用返回值乘以当前n值)
// 这里我们拍下快照.
currentSnapshot.stage=1; // 当前的快照表示正在被处理，并等待自身调用结果返回，所以赋值为1
snapshotStack.push(currentSnapshot);
// 创建一个新的快照，用于调用自身
SnapShotStruct newS
newSnapshot.inputN= currentSnapshot.inputN -1 ; // 初始化参数
newSnapshot.stage = 0 ;
// 从头开始执行自身，所以赋值stage==0
snapshotStack.push(newSnapshot);
// (步骤7)
// (步骤8)
returnVal = currentSnapshot.inputN * returnV
// (步骤9)
// (步骤2)
return returnV
115 #endif //__LINEAR_RECURSION_H__
（2）二分递归
1 #ifndef __BINARY_RECURSION_H__
2 #define __BINARY_RECURSION_H__
4 #include &stack&
5 using namespace
8 * \function FibNum
9 * \brief 求斐波纳契数列
10 * \para
11 * \return
12 * \note 递归实现
14 int FibNum(int n)
if (n & 1)
return -1;
if (1 == n || 2 == n)
// 这里可以看成是
//int addVal = FibNum( n - 1);
// addVal += FibNum(n - 2);
// return addV
return FibNum(n - 1) + FibNum(n - 2);
28 * \function FibNumLoop
29 * \brief 求斐波纳契数列
30 * \para
31 * \return
32 * \note 循环实现
34 int FibNumLoop(int n)
// (步骤1)
struct SnapShotStruct // 快照结构体局部声明
int inputN;
// 会改变的参数
// 局部变量
// 阶段变量用于快照跟踪
// (步骤2)
int returnV
// 用于保存当前调用返回值
// (步骤3)
stack&SnapShotStruct& snapshotS
// (步骤4)
SnapShotStruct currentS
currentSnapshot.inputN=n;
currentSnapshot.stage=0; // 阶段变量初始化
snapshotStack.push(currentSnapshot);
// (步骤5)
while(!snapshotStack.empty())
currentSnapshot=snapshotStack.top();
snapshotStack.pop();
// (步骤6)
switch(currentSnapshot.stage)
// (步骤7)
if(currentSnapshot.inputN&1)
// (步骤8 & 步骤9)
returnVal = -1;
if(currentSnapshot.inputN == 1 || currentSnapshot.inputN == 2 )
// (步骤8 & 步骤9)
returnVal = 1;
// (步骤10)
// 返回 ( FibNum(n - 1) + FibNum(n - 2)); 相当于两步
// (第一次调用参数是 n-1, 第二次调用参数 n-2)
// 这里我们拍下快照，分成2个阶段
currentSnapshot.stage=1;
// 当前的快照表示正在被处理，并等待自身调用结果返回，所以赋值为1
snapshotStack.push(currentSnapshot);
// 创建一个新的快照，用于调用自身
SnapShotStruct newS
newSnapshot.inputN= currentSnapshot.inputN -1 ; //初始化参数 FibNum(n - 1)
newSnapshot.stage = 0 ;
snapshotStack.push(newSnapshot);
// (步骤7)
// (步骤10)
currentSnapshot.addVal = returnV
currentSnapshot.stage=2;
// 当前的快照正在被处理，并等待的自身调用结果，所以阶段变量变成2
snapshotStack.push(currentSnapshot);
// 创建一个新的快照，用于调用自身
SnapShotStruct newS
newSnapshot.inputN= currentSnapshot.inputN - 2 ; // 初始化参数 FibNum(n - 2)
newSnapshot.stage = 0 ;
// 从头开始执行，阶段变量赋值为0
snapshotStack.push(newSnapshot);
// (步骤8)
returnVal = currentSnapshot.addVal + returnV
// actual addition of ( FibNum(n - 1) + FibNum(n - 2) )
// (步骤9)
// (步骤2)
return returnV
135 #endif //__BINARY_RECURSION_H__
（3）尾递归
1 #ifndef __TAIL_RECURSION_H__
2 #define __TAIL_RECURSION_H__
4 #include &stack&
5 using namespace
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,...
14 int FibNum2(int n, int x, int y)
if (1 == n)
return FibNum2(n-1, y, x+y);
26 * \function FibNum2Loop
27 * \brief 2阶裴波那契序列
28 * \para
29 * \return
30 * \note 循环实现 在尾递归中, 递归调用后除了返回没有任何其它的操作, 所以在变为循环时，不需要stage变量
32 int FibNum2Loop(int n, int x, int y)
// (步骤1)
struct SnapShotStruct
int inputN;
// 会改变的参数
int inputX;
// 会改变的参数
int inputY;
// 会改变的参数
// 没有局部变量
// (步骤2)
int returnV
// (步骤3)
stack&SnapShotStruct& snapshotS
// (步骤4)
SnapShotStruct currentS
currentSnapshot.inputN =
currentSnapshot.inputX =
currentSnapshot.inputY =
snapshotStack.push(currentSnapshot);
// (步骤5)
while(!snapshotStack.empty())
currentSnapshot=snapshotStack.top();
snapshotStack.pop();
if(currentSnapshot.inputN == 1)
// (步骤8 & 步骤9)
returnVal = currentSnapshot.inputY;
// (步骤10)
// 创建新快照
SnapShotStruct newS
newSnapshot.inputN= currentSnapshot.inputN -1 ; // 初始化，调用( FibNum(n-1, y, x+y) )
newSnapshot.inputX= currentSnapshot.inputY;
newSnapshot.inputY= currentSnapshot.inputX + currentSnapshot.inputY;
snapshotStack.push(newSnapshot);
// (步骤2)
return returnV
86 #endif //__TAIL_RECURSION_H__
（4）互递归
1 #ifndef __MUTUAL_RECURSION_H__
2 #define __MUTUAL_RECURSION_H__
3 #include &stack&
4 using namespace
6 bool IsEvenNumber(int n);//判断是否是偶数
7 bool IsOddNumber(int n);//判断是否是奇数
8 bool isOddOrEven(int n, int stage);//判断是否是奇数或偶数
10 /****************************************************/
11 //互相调用的递归实现
12 bool IsOddNumber(int n)
// 终止条件
if (0 == n)
return false;
// 互相调用函数的递归调用
return IsEvenNumber(n - 1);
22 bool IsEvenNumber(int n)
// 终止条件
if (0 == n)
return true;
// 互相调用函数的递归调用
return IsOddNumber(n - 1);
33 /*************************************************/
34 //互相调用的循环实现
35 bool IsOddNumberLoop(int n)
return isOddOrEven(n , 0);
40 bool IsEvenNumberLoop(int n)
return isOddOrEven(n , 1);
45 bool isOddOrEven(int n, int stage)
// (步骤1)
struct SnapShotStruct
int inputN;
// 会改变的参数
// 没有局部变量
// (步骤2)
bool returnV
// (步骤3)
stack&SnapShotStruct& snapshotS
// (步骤4)
SnapShotStruct currentS
currentSnapshot.inputN =
currentSnapshot.stage =
snapshotStack.push(currentSnapshot);
// (步骤5)
while(!snapshotStack.empty())
currentSnapshot=snapshotStack.top();
snapshotStack.pop();
// (步骤6)
switch(currentSnapshot.stage)
// (步骤7)
// bool IsOddNumber(int n)
// 终止条件
if (0 == currentSnapshot.inputN)
// (步骤8 & 步骤9)
returnVal = false;
// (步骤10)
// 模拟互调用的递归调用
// 创建新的快照
SnapShotStruct newS
newSnapshot.inputN= currentSnapshot.inputN - 1; // 初始化参数
// 调用 ( IsEvenNumber(n - 1) )
newSnapshot.stage= 1;
snapshotStack.push(newSnapshot);
// (步骤7)
// bool IsEvenNumber(int n)
// 终止条件
if (0 == currentSnapshot.inputN)
// (步骤8 & 步骤9)
returnVal = true;
// (步骤10)
// 模拟互调用的递归调用
// 创建新的快照
SnapShotStruct newS
newSnapshot.inputN= currentSnapshot.inputN - 1; //
// calling itself ( IsEvenNumber(n - 1) )
newSnapshot.stage= 0;
snapshotStack.push(newSnapshot);
// (步骤2)
return returnV
135 #endif //__MUTUAL_RECURSION_H__
（5）嵌套递归
1 #ifndef __NESTED_RECURSION_H__
2 #define __NESTED_RECURSION_H__
3 #include &stack&
4 using namespace
6 int Ackermann(int x, int y)
// 终止条件
if (0 == x)
return y + 1;
// 错误处理条件
return -1;
// 线性方法的递归调用
else if (x & 0 && 0 == y)
return Ackermann(x-1, 1);
// 嵌套方法的递归调用
//可以看成是：
// int midVal = Ackermann(x, y-1);
// return Ackermann(x-1, midVal);
return Ackermann(x-1, Ackermann(x, y-1));
35 int AckermannLoop(int x, int y)
// (步骤1)
struct SnapShotStruct
int inputX;
// 会改变的参数
int inputY;
// 会改变的参数
// 没有局部变量
// (步骤2)
int returnV
// (步骤3)
stack&SnapShotStruct& snapshotS
// (步骤4)
SnapShotStruct currentS
currentSnapshot.inputX =
currentSnapshot.inputY =
currentSnapshot.stage = 0;
snapshotStack.push(currentSnapshot);
// (步骤5)
while(!snapshotStack.empty())
currentSnapshot=snapshotStack.top();
snapshotStack.pop();
// (步骤6)
switch(currentSnapshot.stage)
// (步骤7)
// 终止条件
if(currentSnapshot.inputX == 0)
// (步骤8 & 步骤9)
returnVal = currentSnapshot.inputY + 1;
// 这里必须返回
// 错误处理条件
if (currentSnapshot.inputX & 0
currentSnapshot.inputY & 0)
// (步骤8 & 步骤9)
returnVal = -1;
// 这里必须返回
// 线性方法的递归调用
else if (currentSnapshot.inputX & 0 && 0 == currentSnapshot.inputY)
// (步骤10)
// 创建新快照
SnapShotStruct newS
newSnapshot.inputX= currentSnapshot.inputX - 1; // 参数设定 calling itself ( Ackermann(x-1, 1) )
newSnapshot.inputY= 1;
// 参数设定 calling itself ( Ackermann(x-1, 1) )
newSnapshot.stage= 0;
snapshotStack.push(newSnapshot);
// Recursive call by Nested method
// (步骤10)
currentSnapshot.stage=1;
snapshotStack.push(currentSnapshot);
// 创建新快照
SnapShotStruct newS
newSnapshot.inputX= currentSnapshot.inputX;
//参数设定calling itself ( Ackermann(x, y-1) )
newSnapshot.inputY= currentSnapshot.inputY - 1; //参数设定calling itself ( Ackermann(x, y-1) )
newSnapshot.stage = 0;
snapshotStack.push(newSnapshot);
// (步骤10)
// 创建新快照
SnapShotStruct newS
newSnapshot.inputX= currentSnapshot.inputX - 1;
// 设定参数calling itself ( Ackermann(x-1,
Ackermann(x, y-1)) )
newSnapshot.inputY= returnV
// 设定参数calling itself ( Ackermann(x-1,
Ackermann(x, y-1)) )
newSnapshot.stage = 0;
snapshotStack.push(newSnapshot);
// (步骤2)
return returnV
131 #endif //__NESTED_RECURSION_H__
测试代码：
1 #include &tchar.h&
2 #include "BinaryRecursion.h"
3 #include "LinearRecursion.h"
4 #include "MutualRecursion.h"
5 #include "NestedRecursion.h"
6 #include "TailRecursion.h"
9 int _tmain(int argc,_TCHAR argv[] )
// Binary Recursion
int result = FibNum(10);
int result2 = FibNumLoop(10);
printf("FibNum(10) = %d\n",result);
printf("FibNumLoop(10) = %d\n",result2);
// Linear Recursion
result = Fact(10);
result2 = FactLoop(10);
printf("Fact(10) = %d\n",result);
printf("FactLoop(10) = %d\n",result2);
// Tail Recursion
result = FibNum2(10,5,4);
result2 = FibNum2Loop(10,5,4);
printf("FibNum2(10,5,4) = %d\n",result);
printf("FibNumLoop2(10,5,4) = %d\n",result2);
// Mutual Recursion
bool bResult = IsOddNumber(10);
bool bResult2 = IsOddNumberLoop(10);
bool bResult3 = IsEvenNumber(10);
bool bResult4 = IsEvenNumberLoop(10);
printf("IsOddNumber(10) = %d\n",(int)bResult);
printf("IsOddNumberLoop(10) = %d\n",(int)bResult2);
printf("IsEvenNumber(10) = %d\n",(int)bResult3);
printf("IsEvenNumberLoop(10) = %d\n",(int)bResult4);
// Nested Recursion
result = Ackermann(3,2);
result2 = AckermannLoop(3,2);
printf("Ackermann(3,2) = %d\n",result);
printf("AckermannLoop(3,2) = %d\n",result2);
while(1){}
6 更多的例子
我的结论就是在c/c++或者Java代码中，尽量避免用递归。但是正如你看到的，递归容易理解，但是容易导致栈溢出。虽然循环版本的函数不会增加代码可读性和提升性能，但是它能有效的避免冲突或未定义行为。正如我开头所说，我的做法通常是在代码中写两份代码，一份递归，一份循环的。前者用于理解代码，后者用于实际的运行和测试用。如果你对于自己代码中使用这两种代码的利弊很清楚，你可以选择你自己的方式。
本文及包含的代码遵从协议
&************************************************************************************************************
以上就是原文的一些内容，感谢原作者。
这篇文章中的代码我在调式过程中，发现了一个问题：循环版本的函数在执行效率方面存在问题。以后再改
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：51980次
积分：1266
积分：1266
排名：千里之外
原创：69篇
转载：38篇
(1)(1)(1)(5)(3)(2)(2)(3)(2)(1)(1)(3)(57)(1)(1)(7)(2)(10)(2)(1)(1)