不得不说,栈是很简单方便的,内存块的生命周期被栈自动控制,出栈入栈操作在指令集的层面被广泛支持。但在实际编码工作(而不是算法实验)中,栈的弊病也很明显,那就是很容易溢出,这是由于在目前常用的操作系统里,栈作为被定义的一段固定内存空间,是有长度限制的。没有长度限制的栈,我认为是可以存在的,只是会部分牺牲栈的高效性,因为这样要求在每次入栈操作之前检查溢出,避免方法我想是有的,只是会增加平台实现的复杂度。
这里仅仅用来记录避免栈溢出的方法。
用堆变量取代栈变量
当局部变量很大或者很多的时候,极易出现栈溢出,解决方法很简单,用堆来管理它们。
#include <iostream>
using namespace std;
class A;
int demo()
{
int x = 10000;
int y = 10000;
A * q = NULL;
//stack
A p[x*y];
//heap_1
q = new A[x*y];
delete q;
//heap_2
q = (A *)malloc(sizeof(A)*x*y);
free(q);
return 0;
}
demo中heap_1与heap_2的效果基本一样,区别在于new关键字会触发类A的构造函数,而malloc不会。
使用循环取代递归
递归是很经典的编程方法,它的优点是易于设计与理解,缺点也很明显,出入栈的时间与空间开销非常大。因为每当一个函数被调用,调用者自身的局部数据就会被压入栈中,而栈空间是有限定长度的。如果在算法设计大赛中轻易使用递归,面对庞大的测试数据,分分钟会面临爆栈的窘境。在很多时候,我们可以使用循环来取代递归,循环体不会产生入栈行为,自然不会溢出。下面以常见的二叉树搜索来举例。
//recursion
bool TreeSearch(Tree * source, int target)
{
if(source == NULL)
return false;
if(source->Value == target)
return true;
else if(source->Value > target)
return TreeSearch(source->Left, target);
else
return TreeSearch(source->Right, target);
}
//loop
bool TreeSearch(Tree * source, int target)
{
while(source!=NULL)
{
if(source->Value == target)
return true;
else if(source->value > target)
source = source->Left;
else
source = source->Right;
}
return false;
}
当然,这个方法也有自己的局限性,显然,一旦算法变复杂(而不是示例这样简单的搜索二叉树),代码的可读性会下降得很厉害。在这里有关于递归改写循环的具体描述。
使用尾递归取代普通递归
那么有没有既不损害代码易读性,又能避免栈溢出的方法呢?尾递归是一个方法。
顾名思义,尾递归就是在函数的尾部进行递归。当递归函数对自己的调用出现在函数的最后一行,并且最后一行只有递归函数本身,就意味着之前的局部数据都不再有被保留的意义了。此时编译器会直接舍弃之前的局部数据,用新的入参代替旧入参直接再次运行函数。我们还是以上面的搜索二叉树为例。
//common recursion
bool TreeSearch(Tree * source, int target)
{
if(source == NULL)
return false;
if(source->Value == target)
return true;
else if(source->Value > target)
return TreeSearch(source->Left, target); //3.call here is not right
else
return TreeSearch(source->Right, target); //1.call should be here
}
//tail recursion
bool TreeSearch(Tree * source, int target)
{
if(source == NULL)
return false;
if(source->Value == target)
return true;
else if(source->Value > target)
source = source->Left;
else
source = source->Right;
return TreeSearch(source, target); //2.just call itself
}
需要注意的是,如注释所示,满足尾递归的条件有三点:
- 最后一行是对自身的调用
- 最后一行除了对自身的调用外不得出现别的操作
- 除最后一行外其它地方不能出现对自身的调用
而这个方法也有一个很大的缺点,那就是需要编译器的支持,目前只有C语言支持尾递归的优化。