递归详解
一、入门的阶乘
提到递归,我猜大多数同学第一印象就是:f(n) = f(n-1) * n
阶乘。所以咱们今天就先从最基础的阶乘来入手。
阶乘是一个非常 线性 的问题。用我们的大脑来 构建调用栈 也很容易和清晰。函数调用单项的一层层 递
下去,然后通过最终的return条件,再一层层的return回去( 归 )。
递归实现的阶乘很好理解,那咱们就趁热打铁总结一下递归的特点:
- 1. 一个问题的解可以分解为多个相同类型子问题
- 咱们阶乘中
f(n-1) * n
就是抽象出来的子问题。而且无论存在多少种入参的情况,子问题解题思路是一致的。
- 咱们阶乘中
- 2. 存在递归终止条件
- 子问题可能有很多,如果无限重复下去,那么就是栈溢出了,所以需要有终止条件。
二、难度进阶
有了阶乘的入门,咱们来稍稍提升一些难度:假如这里有 n 个台阶,每次你可以跨 1 个台阶或者 2 个台阶,请问走这 n 个台阶有多少种走法?
PS:当年我看到这个题目是非常蒙蔽的,每一步都有两种选择,很难搞哇。
因为本篇章的主角是递归,所以咱们依旧用递归的思路去解题。咱先来思考一下,这题是不是比阶乘难?答案是肯定的。
那它比阶乘难在哪呢?难在 它不再是线性的问题! 每一步都有两个不同的选择。
咱不管这么多,先套递归的特点:1、找子问题,构建合适的递归公式;2、找到合适的终止条件。
很多教程都是先找子问题构建递归公式,但是这次咱们反过来 先找终止条件 。
1、找终止条件
既然是找终止条件,那咱们就得明确题目中的终止是啥,就是走完台阶,最终走完台阶的方式只有两种:要么是跨 1 个台阶走完,要么是跨 2 个台阶走完。
好,那咱们的终止条件其实就出来了,假设n表示当前还剩多少阶台阶,返回值表示有几种走法:
if(n = 1) return 1
;此时只有一种走法;if(n = 2) return 2
;此时有两种走法。
咱们找到了终止条件,这里停下来咱们想一个问题:咱们终止条件找的是如果只剩1个 / 2个台阶时的走法。
那么我们把1/2这两个实际的参数抽象一下,是不是可以转化为我们再找n - 1
个台阶的走法和n - 2
个台阶的走法。(如果此时`n =
3`,就得到了我们终止条件的答案)
2、构建合适的递归公式
通过上边找终止条件的过程,抽象一下就会发现:我们本质就是在寻找n - 1
个台阶的走法和n - 2
个台阶的走法一共有多少种。
所以子问题就出来了:基于当前台阶数,走一阶有多少种走法 + 走两阶有多少种走法。(换成伪码就是f(n) = f(n-1)+f(n-2)
)
注意(这句话一定要看) :这里千万不要陷进去,也就是 不要基于当前去思考:有多少种走法! 因为
这不是当前子问题该考虑的事情,这个问题的答案会在归的过程由前一个子问题回答 。
如果非要思考,也没关系。我贴张图帮助你去思考:
image.png
我着重圈了两个地方:
一个是不满足终止条件“递的过程”
该行为会按照我们的递归公式,逐步递出全部可能性,也就是为什么想告知大家不要陷进去。
对于咱们这个问题,如果想要展开递的过程,那么就会像二叉树一样不断延展开来,然而这个展开的过程对于我们来说没有任何意义,因为这本身就是重复的过程,
这种事不应该是我们人脑该做的 。
另一个是满足终止条件“归的过程”
归的过程说白了就是:某一层子问题找到了答案,逐层往上告知的过程。
这一步其实就是解释了,递的过程为什么不要钻牛角尖,去基于当前去想到底有多少种走法。因为一旦想要知道答案,就要展开所有可能。
然而我们的每一层的答案都会由下一层子问题在归的过程中解答。
解题代码
所以这个题目的代码就很简单了:
int f(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
return f(n-1) + f(n-2);
}
三、递归的优缺点
硬说递归的有点,个人感觉那就是代码量少...但是同样也是它的缺点,代码越简单理解成本就越高。当然这个问题不痛不痒。
这一Part咱们主要说一下递归比较关键两个问题:
1、避免堆栈溢出
这一点还是比较好理解的,因为一旦终止条件有问题,那么无限递归就会造成栈溢出。
Exception in thread "main" java.lang.StackOverflowError
2、重复执行
这个问题算是递归中比较重点的缺点。借助下面这张图,我圈起来的f(4)
、f(3)
,很明显看到它们被重复执行了很多遍。
当然解决起来也很简单,那就是 加缓存 。每次执行的时候先去缓存里读,没有的话再执行递的过程。
四、非递归实现
这里有一个非递归的实现。代码是这样的:
int f(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
int ret = 0;
int pre = 2;
int prepre = 1;
for (int i = 3; i <= n; ++i) {
ret = pre + prepre;
prepre = pre;
pre = ret;
}
return ret;
}
相关文章
- 【技术种草】cdn+轻量服务器+hugo=让博客“云原生”一下
- CLB运维&运营最佳实践 ---访问日志大洞察
- vnc方式登陆服务器
- 轻松学排序算法:眼睛直观感受几种常用排序算法
- 十二个经典的大数据项目
- 为什么使用 CDN 内容分发网络?
- 大数据——大数据默认端口号列表
- Weld 1.1.5.Final,JSR-299 的框架
- JavaFX 2012:彻底开源
- 提升as3程序性能的十大要点
- 通过凸面几何学进行独立于边际的在线多类学习
- 利用行动影响的规律性和部分已知的模型进行离线强化学习
- ModelLight:基于模型的交通信号控制的元强化学习
- 浅谈Visual Source Safe项目分支
- 基于先验知识的递归卡尔曼滤波的代理人联合状态和输入估计
- 结合网络结构和非线性恢复来提高声誉评估的性能
- 最佳实践丨云开发CloudBase多环境管理实践
- TimeVAE:用于生成多变量时间序列的变异自动编码器
- 具有线性阈值激活的神经网络:结构和算法
- 内网渗透之横向移动 -- 从域外向域内进行密码喷洒攻击