今天看了个文章,是说递归的。
大概代码如下:
void test(int n){
if (n<1000000)
{
test(n+1);
}
}
int main()
{
test(1);
return 0;
}
运行报错:Stack overflow 堆栈溢出。
为什么会溢出内,因为在内存开辟的一块栈的空间是有限的(具体内存开辟了多少,如何开辟还在研究);
然后程序执时会将函数压入栈内,程序没有返回或结束时,不会从栈内弹出来,也就是说会压入栈内1000000次函数执行体。这样就撑爆了栈,所以会报错。
回到题目:
为什么斐波那契递归第50项,要计算2^49次方,不会栈溢出呢?
用计算器计算一下2^49次方等于:1125899906842624,这么多次栈没有溢出。
而开始的 1000000 次就溢出的?
为什么?
递归斐波那契第50项的值,就要知道49和48的值相加。
递归斐波那契第49项的值,就要知道48和47的值相加。
递归斐波那契第48项的值,就要知道47和46的值相加。
.......
50 2^0
49 + 48 2^1
48 + 47 47 + 46 2^2
...... ...... 2^n
最后2^49
那么他是这样层序遍历的吗?
不是,他是通过前序遍历,即:
求第50项的斐波那契数:
Fei(50-1) + Fei(50-2),当执行到Fei(50-1)时,又进入递归了(Fei(50-2)没来得及执行呢),就是走到了上图左子树49的位置,
Fei(49-1) + Fei(49-2),当执行到Fei(49-1)时,又进入递归(Fei(49-2)没来得及执行呢),就是走到了上图左子树48的位置,
Fei(48-1) + Fei(48-2),当执行到Fei(48-1)时,又进入递归(Fei(48-2)没来得及执行呢),就是走到了上图左子树47的位置(上图写的....没都写出来)
.....
直到最后
Fei(2-1) + Fei(2-2),当执行到Fei(2-1)时,又进入递归(Fei(2-2)没来得及执行呢),就是走到了上图左子树1的位置,
然后条件成立了,就返回了1。这时就开始回溯了,回溯的同时就是出栈了,释放栈。
所以左子树遍历40次就释放栈了。不会将几千万都压入栈中再释放的。
所以就不会栈溢出了!
如果没懂就留言吧。后期博客再完善一下,配图或动画详细讲解。这都是手写的过程,不那么明确!