算法学习之递归和堆栈
时间:2015-06-17 21:45:56
收藏:0
阅读:247
【摘要】当执行完被调用函数,返回外部程序前,系统首先要恢复外部程序的变量当前值,然后返回外部程序的返回地址。递归函数被外部程序调用时,系统要做的工作和非递归函数被调用时系统要做的工作在形式上类同,只是实现方法不同而已。那递归代码和运行时的堆栈有什么关系呢?我们先看一下下面这几幅图,关于递归代码和运行时堆栈关系。
我们可以看一下普通函数的调用怎么样的。试想如果函数A调用了函数B,函数B又调用了函数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()
看到这里,大家可能感到递归函数不过如此,事实上也是这样。但是,还有一点大家需要牢记在心,递归的深度是我们必须考虑的一个问题。只有递归深度在一个可控的范围内,那么整个递归过程都是可控的。那什么时候不可控呢?那就是递归深度超过了一定的数字?这个数字和具体的线程堆栈长度有关?等到堆栈溢出了,那么获得的数据已经失去了真实性,所以也就没有意义了。
我们把上面的问题推广一下,如何用自己定义的堆栈模拟上面的递归调用呢?这样既能满足递归的属性,又能确保函数深度可控。
- 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;
- }
原文:http://blog.csdn.net/xy010902100449/article/details/46535555
评论(0)