程序员面试金典-面试题 08.05. 递归乘法

题目：

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

示例1:

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

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

分析：

我们将A看做被乘数，如果A为偶数的话则multiply(A , B) = multiply(A>>1 , B) << 1 ,也就是A/2*B的二倍。

如果A为奇数数的话则multiply(A , B) = multiply(A>>1 , B) << 1 + B ,也就是（A-1）/2*B*2 + B。

程序：

class Solution {
    public int multiply(int A, int B) {
        return helper(A, B);
    }
    public int helper(int A, int B) {
        if(A == 1)
            return B;
        if(A % 2 == 0)
            return helper(A >> 1, B) << 1;
        else
            return (helper(A >> 1, B) << 1) + B;
    }
}