C++算法之递归和堆栈的代码

开发过程中，把开发过程较好的代码段收藏起来，如下资料是关于C++算法之递归和堆栈的代码，希望对码农们有些用。

函数A    ^ 

函数B    |    (地址递减) 

函数C    | 

如果是递归函数呢，举一个简单的递归函数为例：

int iterate(int value) 

{ 

    if(value == 1) 

        return 1; 

    return value + iterate(value -1); 

} 

下面我们使用一个函数进行调用，看看会发生什么情况？

void process() 

{ 

    int value = iterate(6); 

} 

看看此时内存堆栈是什么样的？

iterate(int 1) line 96 

iterate(int 2) line 97 + 12 bytes 

iterate(int 3) line 97 + 12 bytes 

iterate(int 4) line 97 + 12 bytes 

iterate(int 5) line 97 + 12 bytes 

iterate(int 6) line 97 + 12 bytes 

process() line 102 + 7 bytes 

main() line 108 

mainCRTStartup() line 206 + 25 bytes 

KERNEL32! 7c817067() 

大家也看到了上面的代码，递归函数和普通的函数也没有什么差别。除了自己调用本身之外，他就是一个普通的函数。那么这个函数递归到什么时候返回呢？这就是递归函数的关键了。我们看到iterate函数到1就停止了，所以上面的堆栈在（value==1）即return。所以一个递归函数最关键的部分就是两点：（1）递归策略；（2）函数出口。看到这里，大家可能感到递归函数不过如此，事实上也是这样。但是，还有一点大家需要牢记在心，递归的深度是我们必须考虑的一个问题。只有递归深度在一个可控的范围内，那么整个递归过程都是可控的。那什么时候不可控呢？那就是递归深度超过了一定的数字？这个数字和具体的线程堆栈长度有关？等到堆栈溢出了，那么获得的数据已经失去了真实性，所以也就没有意义了。我们把上面的问题推广一下，如何用自己定义的堆栈模拟上面的递归调用呢？这样既能满足递归的属性，又能确保函数深度可控。大家可以先写一下自己的方案，下面只是我个人的一个思路。

int iterate(int value) 

{ 

    int count = 0; 

    int number  =0; 

    push(value); 

    while(-1 != (number = pop())) 

    { 

        if(1 != number) 

            push(number -1); 

        count += number; 

    } 

    return count; 

}