干货满满！全面详解如何用递归解题( 二 ) _递归

听起来是不是很简单，接下来我们就由浅入深地来看几道递归题，看下怎么用上面的几个步骤来套

4.实战演练（从初级到高阶）
热身赛

输入一个正整数n，输出n!的值。其中n!=123*…*n,即求阶乘

套用上一节我们说的递归四步解题套路来看看怎么解

定义这个函数，明确这个函数的功能，我们知道这个函数的功能是求 n 的阶乘, 之后求 n-1, n-2 的阶乘就可以调用此函数了

/*** 求 n 的阶乘*/public intfactorial(int n) {}2.寻找问题与子问题的关系阶乘的关系比较简单，我们以 f(n) 来表示 n 的阶乘，显然 f(n) = n * f(n - 1), 同时临界条件是 f(1) = 1,即
3.将第二步的递推公式用代码表示出来补充到步骤 1 定义的函数中

/*** 求 n 的阶乘*/public intfactorial(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 intf(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 intf(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 为 n，value 即 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) = 1f(2) = 2f(3) = f(1) + f(2) = 3f(4) = f(3) + f(2) = 5....f(n) = f(n-1) + f(n-2)最底层 f(1), f(2) 的值是确定的，之后的 f(3), f(4) ,...等问题都可以根据前两项求解出来，一直到 f(n) 。所以我们的代码可以改造成以下方式