递归乘法

难度:

标签:

题目描述

Write a recursive function to multiply two positive integers without using the * operator. You can use addition, subtraction, and bit shifting, but you should minimize the number of those operations.

Example 1:

 Input: A = 1, B = 10
 Output: 10

Example 2:

 Input: A = 3, B = 4
 Output: 12

Note:

The result will not overflow.

代码结果

运行时间: 23 ms, 内存: 16.0 MB

/*
题目思路：
使用 Java Stream 不适合直接解决递归乘法问题，因为 Stream 是一个数据处理工具，而不是一个递归工具。
但是我们可以使用其他方法来模拟这个递归过程。
这里我们使用 IntStream 来生成一个从 0 到 B-1 的范围，并将每个值映射为 A，最后进行求和。
*/

import java.util.stream.IntStream;

public class Solution {
    public int multiply(int A, int B) {
        return IntStream.range(0, B).map(i -> A).sum();
    }
}

解释

方法:

本题解采用了递归的方式来实现两个正整数的乘法。递归的基本思想是将乘法问题 A * B 转换为 A + (A * (B-1))。具体来说，若乘数 B 为 1，直接返回被乘数 A；若乘数 B 为 0，根据乘法定义，返回 0。否则，递归调用自身，计算 A 与 B-1 的乘积，并将结果与 A 相加。

时间复杂度:

O(B)

空间复杂度:

O(B)

代码细节讲解

🦆

在递归函数中，为什么选择将问题分解为A + (A * (B-1))，而不是(B + (B * (A-1)))，这两种方式有何不同？

▷

在递归函数中，选择将问题分解为A + (A * (B-1))或(B + (B * (A-1)))本质上是等价的，因为乘法运算是交换律的。不过，在实现时，选择一种固定的递归方向（例如始终减小B而不是A）可以简化问题的理解和代码的实现。此外，如果从实现的角度来看，选择较小的数字作为递归深度的依据（例如当B < A时，使用B作为递归参数）可以减少递归调用的深度，从而提高效率。但在题解中，未明确说明这一点，而是固定地使用B来减少。

🦆

递归方法在处理大数字乘法时可能存在哪些性能问题，比如说对于非常大的B值？

▷

递归方法在处理大数字乘法时主要的性能问题是递归深度过大，可能会导致栈溢出。在递归每次调用中，若B的值非常大，那么需要递归调用自身B次，这样的递归深度在B非常大时可能超出系统栈的限制，从而引发运行时错误。此外，递归的重复计算和函数调用开销也会导致程序运行效率低下。优化的方案可以包括使用尾递归优化、迭代替代递归或者使用分治法如俄罗斯农民乘法等方法来减少递归的深度和次数。

🦆

为什么在递归基例中单独处理B为1和B为0的情况，这种处理对于整体递归流程有何影响？

▷

在递归基例中单独处理B为1和B为0的情况，是为了定义递归的终止条件，从而防止无限递归的发生。当B为1时，根据乘法定义，A乘以1就是A本身，这提供了一个自然的停止点。当B为0时，任何数乘以0都应为0，这同样是递归的另一个终止点。这两个基例是递归能够正确并有效返回结果的关键。如果没有这些基例，递归将缺乏明确的结束条件，可能会导致错误的结果或无限递归。因此，这种处理不仅符合乘法的数学定义，也是确保递归能够正确完成的必要条件。

递归乘法

题目描述

代码结果

解释

代码细节讲解

相关问题