难度: Medium
递归乘法。 写一个递归函数，不使用 * 运算符， 实现两个正整数的相乘。可以使用加号、减号、位移，但要吝啬一些。
示例1:
输入：A = 1, B = 10 输出：10
示例2:
输入：A = 3, B = 4 输出：12
提示:
- 保证乘法范围不会溢出
Submission
运行时间: 23 ms
内存: 16.0 MB
class Solution:
def multiply(self, A: int, B: int) -> int:
if B==1:
return A
if B==0:
return 0
return self.multiply(A, B-1) + A
Explain
本题解采用了递归的方式来实现两个正整数的乘法。递归的基本思想是将乘法问题 A * B 转换为 A + (A * (B-1))。具体来说，若乘数 B 为 1，直接返回被乘数 A；若乘数 B 为 0，根据乘法定义，返回 0。否则，递归调用自身，计算 A 与 B-1 的乘积，并将结果与 A 相加。
时间复杂度: O(B)
空间复杂度: O(B)
class Solution:
def multiply(self, A: int, B: int) -> int:
# Base case: if B is 1, the result is simply A
if B == 1:
return A
# Base case: if B is 0, the result of multiplication is 0
if B == 0:
return 0
# Recursive call: multiply A with (B-1) and add A to the result
return self.multiply(A, B-1) + A
Explore
在递归函数中，选择将问题分解为A + (A * (B-1))或(B + (B * (A-1)))本质上是等价的，因为乘法运算是交换律的。不过，在实现时，选择一种固定的递归方向（例如始终减小B而不是A）可以简化问题的理解和代码的实现。此外，如果从实现的角度来看，选择较小的数字作为递归深度的依据（例如当B < A时，使用B作为递归参数）可以减少递归调用的深度，从而提高效率。但在题解中，未明确说明这一点，而是固定地使用B来减少。
递归方法在处理大数字乘法时主要的性能问题是递归深度过大，可能会导致栈溢出。在递归每次调用中，若B的值非常大，那么需要递归调用自身B次，这样的递归深度在B非常大时可能超出系统栈的限制，从而引发运行时错误。此外，递归的重复计算和函数调用开销也会导致程序运行效率低下。优化的方案可以包括使用尾递归优化、迭代替代递归或者使用分治法如俄罗斯农民乘法等方法来减少递归的深度和次数。
在递归基例中单独处理B为1和B为0的情况，是为了定义递归的终止条件，从而防止无限递归的发生。当B为1时，根据乘法定义，A乘以1就是A本身，这提供了一个自然的停止点。当B为0时，任何数乘以0都应为0，这同样是递归的另一个终止点。这两个基例是递归能够正确并有效返回结果的关键。如果没有这些基例，递归将缺乏明确的结束条件，可能会导致错误的结果或无限递归。因此，这种处理不仅符合乘法的数学定义，也是确保递归能够正确完成的必要条件。