README.md

面试题 08.05. 递归乘法

English Version

题目描述

递归乘法。 写一个递归函数，不使用 * 运算符， 实现两个正整数的相乘。可以使用加号、减号、位移，但要吝啬一些。

示例1:

 输入：A = 1, B = 10
 输出：10

示例2:

 输入：A = 3, B = 4
 输出：12

提示:

1. 保证乘法范围不会溢出

解法

最佳方案： 直接返回 A * B 正常递归，叠加总和

MULTIPLY(A, B)
    if A == 0 || B == 0
        return 0
    A + multiply(A, B - 1)

优化 1： 由数值较小的数字决定递归层次

MULTIPLY(A, B)
    if A == 0 || B == 0
        return 0
    return max(A, B) + multiply(max(A, B), min(A, B) - 1)

优化 2： 使用位移减少递归层次

MULTIPLY(A, B)
    return (B % 1 == 1 ? A : 0) + (B > 1 ? MULTIPLY(A + A, B >> 1) : 0)

可进一步，转换为循环，虽然并不符合递归主题。

A 与 B 皆为正整数，初始值不会为 0，所以终止条件是 B != 1

MULTIPLY(A, B)
    T = min(A, B)
    A = max(A, B)
    B = T
    r = 0
    while B != 1 {
        if B % 2 == 1 {
            r = r + A
        }
        A = A + A
        B = B >> 1
    }
    return res + A

Python3

Java

TypeScript

function multiply(A: number, B: number): number {
    if (A === 0 || B === 0) {
        return 0;
    }
    const [max, min] = [Math.max(A, B), Math.min(A, B)];
    return max + multiply(max, min - 1);
}

function multiply(A: number, B: number): number {
    const max = Math.max(A, B);
    const min = Math.min(A, B);
    const helper = (a: number, b: number) =>
        (b & 1 ? a : 0) + (b > 1 ? helper(a + a, b >> 1) : 0);
    return helper(max, min);
}

Rust

impl Solution {
    pub fn multiply(a: i32, b: i32) -> i32 {
        if a == 0 || b == 0 {
            return 0;
        }
        a.max(b) + Self::multiply(a.max(b), a.min(b) - 1)
    }
}

...