如何写递归( 三 ) _递归

下面我们以力扣一个算法题递归乘法进行实战，实战前请花 10 min 时间尝试自我完成。
如果只是局限于看小说似的阅读，现在就可以「ALT+F4」了。::
java
递归乘法。写一个递归函数，不使用 * 运算符，实现两个正整数的相乘。可以使用加号、减号、位移，但要吝啬一些。示例 1:输入：A = 1, B = 10输出：10示例 2:输入：A = 3, B = 4输出：12public int multiply(int A, int B)
3.1 审题思路
乘法本身是加法的变种，A * B = A 个 B 相加。
寻找基本情况的条件为：A 个 B 相加一次 A - 1，A 如果为 1 时即找到最后一个 B。
首先我们用循环完成。
public int multiplyFor(int A, int B) {int sum = 0;while (A-- > 0) sum += B;return sum;}
3.2 尝试递归
寻找递推关系 f(a,b) = b + f(a-1,b)f(a,b)=b+f(a?1,b)，基本情况条件为 a < 2a
套入「由下到上」的范式如下：
- 寻找递归递推关系- 寻找递归基本情况，跳出时返回基本情况的结果 -> B- 修改递归函数的参数，递归调用并返回中间变量 -> return sum（中间变量）- 使用递归函数的返回值进行计算并返回最终结果 -> sum + Bpublic int multiply(int A, int B) {if (A < 2) return B;// 跳出时返回基本情况的结果int sum = multiply(A - 1, B); // 先递归return sum + B;// 再计算，依赖递归的返回值}
尝试转换为递归「由上到下」（尾递归），依赖中间结果（每次的和），先计算再递归。
f(a,b) = sum + f(a-n,b)f(a,b)=sum+f(a?n,b)，为已经计算了的 nn 个 bb 的和。
- 寻找递推关系- 创建新函数，将「由下到上-范式」中的最终结果计算依赖的中间变量提取为函数的参数 -> multiply1Help 函数 sum 为中间变量- 寻找递归基本情况，跳出时返回基本情况的结果与中间变量的计算结果（最终结果） -> return B + sum- 根据函数参数与中间变量重新计算出新的中间变量 -> sum += B- 修改参数 -> A - 1- 递归调用并返回（该处的返回由基本情况条件触发）-> B + sumpublic int multiply1(int A, int B) {return multiply1Help(A, B, 0);}public int multiply1Help(int A, int B, int sum) {if (A < 2) return B + sum;// 跳出时返回基本情况的结果与中间变量的计算结果sum += B;// 根据函数参数与中间变量重新计算出新的中间变量return multiply1Help(A - 1, B, sum);// 由基本情况条件触发决定，最终返回 B + sum}
至此，两个递归写法已实现，实际编码中「由上到下」比「由下到上」更容易理解，因为我们的思维从上向下思考容易，但是逆着思考就比较抽象了。
这个抽象过程需要大量的练习，末尾推荐了部分递归的算法题。
3.3 尝试优化
分析上述实现的两个递归时间复杂度为 O(n)O(n)，n = Max(A,B)n=Max(A,B)，考虑如何优化时间复杂度。
如果 A > B，处理 A 次，因此考虑使用 M=MIN(A,B)M=MIN(A,B) 作为循环次数。比如 100 * 1100?1 时可优化 100 倍
分析重复计算问题，目前没有。

文章插图
分析参数的边界问题，目前没有。题目给定约束都是正整数。
优化时间复杂度，重新分析递推关系为 a * b = (a/2) * (b*2)a?b=(a/2)?(b?2)，直到 a/2a/2 等于 11 时，bb 就是最终结果，我们基于二进制的位移操作进行优化，
但是要考虑如果是奇数除以 22 时会丢失一个 bb，这样复杂度优化为 O(\)O(log
?
n)

优化过程示例：a * b = (a/2) * (b*2)偶数为循环次数的运算过程8 * 9 4 * 182 * 361 * 7272奇数为循环次数的运算过程7 * 99 + (3 * 18)-> 7/2 时丢失一个 9 9 + 18 + (1 * 36)-> 3/2 时丢失一个 18 9 + 18 + 36 63