【基础篇】8 # 递归:如何避免出现堆栈溢出呢?

简介: 【基础篇】8 # 递归:如何避免出现堆栈溢出呢?

说明

【数据结构与算法之美】专栏学习笔记



什么是递归?


递归是一种应用非常广泛的算法(或者编程技巧),比如 DFS 深度优先搜索、前中后序二叉树遍历等等都是用到了递归。


方法或函数调用自身的方式称为递归调用,调用称为递,返回称为归。


递归问题基本都可以用递推公式来表示,比如:

f(1) = 1;
f(n) = f(n-1) + 1; // n 是大于 1 的正整数



递归需要满足的三个条件

  1. 一个问题的解可以分解为几个子问题的解
  2. 分解之后的子问题求解思路一样
  3. 存在递归终止条件


如何编写递归代码?

写递归代码的关键就是找到如何将大问题分解为小问题的规律,并且基于此写出递推公式,然后再推敲终止条件,最后将递推公式和终止条件翻译成代码。


编写递归代码的关键是,只要遇到递归,我们就把它抽象成一个递推公式,不用想一层层的调用关系,不要试图用人脑去分解递归的每个步骤。



如何避免出现堆栈溢出呢?


为什么递归代码容易造成堆栈溢出呢?

函数调用会使用栈来保存临时变量。每调用一个函数,都会将临时变量封装为栈帧压入内存栈,等函数执行完成返回时,才出栈。系统栈或者虚拟机栈空间一般都不大。如果递归求解的数据规模很大,调用层次很深,一直压入栈,就会有堆栈溢出的风险。


如何预防堆栈溢出呢?

可以通过在代码中限制递归调用的最大深度的方式来解决。递归调用超过一定深度之后,不继续往下再递归,直接返回报错。


如何避免重复计算呢?

可以通过一个数据结构(比如散列表)来保存已经求解过的 f(k)。当递归调用到 f(k) 时,先看下是否已经求解过;如果是,则直接从散列表中取值返回,不需要重复计算。



怎么将递归代码改写为非递归代码?


递归代码优点:


  • 表达力很强
  • 写起来非常简洁

递归代码缺点:


  • 空间复杂度高
  • 有堆栈溢出的风险
  • 存在重复计算
  • 过多的函数调用会耗时较多



笼统的讲,所有的递归代码都可以改写为迭代循环的非递归写法。抽象出递推公式、初始值和边界条件,然后用迭代循环实现。



调试递归


  1. 打印日志发现,递归值。
  2. 结合条件断点进行调试。






目录
相关文章
|
机器学习/深度学习 监控 算法
线性与非线性数据降维方法汇总(Python代码实现)
线性与非线性数据降维方法汇总(Python代码实现)
线性与非线性数据降维方法汇总(Python代码实现)
|
12月前
|
测试技术 Python
自动化测试项目学习笔记(四):Pytest介绍和使用
本文是关于自动化测试框架Pytest的介绍和使用。Pytest是一个功能丰富的Python测试工具,支持参数化、多种测试类型,并拥有众多第三方插件。文章讲解了Pytest的编写规则、命令行参数、执行测试、参数化处理以及如何使用fixture实现测试用例间的调用。此外,还提供了pytest.ini配置文件示例。
533 2
|
前端开发 JavaScript 微服务
微前端架构模式
微前端架构模式
|
算法 Python
逆袭之路!用 Python 玩转图的 DFS 与 BFS,让数据结构难题无处遁形
【7月更文挑战第12天】图的遍历利器:DFS 和 BFS。Python 中,图可表示为邻接表或矩阵。DFS 沿路径深入,回溯时遍历所有可达顶点,适合找路径和环。BFS 层次遍历,先近后远,解决最短路径问题。两者在迷宫、网络路由等场景各显神通。通过练习,掌握这些算法,图处理将游刃有余。
163 3
The authenticity of host ‘gitee.com (180.76.198.77)‘ can‘t be established.ED25519 key fingerprint i
The authenticity of host ‘gitee.com (180.76.198.77)‘ can‘t be established.ED25519 key fingerprint i
|
NoSQL Java Redis
Redis 从入门到精通之Redis数据排序
Redis支持对List、Set和Sorted Set元素进行排序,排序命令是`SORT`。`SORT`命令可以根据指定的排序规则对列表、集合或有序集合的元素进行排序,并返回排序后的元素列表或子集。使用Jedis和RedisTemplate分别实现Redis列表、集合和有序集合排序操作的示例代码
1653 101
|
JavaScript 前端开发 Java
利用bladex+avue实现下拉数据源展示
利用bladex+avue实现下拉数据源展示
|
JavaScript
Uncaught runtime errors: × ERROR Avoided redundant navigation to current location: “/xxx“.
Uncaught runtime errors: × ERROR Avoided redundant navigation to current location: “/xxx“.
413 0
|
Web App开发 网络协议 安全
Kali Linux 网络扫描秘籍 第七章 Web 应用扫描(一)
第七章 Web 应用扫描(一) 作者:Justin Hutchens 译者:飞龙 协议:CC BY-NC-SA 4.0 7.1 使用 Nikto 扫描 Web 应用 Nikto 是 Kali 中的命令行工具,用于评估 Web 应用的已知安全问题。
2225 0
|
关系型数据库 MySQL Spring
mysql 默认八小时空闲自动断开连接
MySQL 的默认设置下,当一个连接的空闲时间超过8小时后,MySQL 就会断开该连接,而 c3p0 连接池则以为该被断开的连接依然有效。在这种情况下,如果客户端代码向 c3p0 连接池请求连接的话,连接池就会把已经失效的连接返回给客户端,客户端在使用该失效连接的时候即抛出异常 解决这个问题的办法有三种: 1. 增加 MySQL 的 wait_timeout 属性的值。 修改 /et
3355 0