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

class Solution {
public:
    int multiply(int A, int B) {
        if(A == 0 || B == 0)
            return 0;
        if(A < B)
            return B + multiply(A-1,B);
        else
            return A + multiply(A, B-1);
    }
};

之所以要判断A与B的大小，是因为使用小的作为循环次数，可以提高效率。
方法二：分治法

class Solution {
public:
    int multiply(int A, int B) {
        if(B == 0) return 0;
        if(B == 1) return A;
        int C = 0;
        if(B&1) C = A;
        return multiply(A, B>>1) + multiply(A, B>>1) + C;
    }
};

运行效率:

执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗：5.7 MB, 在所有 C++ 提交中击败了82.22%的用户