提到递归,我猜大多数同学第一印象就是:f(n) = f(n-1) * n
阶乘。所以咱们今天就先从最基础的阶乘来入手。
阶乘是一个非常 线性 的问题。用我们的大脑来 构建调用栈 也很容易和清晰。函数调用单项的一层层 递
下去,然后通过最终的return条件,再一层层的return回去( 归 )。
递归实现的阶乘很好理解,那咱们就趁热打铁总结一下递归的特点:
f(n-1) * n
就是抽象出来的子问题。而且无论存在多少种入参的情况,子问题解题思路是一致的。有了阶乘的入门,咱们来稍稍提升一些难度:假如这里有 n 个台阶,每次你可以跨 1 个台阶或者 2 个台阶,请问走这 n 个台阶有多少种走法?
PS:当年我看到这个题目是非常蒙蔽的,每一步都有两种选择,很难搞哇。
因为本篇章的主角是递归,所以咱们依旧用递归的思路去解题。咱先来思考一下,这题是不是比阶乘难?答案是肯定的。
那它比阶乘难在哪呢?难在 它不再是线性的问题! 每一步都有两个不同的选择。
咱不管这么多,先套递归的特点:1、找子问题,构建合适的递归公式;2、找到合适的终止条件。
很多教程都是先找子问题构建递归公式,但是这次咱们反过来 先找终止条件 。
既然是找终止条件,那咱们就得明确题目中的终止是啥,就是走完台阶,最终走完台阶的方式只有两种:要么是跨 1 个台阶走完,要么是跨 2 个台阶走完。
好,那咱们的终止条件其实就出来了,假设n表示当前还剩多少阶台阶,返回值表示有几种走法:
if(n = 1) return 1
;此时只有一种走法;if(n = 2) return 2
;此时有两种走法。咱们找到了终止条件,这里停下来咱们想一个问题:咱们终止条件找的是如果只剩1个 / 2个台阶时的走法。
那么我们把1/2这两个实际的参数抽象一下,是不是可以转化为我们再找n - 1
个台阶的走法和n - 2
个台阶的走法。(如果此时`n =
3`,就得到了我们终止条件的答案)
通过上边找终止条件的过程,抽象一下就会发现:我们本质就是在寻找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咱们主要说一下递归比较关键两个问题:
这一点还是比较好理解的,因为一旦终止条件有问题,那么无限递归就会造成栈溢出。
Exception in thread "main" java.lang.StackOverflowError
这个问题算是递归中比较重点的缺点。借助下面这张图,我圈起来的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;
}
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。