如何使用堆栈和 while 循环替换递归函数以避免堆栈溢出
本文介绍了使用堆栈和while循环替换递归函数以避免堆栈溢出的10条规则（步骤）。
目录
简介
在某些情况下，我们更倾向于使用递归函数，例如排序（归并排序）或树操作（堆化向上/堆化向下）。然而，如果在某些环境中，递归函数的深度过深，例如在Visual C++代码中，可能会出现意外结果，如堆栈溢出。许多专业开发人员可能已经知道如何提前通过替换为迭代函数或使用堆栈（堆栈）和while循环（递归模拟函数）来替换递归函数以避免堆栈溢出。但我认为分享一个简单通用的方法（或指南）来使用堆栈（堆栈）和while循环替换递归函数以避免堆栈溢出，对新手开发人员会很有帮助。
模拟函数目的
如果您使用递归函数，由于您无法控制调用堆栈并且堆栈是有限的，当递归调用的深度过深时，可能会发生堆栈溢出/堆损坏。模拟函数的目的是将调用堆栈移至堆中的堆栈，以便您可以更好地控制内存和进程流，并避免堆栈溢出。如果将其替换为迭代函数会更好，但为此需要时间和经验来正确处理每个递归函数，因此本文是一个简单的指南，旨在帮助新手开发人员在尚未准备好正确处理一切时，通过使用递归函数来避免堆栈溢出。
递归函数和模拟函数的优缺点
递归函数
- 优点
- 对算法非常直观
- 请参阅 RecursiveToLoopSamples.zip 中的示例。
- 对算法非常直观
- 缺点
- 可能发生“堆栈溢出”或“堆损坏”
- 尝试运行“MutualRecursion.h”中“RecursiveToLoopSamples.zip”的
IsEvenNumber函数（递归）和IsEvenNumberLoop函数（模拟），并以“10000”作为其参数输入。
- 尝试运行“MutualRecursion.h”中“RecursiveToLoopSamples.zip”的
- 可能发生“堆栈溢出”或“堆损坏”
#include "MutualRecursion.h"
bool result = IsEvenNumberLoop(10000); // returns successfully
bool result2 = IsEvenNumber(10000); // stack-overflow error occurs
有人说“（为了修复递归函数引起的堆栈溢出，）增加堆栈的最大值以避免堆栈溢出。”但 N仅仅是权宜之计，因为如果递归调用越来越深，堆栈溢出很可能会再次出现。
模拟函数
- 优点
- 可以避免“堆栈溢出”或“堆损坏”错误。
- 对进程流和内存有更多控制。
- 缺点
- 对算法不太直观。
- 难以维护代码。
用堆栈和while循环替换递归函数的10条规则（步骤）
第一条规则
- 定义一个名为“
Snapshot”的新结构体。该数据结构的目的是保存递归结构中使用的任何数据以及任何状态信息。 - “
Snapshot”结构体中要包含的内容。- 当递归函数调用自身时会发生变化的函数参数**然而，**当函数参数是引用时，则不需要将其包含在
Snapshot结构体中。因此，在下面的示例中，参数n应包含在结构体中，但参数retVal不应包含。void SomeFunc(int n, int &retVal);
- “
Stage”变量（通常是int，用于切换到正确的进程划分）- 请参阅“第六条规则”了解详细信息。
- 将在函数返回后使用的局部变量（可能发生在二元递归或嵌套递归期间）
- 当递归函数调用自身时会发生变化的函数参数**然而，**当函数参数是引用时，则不需要将其包含在
// 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;
}
// 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)
};
...
}
第二条规则
- 在函数顶部创建一个局部变量。该值将代表返回函数在递归函数中的作用。
- 在迭代函数中，它更像是递归函数内部每次递归调用的临时返回值持有者，因为C++函数只能有一个返回类型。
- 如果递归函数的返回类型是
void，则可以忽略创建此变量。 - 如果存在任何默认返回值，则将此局部变量初始化为默认返回值。
// Recursive Function "Second rule" example
int SomeFunc(int n, int &retIdx)
{
...
if(n>0)
{
int test = SomeFunc(n-1, retIdx);
test--;
...
return test;
}
...
return 0;
}
// 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
...
// (Second rule)
return retVal;
}
第三条规则
- 使用“
Snapshot”结构体类型创建一个堆栈。
// Recursive Function "Third rule" example
// 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;
...
// (Second rule)
return retVal;
}
第四条规则
- 创建一个新的“
Snapshot”实例，并使用输入到迭代函数中的参数和起始“Stage”编号进行初始化。 - 将
Snapshot实例推送到空堆栈。
// Recursive Function "Fourth rule" example
// 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);
...
// (Second rule)
return retVal;
}
第五条规则
- 创建一个
while循环，该循环在堆栈**不**为空时继续循环。 - 在
while循环的每次迭代中，从堆栈中弹出一个Snapshot对象
// Recursive Function "Fifth rule" example
// 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();
...
}
// (Second rule)
return retVal;
}
第六条规则
- 将阶段分成两部分（仅当递归函数中只有一个递归调用时）。第一种情况代表在进行下一个递归调用之前处理的递归函数中的代码，第二种情况代表在下一个递归调用返回后处理的代码（并且在函数返回之前可能收集或累积了返回值）。
- 在函数中有两个递归调用的情况下，必须有三个阶段
- **（阶段1 --> 递归调用 --> （从第一个递归调用返回）阶段2（阶段1中的递归调用）--> （从第二个递归调用返回）阶段3
- 在有三个不同递归调用的情况下，则至少需要4个阶段。
- 依此类推。
// Recursive Function "Sixth rule" example
int SomeFunc(int n, int &retIdx)
{
...
if(n>0)
{
int test = SomeFunc(n-1, retIdx);
test--;
...
return test;
}
...
return 0;
}
// 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:
... // before ( SomeFunc(n-1, retIdx); )
break;
case 1:
... // after ( SomeFunc(n-1, retIdx); )
break;
}
}
// (Second rule)
return retVal;
}
第七条规则
- 根据“
Stage”变量切换到进程划分 - 执行相关进程
// Recursive Function "Seventh rule" example
int SomeFunc(int n, int &retIdx)
{
...
if(n>0)
{
int test = SomeFunc(n-1, retIdx);
test--;
...
return test;
}
...
return 0;
}
// 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 )
{
...
}
...
break;
case 1:
// (Seventh rule)
currentSnapshot.test = retVal;
currentSnapshot.test--;
...
break;
}
}
// (Second rule)
return retVal;
}
第八条规则
- 如果递归函数有返回值，则将循环迭代的结果存储在局部变量（例如retVal）中。
- 当
while循环退出时，此局部变量将包含递归函数的最终结果。
// Recursive Function "Eighth rule" example
int SomeFunc(int n, int &retIdx)
{
...
if(n>0)
{
int test = SomeFunc(n-1, retIdx);
test--;
...
return test;
}
...
return 0;
}
// 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 )
{
...
}
...
// (Eighth rule)
retVal = 0 ;
...
break;
case 1:
// (Seventh rule)
currentSnapshot.test = retVal;
currentSnapshot.test--;
...
// (Eighth rule)
retVal = currentSnapshot.test;
...
break;
}
}
// (Second rule)
return retVal;
}
第九条规则
- 在递归函数中有“
return”关键字的情况下，“return”关键字应在“while”循环内转换为“continue”。
-
- 在递归函数返回值为值的情况下，如“第八条规则”所述，将返回值存储在局部变量（例如
retVal）中，然后“continue” - 大多数情况下，“第九条规则”是可选的，但它有助于避免逻辑错误。
- 在递归函数返回值为值的情况下，如“第八条规则”所述，将返回值存储在局部变量（例如
// Recursive Function "Ninth rule" example
int SomeFunc(int n, int &retIdx)
{
...
if(n>0)
{
int test = SomeFunc(n-1, retIdx);
test--;
...
return test;
}
...
return 0;
}
// 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 )
{
...
}
...
// (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;
}
第十条规则（也是最后一条...）
- 要在迭代函数中将递归函数内的递归调用转换为，创建一个新的“Snapshot”对象，初始化新的“
Snapshot”对象阶段，根据递归调用参数设置其成员变量，并推送到堆栈，然后“continue” - 如果递归调用后需要执行某些操作，请将当前“Snapshot”对象的阶段变量更改为相关阶段，并在将新的“Snapshot”对象推送到堆栈之前将其推送到堆栈。
// Recursive Function "Tenth rule" example
int SomeFunc(int n, int &retIdx)
{
...
if(n>0)
{
int test = SomeFunc(n-1, retIdx);
test--;
...
return test;
}
...
return 0;
}
// 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;
}
递归类型简单示例
- 请下载 RecursiveToLoopSamples.zip
- 解压文件。
- 使用Visual Studio打开项目。
- 此项目是使用Visual Studio 2008开发的
- 示例项目包含
- 线性递归示例
- 二元递归示例
- 尾递归示例
- 互递归示例
- 嵌套递归示例
更实用的示例来源
以下来源同时包含递归版本和模拟版本，其中模拟版本是使用上述方法推导出来的。
为什么源代码同时包含模拟版本和递归版本？
如果您查看源代码，您会很容易发现模拟版本比递归版本复杂得多。 对于不知道函数作用的人来说，要弄清楚带有循环的函数实际做什么会更困难。 所以，我更愿意保留两个版本，这样人们可以轻松地用递归版本测试简单的输入和输N出，而对于大量的操作，则使用模拟版本来避免堆栈溢出。
结论
我相信，在编写C/C++或Java代码时，必须谨慎使用递归函数以避免堆栈溢出错误。 然而，正如您从示例中看到的，在许多情况下，递归函数易于理解且易于编写，缺点是“如果递归函数调用的深度过深，就会导致堆栈溢出错误”。 因此，将递归函数转换为模拟函数并不是为了提高可读性或提高算法性能，而是为了规避崩溃或未定义行为/错误的简单方法。 正如我上面所说，我更喜欢在我的代码中同时保留递归版本和模拟版本，这样我就可以使用递归版本来提高代码的可读性和可维护性，并使用模拟版本来运行和测试代码。 您将可以自行选择如何编写代码，只要您了解您所做选择的优缺点即可。
参考
历史
- 2015.02.07：- 修复了损坏的链接
- 2013.06.09：- 修复了拼写错误（感谢 lovewubo）
- 2013.08.22：- 从GPL v3重新分发为MIT许可
- 2012.08.10：- 更新了目录
- 2012.08.04：- 将文章子部分移至“Howto”
- 2012.07.23：- 对文章进行了小的修复
- 2012.07.13：- 修改了目录
- 删除了章节
- 将文章移至“新手”部分
- 更改了措辞
- 2012.07.13：- 添加了目录。
- 修改了标题。
- 添加了新章节。
- 递归函数与迭代函数之间的区别
- 递归方法和迭代方法的优缺点
- 2012.07.12：- 修复了示例中的错误。
- 重新组织了文章。
- 添加了第九条和第十条规则。
- 为每条规则添加了示例。
- 2012.07.11：- 提交了文章。