一、简介
栈溢出:Stack Overflow。对于每个程序,栈能使用的内存是有限的,一般是1M-8M,在程序编译时就已经决定了,程序运行期间不能改变。如果程序使用的栈内存超出最大值,就会发生栈溢出错误,程序会崩溃。
二、栈溢出的原因
因为每调用一个方法就会在栈上创建一个栈帧,方法调用结束后就会弹出该栈帧,而栈的大小不是无限的,所以递归调用次数过多的话就会导致溢出。而递归调用的特点是每递归一次,就要创建一个新的栈帧,而且还要保留之前的环境(栈帧),直到遇到结束条件。所以递归调用一定要明确好结束条件,不要出现死循环,而且避免栈太深。
三、解决办法
- 不使用递归,用循环替代。缺点是代码逻辑不够清晰。
- 限制递归次数。
- 使用尾递归。尾递归指在方法返回时,只调用自己本身,且不能包含表达式。编译器或解释器把尾递归做优化,使递归方法无论调用多少次,都只会占用一个栈帧,所以不会出现栈溢出。Tips:Java没有尾递归优化。
四、尾递归例子
一般的递归code:
fuction add(num){ if(num == 1) return 1; return num + add(num - 1); }
尾递归code:
/// /// 尾递归:函数结束只能调用自身 /// function add(num,sum){ if(num == 1) return sum + num; return add(num - 1,sum + num); }
分析:一般递归中,add(num)需要在得到 add(num - 1)结果之后才会计算它自己的返回值,所以理论上,在add(num - 1)返回之前,add(num)不能返回结果,所以add(num)在栈上额数据必须保留,知道add(num - 1)先返回,而栈的大小不是无限的,windows下为1M。所以可能出现栈溢出。
尾递归中,它不必等拿到 add(num - 1,sum + num)的返回值才计算自己的结果,完全可以等于add(num - 1,sum + num)的返回值。理论上 add(num,sum) 在调用 add(num - 1,sum + num)之前,完全可以先销毁自己的栈帧。这也就是为何尾递归在得到编译器的帮助下,完全可以避免栈溢出的原因。每个函数在调用下一个函数之前,都能做法哦先把当前自己的栈帧释放。尾递归的调用链上可以做到只有一个函数在使用栈,因此可以无限调用。
Tips:尾递归自己并不会销毁栈帧,而是依赖于程序有没有编译器的优化。如果不开优化,依然可能出现栈溢出。所以主要取决于编译器。
标签:调用,递归,sum,add,num,溢出 From: https://www.cnblogs.com/xiaobaicai12138/p/18022959