面试题 08.05. 递归乘法

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

示例1:

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

示例2:

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

提示:

• 保证乘法范围不会溢出

Python 解答：
1.累加

class Solution:
    def multiply(self, A: int, B: int) -> int:
        res = 0
        A, B = max(A, B), min(A, B)
        for i in range(B):
            res += A
        return res

2.位移

class Solution:
    def multiply(self, A: int, B: int) -> int:
        if A == 1:
            return B
        elif A&1 == 1:
            return self.multiply(A>>1, B<<1) + B
        else:
            return self.multiply(A>>1, B<<1)