如何做导购网站,网站使用说明书模板,2h1g做视频网站,菏泽做网站设计前言递归是算法中一种非常重要的思想#xff0c;应用也很广#xff0c;小到阶乘,再在工作中用到的比如统计文件夹大小#xff0c;大到 Google 的 PageRank 算法都能看到#xff0c;也是面试官很喜欢的考点最近看了不少递归的文章#xff0c;收获不小#xff0c;不过我发现… 前言递归是算法中一种非常重要的思想应用也很广小到阶乘,再在工作中用到的比如统计文件夹大小大到 Google 的 PageRank 算法都能看到也是面试官很喜欢的考点最近看了不少递归的文章收获不小不过我发现大部分网上的讲递归的文章都不太全面主要的问题在于解题后大部分都没有给出相应的时间/空间复杂度而时间/空间复杂度是算法的重要考量!递归算法的时间复杂度普遍比较难需要用到归纳法等换句话说如果能解决递归的算法复杂度其他算法题题的时间复杂度也基本不在话下。另外递归算法的时间复杂度不少是不能接受的如果发现算出的时间复杂度过大则需要转换思路看下是否有更好的解法 这才是根本目的不要为了递归而递归本文试图从以下几个方面来讲解递归什么是递归递归算法通用解决思路实战演练从初级到高阶力争让大家对递归的认知能上一个新台阶特别会对递归的精华:时间复杂度作详细剖析会给大家总结一套很通用的求解递归时间复杂度的套路相信你看完肯定会有收获什么是递归简单地说就是如果在函数中存在着调用函数本身的情况这种现象就叫递归。以阶乘函数为例,如下, 在 factorial 函数中存在着 factorial(n - 1) 的调用所以此函数是递归函数public int factorial(int n) {if (n 1) {return 1;}return n * factorial(n - 1)
}
进一步剖析「递归」先有「递」再有「归」「递」的意思是将问题拆解成子问题来解决 子问题再拆解成子子问题...直到被拆解的子问题无需再拆分成更细的子问题即可以求解「归」是说最小的子问题解决了那么它的上一层子问题也就解决了上一层的子问题解决了上上层子问题自然也就解决了,....,直到最开始的问题解决,文字说可能有点抽象那我们就以阶层 f(6) 为例来看下它的「递」和「归」。求解问题 f(6), 由于 f(6) n * f(5), 所以 f(6) 需要拆解成 f(5) 子问题进行求解同理 f(5) n * f(4) ,也需要进一步拆分,... ,直到 f(1), 这是「递」f(1) 解决了由于 f(2) 2 f(1) 2 也解决了,.... f(n)到最后也解决了这是「归」所以递归的本质是能把问题拆分成具有相同解决思路的子问题。。。直到最后被拆解的子问题再也不能拆分解决了最小粒度可求解的子问题后在「归」的过程中自然顺其自然地解决了最开始的问题。递归算法通用解决思路我们在上一节仔细剖析了什么是递归可以发现递归有以下两个特点一个问题可以分解成具有相同解决思路的子问题子子问题换句话说这些问题都能调用同一个函数经过层层分解的子问题最后一定是有一个不能再分解的固定值的即终止条件,如果没有的话,就无穷无尽地分解子问题了问题显然是无解的。所以解递归题的关键在于我们首先需要根据以上递归的两个特点判断题目是否可以用递归来解。经过判断可以用递归后接下来我们就来看看用递归解题的基本套路四步曲先定义一个函数明确这个函数的功能由于递归的特点是问题和子问题都会调用函数自身所以这个函数的功能一旦确定了 之后只要找寻问题与子问题的递归关系即可接下来寻找问题与子问题间的关系即递推公式这样由于问题与子问题具有相同解决思路只要子问题调用步骤 1 定义好的函数问题即可解决。所谓的关系最好能用一个公式表示出来比如 f(n) n * f(n-) 这样如果暂时无法得出明确的公式用伪代码表示也是可以的, 发现递推关系后要寻找最终不可再分解的子问题的解即临界条件确保子问题不会无限分解下去。由于第一步我们已经定义了这个函数的功能所以当问题拆分成子问题时子问题可以调用步骤 1 定义的函数符合递归的条件函数里调用自身将第二步的递推公式用代码表示出来补充到步骤 1 定义的函数中最后也是很关键的一步根据问题与子问题的关系推导出时间复杂度,如果发现递归时间复杂度不可接受则需转换思路对其进行改造看下是否有更靠谱的解法听起来是不是很简单接下来我们就由浅入深地来看几道递归题看下怎么用上面的几个步骤来套实战演练从初级到高阶热身赛输入一个正整数n输出n!的值。其中n!123*…*n,即求阶乘套用上一节我们说的递归四步解题套路来看看怎么解定义这个函数明确这个函数的功能我们知道这个函数的功能是求 n 的阶乘, 之后求 n-1, n-2 的阶乘就可以调用此函数了/*** 求 n 的阶乘*/
public int factorial(int n) {
}
2.寻找问题与子问题的关系 阶乘的关系比较简单 我们以 f(n) 来表示 n 的阶乘 显然 f(n) n * f(n - 1), 同时临界条件是 f(1) 1,即3.将第二步的递推公式用代码表示出来补充到步骤 1 定义的函数中/*** 求 n 的阶乘*/
public int factorial(int n) {// 第二步的临界条件if (n 1) {return 1;}// 第二步的递推公式return n * factorial(n-1)
}
4.求时间复杂度 由于 f(n) n * f(n-1) n * (n-1) * .... * f(1),总共作了 n 次乘法所以时间复杂度为 n。看起来是不是有这么点眉目 当然这道题确实太过简单,很容易套路那我们再来看进阶一点的题入门题一只青蛙可以一次跳 1 级台阶或一次跳 2 级台阶,例如:跳上第 1 级台阶只有一种跳法直接跳 1 级即可。跳上第 2 级台阶有两种跳法每次跳 1 级跳两次或者一次跳 2 级。问要跳上第 n 级台阶有多少种跳法
我们继续来按四步曲来看怎么套路1.定义一个函数这个函数代表了跳上 n 级台阶的跳法/*** 跳 n 极台阶的跳法*/
public int f(int n) {
}
2.寻找问题与子问题之前的关系 这两者之前的关系初看确实看不出什么头绪但仔细看题目一只青蛙只能跳一步或两步台阶自上而下地思考也就是说如果要跳到 n 级台阶只能从 从 n-1 或 n-2 级跳 所以问题就转化为跳上 n-1 和 n-2 级台阶的跳法了如果 f(n) 代表跳到 n 级台阶的跳法那么从以上分析可得 f(n) f(n-1) f(n-2),显然这就是我们要找的问题与子问题的关系,而显然当 n 1, n 2 即跳一二级台阶是问题的最终解于是递推公式系为3.将第二步的递推公式用代码表示出来补充到步骤 1 定义的函数中 补充后的函数如下/*** 跳 n 极台阶的跳法*/
public int f(int n) {if (n 1) return 1;if (n 2) return 2;return f(n-1) f(n-2)
}
4.计算时间复杂度 由以上的分析可知 f(n) 满足以下公式斐波那契的时间复杂度计算涉及到高等代数的知识 这里不做详细推导有兴趣的同学可以点击这里查看,我们直接结出结论由些可知时间复杂度是指数级别显然不可接受那回过头来看为啥时间复杂度这么高呢,假设我们要计算 f(6),根据以上推导的递归公式展示如下可以看到有大量的重复计算, f(3) 计算了 3 次 随着 n 的增大f(n) 的时间复杂度自然呈指数上升了5.优化 既然有这么多的重复计算我们可以想到把这些中间计算过的结果保存起来如果之后的计算中碰到同样需要计算的中间态直接在这个保存的结果里查询即可这就是典型的 以空间换时间,改造后的代码如下public int f(int n) {if (n 1) return 1;if (n 2) return 2;// map 即保存中间态的键值对 key 为 nvalue 即 f(n)if (map.get(n)) {return map.get(n)}return f(n-1) f(n-2)
}
那么改造后的时间复杂度是多少呢由于对每一个计算过的 f(n) 我们都保存了中间态 不存在重复计算的问题所以时间复杂度是 O(n), 但由于我们用了一个键值对来保存中间的计算结果所以空间复杂度是 O(n)。问题到这里其实已经算解决了但身为有追求的程序员我们还是要问一句,空间复杂度能否继续优化?6.使用循环迭代来改造算法 我们在分析问题与子问题关系f(n) f(n-1) f(n-2)的时候用的是自顶向下的分析方式,但其实我们在解 f(n) 的时候可以用自下而上的方式来解决通过观察我们可以发现以下规律f(1) 1
f(2) 2
f(3) f(1) f(2) 3
f(4) f(3) f(2) 5
....
f(n) f(n-1) f(n-2)
最底层 f(1), f(2) 的值是确定的之后的 f(3), f(4) ,...等问题都可以根据前两项求解出来一直到 f(n)。所以我们的代码可以改造成以下方式public int f(int n) {if (n 1) return 1;if (n 2) return 2;int result 0;int pre 1;int next 2;for (int i 3; i n 1; i ) {result pre next;pre next;next result;}return result;
}
改造后的时间复杂度是 O(n), 而由于我们在计算过程中只定义了两个变量prenext所以空间复杂度是O(1)简单总结一下分析问题我们需要采用自上而下的思维而解决问题有时候采用自下而上的方式能让算法性能得到极大提升,思路比结论重要初级题接下来我们来看下一道经典的题目: 反转二叉树 将左边的二叉树反转成右边的二叉树接下来让我们看看用我们之前总结的递归解法四步曲如何解题 1.定义一个函数这个函数代表了翻转以 root 为根节点的二叉树public static class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) { val x; }
}public TreeNode invertTree(TreeNode root) {
}2.查找问题与子问题的关系,得出递推公式 我们之前说了解题要采用自上而下的思考方式那我们取前面的1 23 结点来看对于根节点 1 来说假设 2, 3 结点下的节点都已经翻转那么只要翻转 2 3 节点即满足需求对于2 3 结点来说也是翻转其左右节点即可,依此类推,对每一个根节点依次翻转其左右节点所以我们可知问题与子问题的关系是 翻转(根节点) 翻转(根节点的左节点) 翻转(根节点的右节点) 即 invert(root) invert(root-left) invert(root-right)而显然递归的终止条件是当结点为叶子结点时终止因为叶子节点没有左右结点3.将第二步的递推公式用代码表示出来补充到步骤 1 定义的函数中 public TreeNode invertTree(TreeNode root) {// 叶子结果不能翻转if (root null) {return null;}// 翻转左节点下的左右节点TreeNode left invertTree(root.left);// 翻转右节点下的左右节点TreeNode right invertTree(root.right);// 左右节点下的二叉树翻转好后翻转根节点的左右节点root.right left;root.left right;return root;
}
4.时间复杂度分析 由于我们会对每一个节点都去做翻转所以时间复杂度是 O(n)那么空间复杂度呢这道题的空间复杂度非常有意思我们一起来看下由于每次调用 invertTree 函数都相当于一次压栈操作 那最多压了几次栈呢 仔细看上面函数的下一段代码 TreeNode left invertTree(root.left);
从根节点出发不断对左结果调用翻转函数, 直到叶子节点每调用一次都会压栈左节点调用完后出栈再对右节点压栈....,下图可知栈的大小为3 即树的高度如果是完全二叉树 则树的高度为logn, 即空间复杂度为O(logn)最坏情况如果此二叉树是如图所示(只有左节点没有右节点)则树的高度即结点的个数 n此时空间复杂度为 O(n),总的来看空间复杂度为O(n)说句题外话这道题当初曾引起轰动因为 Mac 下著名包管理工具 homebrew 的作者 Max Howell 当初解不开这道题结果被 Google 拒了也就是说如果你解出了这道题就超越了这位世界大神想想是不是很激动中级题接下来我们看一下大学时学过的汉诺塔问题 如下图所示从左到右有A、B、C三根柱子其中A柱子上面有从小叠到大的n个圆盘现要求将A柱子上的圆盘移到C柱子上去期间只有一个原则一次只能移到一个盘子且大盘子不能在小盘子上面求移动的步骤和移动的次数接下来套用我们的递归四步法看下这题怎么解1.定义问题的递归函数明确函数的功能,我们定义这个函数的功能为把 A 上面的 n 个圆盘经由 B 移到 C// 将 n 个圆盘从 a 经由 b 移动到 c 上
public void hanoid(int n, char a, char b, char c) {
}
2.查找问题与子问题的关系 首先我们看如果 A 柱子上只有两块圆盘该怎么移前面我们多次提到分析问题与子问题的关系要采用自上而下的分析方式要将 n 个圆盘经由 B 移到 C 柱上去可以按以下三步来分析 * 将 上面的 n-1 个圆盘看成是一个圆盘,这样分析思路就与上面提到的只有两块圆盘的思路一致了 * 将上面的 n-1 个圆盘经由 C 移到 B * 此时将 A 底下的那块最大的圆盘移到 C * 再将 B 上的 n-1 个圆盘经由A移到 C上有人问第一步的 n - 1 怎么从 C 移到 B,重复上面的过程,只要把 上面的 n-2个盘子经由 A 移到 B, 再把A最下面的盘子移到 C,最后再把上面的 n - 2 的盘子经由A 移到 B 下..., 怎么样是不是找到规律了不过在找问题的过程中 切忌把子问题层层展开,到汉诺塔这个问题上切忌再分析 n-3,n-4 怎么移这样会把你绕晕只要找到一层问题与子问题的关系得出可以用递归表示即可。由以上分析可得move(n from A to C) move(n-1 from A to B) move(A to C) move(n-1 from B to C)一定要先得出递归公式哪怕是伪代码也好!这样第三步推导函数编写就容易很多终止条件我们很容易看出当 A 上面的圆盘没有了就不移了3.根据以上的递归伪代码补充函数的功能// 将 n 个圆盘从 a 经由 b 移动到 c 上
public void hanoid(int n, char a, char b, char c) {if (n 0) {return;}// 将上面的 n-1 个圆盘经由 C 移到 Bhanoid(n-1, a, c, b);// 此时将 A 底下的那块最大的圆盘移到 Cmove(a, c);// 再将 B 上的 n-1 个圆盘经由A移到 C上hanoid(n-1, b, a, c);
}public void move(char a, char b) {printf(%c-%c\n, a, b);
}
从函数的功能上看其实比较容易理解整个函数定义的功能就是把 A 上的 n 个圆盘 经由 B 移到 C由于定义好了这个函数的功能那么接下来的把 n-1 个圆盘 经由 C 移到 B 就可以很自然的调用这个函数,所以明确函数的功能非常重要,按着函数的功能来解释递归问题其实很好解析切忌在每一个子问题上层层展开死抠,这样这就陷入了递归的陷阱计算机都会栈溢出何况人脑4.时间复杂度分析 从第三步补充好的函数中我们可以推断出f(n) f(n-1) 1 f(n-1) 2f(n-1) 1 2(2f(n-2) 1) 1 2 * 2 * f(n-2) 2 1 22 * f(n-3) 2 1 22 * f(n-3) 2 1 22 * (2f(n-4) 1) 23 * f(n-4) 22 1 .... // 不断地展开 2n-1 2n-2 .... 1显然时间复杂度为 O(2n)很明显指数级别的时间复杂度是不能接受的汉诺塔非递归的解法比较复杂大家可以去网上搜一下进阶题现实中大厂中的很多递归题都不会用上面这些相对比较容易理解的题更加地是对递归问题进行相应地变形 来看下面这道题细胞分裂 有一个细胞 每一个小时分裂一次一次分裂一个子细胞第三个小时后会死亡。那么n个小时候有多少细胞照样我们用前面的递归四步曲来解1.定义问题的递归函数明确函数的功能 我们定义以下函数为 n 个小时后的细胞数public int allCells(int n) {
}
2.接下来寻找问题与子问题间的关系即递推公式 首先我们看一下一个细胞出生到死亡后经历的所有细胞分裂过程图中的 A 代表细胞的初始态, B代表幼年态(细胞分裂一次), C 代表成熟态(细胞分裂两次)C 再经历一小时后细胞死亡 以 f(n) 代表第 n 小时的细胞分解数 fa(n) 代表第 n 小时处于初始态的细胞数, fb(n) 代表第 n 小时处于幼年态的细胞数 fc(n) 代表第 n 小时处于成熟态的细胞数 则显然 f(n) fa(n) fb(n) fc(n) 那么 fa(n) 等于多少呢以n 4 即一个细胞经历完整的生命周期为例仔细看上面的图可以看出 fa(n) fa(n-1) fb(n-1) fc(n-1), 当 n 1 时显然 fa(1) 1fb(n) 呢,看下图可知 fb(n) fa(n-1)。当 n 1 时 fb(n) 0fc(n) 呢,看下图可知 fc(n) fb(n-1)。当 n 1,2 时 fc(n) 0综上 我们得出的递归公式如下f(n) fa(n) fb(n) fc(n)3.根据以上递归公式我们补充一下函数的功能public int allCells(int n) {return aCell(n) bCell(n) cCell(n);
}/*** 第 n 小时 a 状态的细胞数*/
public int aCell(int n) {if(n1){return 1;}else{return aCell(n-1)bCell(n-1)cCell(n-1);}
}/*** 第 n 小时 b 状态的细胞数*/
public int bCell(int n) {if(n1){return 0;}else{return aCell(n-1);}
}/*** 第 n 小时 c 状态的细胞数*/
public int cCell(int n) {if(n1 || n2){return 0;}else{return bCell(n-1);}
}
只要思路对了将递推公式转成代码就简单多了另一方面也告诉我们可能一时的递归关系我们看不出来此时可以借助于画图来观察规律4.求时间复杂度 由第二步的递推公式我们知道 f(n) 2aCell(n-1) 2aCell(n-2) aCell(n-3)之前青蛙跳台阶时间复杂度是指数级别的而这个方程式显然比之前的递推公式(f(n) f(n-1) f(n-2)) 更复杂的所以显然也是指数级别的总结大部分递归题其实还是有迹可寻的 按照之前总结的解递归的四个步骤可以比较顺利的解开递归题一些比较复杂的递归题我们需要勤动手画画图观察规律这样能帮助我们快速发现规律得出递归公式一旦知道了递归公式将其转成递归代码就容易多了,很多大厂的递归考题并不能简单地看出递归规律往往会在递归的基础上多加一些变形不过万遍不离其宗我们多采用自顶向下的分析思维多练习相信递归不是什么难事【END】关注下方二维码订阅更多精彩内容朕已阅
