递归风险的实际开发中应该避免使用递归。 理由主要有两点:
1 .递归调用在深度上是不可预测的,层数太多,不断推栈,可能引起栈溢出崩溃
2 .难以理解
堆栈溢出堆栈溢出异常在程序中经常发生,因为它不足以调用线程堆栈。 windows的默认堆栈大小为1M,如果使用的堆栈空间超过1M,则会报告堆栈溢出异常。
发生原因1、死循环出现死循环。 例如,递归函数没有出口,无论堆栈空间多么大,它总是会溢出。
长函数(Intn ) )。
{
返回函数*函数(n-1 );
}
这是一个没有出口的递归函数,必然引起堆栈溢出。 修正:
长函数(Intn ) )。
{
if(n==1)返回1;
返回函数*函数(n-1 );
}
2、栈确实不足以存储在栈中的主要内容包括局部变量和函数调用的函数环境、函数自变量等。
局部变量,例如:
char buff[1024*1024]
缓冲区是1米。 如果您的堆栈默认也是1M大小,则会发生堆栈溢出。 由于其他内容占用少量的堆栈空间,因此本地变量的可用空间必须小于1米,并且程序在运行主函数之前会跳出堆栈溢出异常。
3、函数调用的层次数太深的情况一般发生在递归调用中
过多的递归调用为什么会引起堆栈溢出呢?
在计算机上,函数调用通过一种名为堆栈的数据结构实现,每当程序执行进入函数调用时,都会向堆栈中添加堆栈帧,每当函数返回时,堆栈就会减少一个堆栈帧。 堆栈的大小不是无限的,因此递归调用的次数过多会导致堆栈溢出。 函数的参数通过堆栈堆栈传递,在调用过程中占用线程的堆栈资源。 递归调用在到达最后一个端点后,函数可以依次退出堆栈。 如果递归调用的层数过多,则使用的堆栈资源可能会超过线程最大值,导致堆栈溢出,从而导致程序异常终止。
不要使用递归场景。 遍历一个目录下的所有文件,包括子目录中的文件。
为了解决包括迭代相似逻辑在内的一些问题,递归是开发人员的明确选择。
当必须使用递归时,如何评估堆栈空间是否足够,以避免堆栈溢出?
评价的想法:
1 .是否确定当前线程的堆栈空间限制?
2 .递归调用n次,分析堆栈n次后堆栈空间的损失是多少?
3 .根据业务估算最大可能的递归调用次数,如果大于或接近堆栈大小,存在堆栈越界风险,需要扩大堆栈空间或限制功能规格。
如果优化堆栈不可用,一种方法是修改程序。
请注意主要由递归调用引起的堆栈溢出。 很多情况下,可以通过算法优化来解决。
1、控制递归深度。 例如,使用动态规划代替递归算法。
2、修改堆栈大小。
尾递归优化尾递归是指函数返回时调用函数本身,并且return语句不能包含表达式。 如果递归调用都出现在函数的末尾,则此递归函数是末尾递归的函数。
尾递归函数的特点是在回归过程中,不用操作。 这个特性很重要。 许多现代编译器利用这个特点自动生成优化的代码。
有些语言强烈提倡尾号递归。 由于编译器优化了代码,所以递归次数的增加不会给函数堆栈带来很大的开销。
末尾优化无论调用多少次都只占用一个堆栈帧,以避免发生堆栈溢出。
递归的优点是逻辑清晰。
可以用循环的方式代替循环递归来改写所有的递归。
斐波那契数列: 1、1、2、3、5、……。
求斐波那契数列的第n项的值
尾递归和循环的执行效率非常高。 但是,末尾递归的递归数大到一定程度时会发生分段错误。 尾递归的函数堆栈开销比常规递归小得多,执行效率相当大。 但是,尾部递归仍有函数栈的开销。
由于尾部递归具有函数堆栈开销,因此其调用次数比循环小很多。
实现不使用递归就不使用递归,如果可以使用末尾递归就使用末尾递归的功能。
//一般递归intfib_normal(intn ) if ) n=2) return 1; ELSEreturnfib_normal(n-1 ) fib_normal ) n-2; //尾部递归intfib_rail(intn,int first,int second ) if(n==1) return first; if(n==2)返回第二次函数; 返回fib _ rail (n-1,second,second first ); } unsignedintfib _ rail _ rec (unsigned intn ) returnfib_rail_rec(n,1,1 ); (//递归intfib_no ) intn ) if ) n=2) return 1; int x=1,y=1,y_tmp=0; for(intI=0; 合2; I ) { y_tmp=y; y=x y; x=y_tmp; }返回y; }堆栈溢出windbg显示堆栈溢出0:072! analyze -v
内容: (.ecxr ) )。
eax=000000 eebx=76 FBC eb8 ecx=00413 fb8 EDX=00417 b 98 ESI=00413 fb8 EDI=0000000
EIP=76ed 83 EB esp=2f 652 ffc ebp=2f 653040 iopl=0nvupeiplnzacpenc
cs=0023 ss=002 BDS=002 bes=002 bfs=0053 GS=002 befl=00010216
ntdll! tlacquiresrwlockexclusive0x b :
76ed83eb 53 push ebx
重置默认值scope
exception_record:(.exr-1 ) )。
扩展地址336076 ed 83 EB (ntdll! tlacquiresrwlockexclusive0x 000000 b )
扩展代码: c 00000软盘(堆栈溢出) )。
ExceptionFlags: 00000000
NumberParameters: 2
Parameter[0]: 00000001
Parameter[1]: 2f652ff8