函数递归调用太深爆栈探索

2024-02-07 23:18

本文主要是介绍函数递归调用太深爆栈探索,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

一、常见的递归调用有斐波那契数列,1,1,2,3,5,8,13…
递归的缺点是递归的层数不能太多,会爆栈,下面从底层的角度讲述递归调用的原理。
1、链接逻辑
每个程序都有头文件,这些头文件包含一系列的库函数,当我们链接程序时这些目标模块就会装配成一个完整的模块装入。
每个模块都有自己的逻辑地址,链接完成后形成自己的从0开始的逻辑地址如图如图,各函数模块链接地址
2、装载
怎么将程序装入内存?程序一开始在磁盘上,还需要装入主存即内存才能运行。内存中低地址留给系统使用,高地址即用户区,是将原地址直接装入内存,相对地址是不变的
插入内存
计算机如何确定程序执行的下一条指令?是通过计算机中一个叫程序计数器(program Counter)的部件来存放程序要执行的下一条指令的。Cpu在程序计数器中取到下一条指令后就到内存中取这条指令,取到之后到Cpu中解析执行。如此循环往复,程序得以执行。
3、函数调用
函数调用,函数原本在主线上执行,遇到调用指令暂时到别的模块执行,执行结束后再回到主模块的过程
为什么可以跳到别的模块执行?因为函数的调用指令指明了模块的首地址,执行过程先将指令传给程序计数器(PC),此时中断了程序的顺序执行,指令之后的其他指令都被入在了内存中的一块专门实现函数调用的栈区,当程序调用指令执行到返回指令时,再出栈,将栈顶元素传给程序计数器(PC),程序因此又回到了主模块。
为什么要入栈?函数调用时入栈保护的不仅仅是指令地址,还有一些变量数据和局部变量,否则会丢失
4、递归函数中的调用
区别就是递归函数的调用就是自己调用自己。

int fibonacci(int n)
{
if(n==1||n==2) //假设本条指令的地址为10000return 1; //假设本条指令的地址为10001
int a=fibonacci(n-2); //假设本条指令的地址为10002
int b=fibonacci(n-1); //假设本条指令的地址为10003
int c=a+b; //假设本条指令的地址为10004
return c; //假设本条指令的地址为10005
}

假设主函数指令地址为15000,下一个指令是15001,从主函数到斐波那契数列的计算第五项,公式及示意图为:

f(5)=f(3)+f(4)=[f(1)+f(2)]+[f(2)+f(3)]=[f(1)+f(2)]+[f(2)+[f(1)+f(2)]]

在这里插入图片描述
循环往复,一直到指令15001出栈给程序计数器,回到主函数。计算完成
5、为什么爆栈?
内存中特地用来存放函数调用的栈区内存是有限的,如果递归太深,就会出现只入栈不出栈的情况。应谨慎使用
6、实际使用中像斐波那契的解法,使用递归会出现:1产生大量重复计算,2n过大时容易爆栈。可以使用动态规划解法(DP)

int fibonacci(int n)
{f[1]=1,f[2]=1;for(int i=3;i<=n;i++){f[i]=f[i-2]+f[i-1];}return f[n];
}

为什么说有重复计算,因为:
f3 = f1+f2
f5 = f3+f4
f4 = f2+f3
so f5=(f1+f2)+(f2+f3)
有两个f2,就相当于要计算两次f2
不如开一个比较大的数组,用循环来做。
(纯属笔记学习,抄自文章https://mp.weixin.qq.com/s/Re_0uZnJ9SikKoPG_bdSWQ)

这篇关于函数递归调用太深爆栈探索的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/689215

相关文章

Rust中的BoxT之堆上的数据与递归类型详解

《Rust中的BoxT之堆上的数据与递归类型详解》本文介绍了Rust中的BoxT类型,包括其在堆与栈之间的内存分配,性能优势,以及如何利用BoxT来实现递归类型和处理大小未知类型,通过BoxT,Rus... 目录1. Box<T> 的基础知识1.1 堆与栈的分工1.2 性能优势2.1 递归类型的问题2.2

Python调用Orator ORM进行数据库操作

《Python调用OratorORM进行数据库操作》OratorORM是一个功能丰富且灵活的PythonORM库,旨在简化数据库操作,它支持多种数据库并提供了简洁且直观的API,下面我们就... 目录Orator ORM 主要特点安装使用示例总结Orator ORM 是一个功能丰富且灵活的 python O

Java调用DeepSeek API的最佳实践及详细代码示例

《Java调用DeepSeekAPI的最佳实践及详细代码示例》:本文主要介绍如何使用Java调用DeepSeekAPI,包括获取API密钥、添加HTTP客户端依赖、创建HTTP请求、处理响应、... 目录1. 获取API密钥2. 添加HTTP客户端依赖3. 创建HTTP请求4. 处理响应5. 错误处理6.

pip install jupyterlab失败的原因问题及探索

《pipinstalljupyterlab失败的原因问题及探索》在学习Yolo模型时,尝试安装JupyterLab但遇到错误,错误提示缺少Rust和Cargo编译环境,因为pywinpty包需要它... 目录背景问题解决方案总结背景最近在学习Yolo模型,然后其中要下载jupyter(有点LSVmu像一个

Python itertools中accumulate函数用法及使用运用详细讲解

《Pythonitertools中accumulate函数用法及使用运用详细讲解》:本文主要介绍Python的itertools库中的accumulate函数,该函数可以计算累积和或通过指定函数... 目录1.1前言:1.2定义:1.3衍生用法:1.3Leetcode的实际运用:总结 1.1前言:本文将详

Deepseek R1模型本地化部署+API接口调用详细教程(释放AI生产力)

《DeepseekR1模型本地化部署+API接口调用详细教程(释放AI生产力)》本文介绍了本地部署DeepSeekR1模型和通过API调用将其集成到VSCode中的过程,作者详细步骤展示了如何下载和... 目录前言一、deepseek R1模型与chatGPT o1系列模型对比二、本地部署步骤1.安装oll

一分钟带你上手Python调用DeepSeek的API

《一分钟带你上手Python调用DeepSeek的API》最近DeepSeek非常火,作为一枚对前言技术非常关注的程序员来说,自然都想对接DeepSeek的API来体验一把,下面小编就来为大家介绍一下... 目录前言免费体验API-Key申请首次调用API基本概念最小单元推理模型智能体自定义界面总结前言最

轻松上手MYSQL之JSON函数实现高效数据查询与操作

《轻松上手MYSQL之JSON函数实现高效数据查询与操作》:本文主要介绍轻松上手MYSQL之JSON函数实现高效数据查询与操作的相关资料,MySQL提供了多个JSON函数,用于处理和查询JSON数... 目录一、jsON_EXTRACT 提取指定数据二、JSON_UNQUOTE 取消双引号三、JSON_KE

MySQL数据库函数之JSON_EXTRACT示例代码

《MySQL数据库函数之JSON_EXTRACT示例代码》:本文主要介绍MySQL数据库函数之JSON_EXTRACT的相关资料,JSON_EXTRACT()函数用于从JSON文档中提取值,支持对... 目录前言基本语法路径表达式示例示例 1: 提取简单值示例 2: 提取嵌套值示例 3: 提取数组中的值注意

JAVA调用Deepseek的api完成基本对话简单代码示例

《JAVA调用Deepseek的api完成基本对话简单代码示例》:本文主要介绍JAVA调用Deepseek的api完成基本对话的相关资料,文中详细讲解了如何获取DeepSeekAPI密钥、添加H... 获取API密钥首先,从DeepSeek平台获取API密钥,用于身份验证。添加HTTP客户端依赖使用Jav