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

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

用堆变量取代栈变量

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

#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_1heap_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语言支持尾递归的优化。

发表评论

电子邮件地址不会被公开。 必填项已用*标注