如何避免栈溢出
不得不说，栈是很简单方便的，内存块的生命周期被栈自动控制，出栈入栈操作在指令集的层面被广泛支持。但在实际编码工作（而不是算法实验）中，栈的弊病也很明显，那就是很容易溢出，这是由于在目前常用的操作系统里，栈作为被定义的一段固定内存空间，是有长度限制的。没有长度限制的栈，我认为是可以存在的，只是会部分牺牲栈的高效性，因为这样要求在每次入栈操作之前检查溢出，避免方法我想是有的，只是会增加平台实现的复杂度。
这里仅仅用来记录避免栈溢出的方法。
用堆变量取代栈变量
当局部变量很大或者很多的时候，极易出现栈溢出，解决方法很简单，用堆来管理它们。
#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语言支持尾递归的优化。
