LeetCode 面试题 08.05. 递归乘法

约 4 分钟
文章信息 8 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 5-10 程序员面试金典（第 6 版） 字节 亚马逊
标签
数学 位运算 递归

题目描述

✅ 面试题 08.05. 递归乘法

image-20260929000733090

题意分析

用递归计算两个正整数的乘积，代码不能使用 * 运算符，可以使用加法、减法和位移，并应尽量减少运算次数。题目保证最终乘积不会溢出。

解法：递归折半相加

核心思路

[!blue]

把乘积看成“将一个数重复相加若干次”。若每层只减少一次相加次数，递归深度会与乘数一样大；可以改为每次把份数折半。利用乘法的交换性，让较小数 smaller 表示份数，较大数 larger 表示每份的值，减少递归层数。

定义 helper(smaller, larger) 为这些份数相加的结果。设 q = smaller >> 1，即份数的一半向下取整，先递归求出 half = helper(q, larger)。如果原份数为偶数，它恰好由两个相同的半份数构成，结果就是 half + half；如果原份数为奇数，两个半份数合起来还少一份，所以再加 larger。smaller & 1 用来区分这两种情况。

smaller == 1 时只有一份，直接返回 larger；代码也将零份定义为零。只要份数大于一，右移后就严格减小，因此递归一定到达出口。从出口向上，每层都把两个半份数与可能剩余的一份重新合并，恢复这一层所要求的准确份数。

两个半规模子问题完全相同，必须只递归一次，并把结果保存为 half 后重复使用。这样递归是一条每层折半的调用链，每层只做一到两次加法；若直接写两次同样的递归调用，就会产生重复分支，把对数级工作重新扩展到线性级。

所有乘数为正，每个子问题的份数都不超过原来的份数，中间的加法结果也不超过最终乘积，因此题目给出的不溢出保证同样覆盖这些中间结果。

解题步骤

  1. 将两个输入中的较小者设为 smaller、较大者设为 larger，调用辅助递归函数。
  2. 若份数为零或一，分别返回零或 larger。
  3. 右移 smaller 一位，只递归一次得到半规模结果 half。
  4. 用最低位判断奇偶：偶数返回 half + half，奇数再加一份 larger。

代码实现

class Solution {
    public int multiply(int A, int B) {
        int smaller = Math.min(A, B);
        int larger = Math.max(A, B);

        return helper(smaller, larger);
    }

    // 较大乘数保持不变，只将较小乘数逐层折半
    private int helper(int smaller, int larger) {
        if (smaller == 0) {
            return 0;
        }

        if (smaller == 1) {
            return larger;
        }

        // 半规模结果只求一次再复用，避免递归重复分叉
        int half = helper(smaller >> 1, larger);

        if ((smaller & 1) == 0) {
            return half + half;
        }

        // 奇数折半少了一份，最后补上较大乘数
        return half + half + larger;
    }
}

func multiply(A int, B int) int {
    smaller, larger := A, B
    if smaller > larger {
        smaller, larger = larger, smaller
    }
    return multiplyHelper(smaller, larger)
}

// 较大乘数保持不变，只将较小乘数逐层折半
func multiplyHelper(smaller int, larger int) int {
    if smaller == 0 {
        return 0
    }
    if smaller == 1 {
        return larger
    }

    // 半规模结果只求一次再复用，避免递归重复分叉
    half := multiplyHelper(smaller>>1, larger)
    if smaller&1 == 0 {
        return half + half
    }
    // 奇数折半少了一份，最后补上较大乘数
    return half + half + larger
}

复杂度分析

  • 时间复杂度：$O(\log(\min(A,B)+1))$。每层只调用一次半规模子问题，并做常数次加法与位运算。
  • 空间复杂度：$O(\log(\min(A,B)+1))$。递归栈的深度由较小乘数不断折半的次数决定。

关键点总结

[!green]

  • 递归缩小的是重复相加的份数，每份的值始终保持不变。
  • 奇数比两个向下取整的半份数多一份，所以要额外加上 larger。
  • 保存并复用 half，才会让每层只计算一个子问题。

易错点总结

[!yellow]

  • 将 half + half 写成两次递归调用，会重复计算完全相同的子问题。
  • 奇数只返回两个 half 会少一份；额外应加的是 larger，不是当前份数 smaller。
  • 两个乘数同时折半，会同时减少份数与每份的值，无法按当前递推还原乘积。
  • 代码中用 half * 2 代替相加，仍然违反禁止使用乘法运算符的要求。

相似题目

题目 难度 关联与区别
50. Pow(x, n) 中等 同样按二进制拆分次数，本题把乘数折半并倍增加数，快速幂则把指数折半并平方底数。
29. 两数相除 中等 同样通过倍增减少逐次累加的成本，本题只禁乘号，除法题的允许操作与符号边界另有要求。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/47196357
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！