[LeetCode]面试题 08.05. 递归乘法

难度 中等

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

示例1:

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

示例2:

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

提示:

    保证乘法范围不会溢出

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/recursive-mulitply-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

首先，题意说明了一定要用递归，并且只能用加号、减号、位移运算出结果。那么首要的是，一定要防止递归爆栈，第二个就是仅用这三种位运算符运算出结果。

解法一：使用递归，防止爆栈,取小值做递归累加。执行通过。

解法二：暂无。

解法一：

class Solution {
    public int multiply(int A, int B) {

        //防止爆栈,取大数做递归累加,这样递归便是最小的栈
        if (A > B) {
            B--;
            if (B < 0)
                return 0;
            return A + multiply(A, B);
        } else {//防止爆栈,取大数做递归累加,这样递归便是最小的栈
            A--;
            if (A < 0)
                return 0;
            return B + multiply(A, B);
        }
    }
}

执行结果：通过
执行用时：0 ms, 在所有 Java 提交中击败了100.00% 的用户
内存消耗：35 MB, 在所有 Java 提交中击败了89.86% 的用户
通过测试用例：30 / 30

记录与总结，2021年 11月 13日 星期六 12:31:52 CST。