首页 > 其他分享 >递归调用和栈溢出

递归调用和栈溢出

时间:2024-02-20 14:44:06浏览次数:20  
标签:调用 递归 sum add num 溢出

一、简介

       栈溢出:Stack Overflow。对于每个程序,栈能使用的内存是有限的,一般是1M-8M,在程序编译时就已经决定了,程序运行期间不能改变。如果程序使用的栈内存超出最大值,就会发生栈溢出错误,程序会崩溃。

二、栈溢出的原因

       因为每调用一个方法就会在栈上创建一个栈帧,方法调用结束后就会弹出该栈帧,而栈的大小不是无限的,所以递归调用次数过多的话就会导致溢出。而递归调用的特点是每递归一次,就要创建一个新的栈帧,而且还要保留之前的环境(栈帧),直到遇到结束条件。所以递归调用一定要明确好结束条件,不要出现死循环,而且避免栈太深。

三、解决办法

  1. 不使用递归,用循环替代。缺点是代码逻辑不够清晰。
  2. 限制递归次数。
  3. 使用尾递归。尾递归指在方法返回时,只调用自己本身,且不能包含表达式。编译器或解释器把尾递归做优化,使递归方法无论调用多少次,都只会占用一个栈帧,所以不会出现栈溢出。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

相关文章

  • Oracle递归授权view底层依赖表查询权限存储过程
    createorreplaceproceduresys.grant_view_base_table_access(p_accessownerVARCHAR2,p_vownerVARCHAR2,p_vnameVARCHAR2)--RETURNnumberasv_accessownerVARCHAR2(200):=trim(upper(p_accessowner));v_ownerVARCHAR2(200):=trim(upper(p_vowner));v_nameVARCHAR......
  • C#调用HTTPS
    1、C#.NETCore使用HttpClient时忽略HTTPS证书最近项目遇到HttpClient请求代理时报SSL认证失败,解决方案记录 varhandler=newHttpClientHandler();handler.ServerCertificateCustomValidationCallback=delegate{returntrue;};varclient=newHttpClient(handler); ......
  • 洛谷题单指南-递推与递归-P3612 [USACO17JAN] Secret Cow Code S
    原题链接:https://www.luogu.com.cn/problem/P3612题意解读:字符串加长的时候,是先把最后一个字符接上,再拼接其余字符,注意不是翻转,要找第n个字符,就要看字符串加长几次后长度能超过n,然后在加长后的字符串中找第n个字符。解题思路:如果直接通过模拟法,字符串长度太长,且要找的第n个数......
  • python调用qq邮箱发送邮件
    代码如下,需要qq邮箱开启授权码importsmtplibfromemail.mime.textimportMIMETextfromemail.headerimportHeadermessage=MIMEText('邮件内容')#邮件内容message['From']=Header('[email protected]')#邮件发送者名字message['To']=Header(&#......
  • 递归与循环比较
    下面通过几个例子,对递归与循环进行比较。递归1#include<iostream>usingnamespacestd;voiddfs(intn){ if(n==0)return; cout<<n<<”“;dfs(n-1);}intmain(){ dfs(10000);dfs(75000);//运行RE}说明递归对内存有一定的消耗对应的循环......
  • 深入理解 Java 方法重载与递归应用
    Java方法重载方法重载允许在同一个类中定义多个具有相同名称的方法,但参数列表必须不同。语法:returnTypemethodName(parameter1,parameter2,...,parameterN){//方法体}示例:publicclassMain{//重载add方法,支持int和double类型参数staticinta......
  • 洛谷题单指南-递推与递归-P1990 覆盖墙壁
    原题链接:https://www.luogu.com.cn/problem/P1990题意解读:用两种可旋转的形状铺满N*2的区域,求方案数,可以使用递推。解题思路:步骤1、设f[i]表示铺满i*2的区域的方案数根据要求,i*2区域最后一列有4种可能的铺法:如果采用图1铺法,则有f[i]=f[i-1]如果采用图2铺法,则有f[i]=f......
  • Feign动态定义调用serverName与path
    Feign动态定义调用serverName与path查看原文方案一(DynamicProcessFeign)1.定义FeignClient工厂@ComponentpublicclassDynamicProcessFeign<T>{/***缓存feignClient,提高客户端性能*/privatestaticMap<String,Object>processMap=newHashMap<>......
  • js判断单行文本是否有溢出
    需求是的单行文本溢出的时候显示展开按钮,需要判断文本是否有溢出       不知道还有没更好的方法,讲究用了,233......
  • Json 递归解析算法笔记
    需求:最近需要处理包含多层的Json字符串解析的问题,比如需要将所有的键值对的值替换,或者将键值对的键替换,包括嵌套对象里面的。大致知道需要使用递归来操作,先记录大致步骤吧。思路:写好一个固定的函数专门处理替换步骤;在这个函数内分别判断值是数组,还是对象,还是值(值走上面的递......