LeetCode面试题 08.05. 递归乘法：A * B 就是B个A相加

【题目描述】

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

示例1:
输入：A = 1, B = 10
输出：10

示例2:
输入：A = 3, B = 4
输出：12

提示:
保证乘法范围不会溢出

【解题思路】

A x B 就是B个A相加。

这里优化了一下，取A和B中，较大的max以及较小的min，做min次max相加可以节省运算次数。

【代码】

class Solution {
    public int multiply(int A, int B) {
        int min = A > B? B: A;
        int max = A > B? A: B;
        return mul(max, min);
    }

    private int mul(int max, int min) {
        if (min == 0) {
            return 0;
        }
        return max + mul(max, --min);
    }
}

来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。