深高北第18次课——递归
2025-04-23 17:07:48
发布于:广东
递归
定义
递归(英语:Recursion),在数学和计算机科学中是指在函数的定义中使用函数自身的方法,在计算机科学中还额外指一种通过重复将问题分解为同类的子问题而解决问题的方法。
引入
要理解递归,就得先理解什么是递归。
递归的基本思想是某个函数直接或者间接地调用自身,这样原问题的求解就转换为了许多性质相同但是规模更小的子问题。求解时只需要关注如何把原问题划分成符合条件的子问题,而不需要过分关注这个子问题是如何被解决的。
以下是一些有助于理解递归的例子:
-
如何给一堆数字排序?答:分成两半,先排左半边再排右半边,最后合并就行了,至于怎么排左边和右边,请重新阅读这句话。
-
你今年几岁?答:去年的岁数加一岁,1999 年我出生。
-
递归代码最重要的两个特征:结束条件和自我调用。自我调用是在解决子问题,而结束条件定义了最简子问题的答案。
int func(传入数值) {
if (终止条件) return 最小子问题解;
return func(缩小规模);
}
为什么要写递归
-
结构清晰,可读性强。
-
练习分析问题的结构。当发现问题可以被分解成相同结构的小问题时,递归写多了就能敏锐发现这个特点,进而高效解决问题。
递归的缺点
在程序执行中,递归是利用堆栈来实现的。每当进入一个函数调用,栈就会增加一层栈帧,每次函数返回,栈就会减少一层栈帧。而栈不是无限大的,当递归层数过多时,就会造成 栈溢出 的后果。
什么是记忆化递归
记忆化递归(Memoization)是一种优化递归算法的技术,通过存储已经计算过的结果来避免重复计算,从而显著提高递归算法的效率。
基本思想
- 缓存计算结果:将已经计算过的子问题的结果存储起来
- 检查缓存:在计算新问题前先检查是否已有存储结果
- 避免重复计算:如果存储中存在结果,直接使用而不重新计算
实现步骤
- 定义一个数组来存储计算结果
- 在递归函数开始时检查是否已有存储的结果
- 如果有则直接返回存储的结果
- 如果没有则进行计算,并在返回前存储结果
这里空空如也
有帮助,赞一个