不得不说，栈是很简单方便的，内存块的生命周期被栈自动控制，出栈入栈操作在指令集的层面被广泛支持。但在实际编码工作（而不是算法实验）中，栈的弊病也很明显，那就是很容易溢出，这是由于在目前常用的操作系统里，栈作为被定义的一段固定内存空间，是有长度限制的。没有长度限制的栈，我认为是可以存在的，只是会部分牺牲栈的高效性，因为这样要求在每次入栈操作之前检查溢出，避免方法我想是有的，只是会增加平台实现的复杂度。

这里仅仅用来记录避免栈溢出的方法。

用堆变量取代栈变量

当局部变量很大或者很多的时候，极易出现栈溢出，解决方法很简单，用堆来管理它们。

#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
}

需要注意的是，如注释所示，满足尾递归的条件有三点：

1. 最后一行是对自身的调用
2. 最后一行除了对自身的调用外不得出现别的操作
3. 除最后一行外其它地方不能出现对自身的调用

而这个方法也有一个很大的缺点，那就是需要编译器的支持，目前只有C语言支持尾递归的优化。