主页 / 问题 / 843059
Accepted
Oleg Khegay
Asked:2020-06-17 17:16:28 +0000 UTC2020-06-17 17:16:28 +0000 UTC

用递归乘以数字

  • 772

我试图了解递归是如何工作的。以下是如何使用循环将两个数字相乘的示例：

public int mult(int a, int b){
    int sum=0;
    for (int i=0;i<b;i++){
        sum+=a;
    }
    return sum;
}

请告诉我如何使用递归重新制作这个循环？（仅使用加法）

java

3 个回答

  1. Best Answer

    前额的解决方案非常简单，但即使在这里也有必要考虑到 rake 的存在：

    private int mult_step(int summand, int steps_count){
    if (steps_count > 0)
        return summand + mult(summand, steps_count - 1);
    else
        return 0;
}

public int mult(int a, int b){
    int summand, steps_count;
    Boolean negate;
    if(a > b){
        summand = a;
        steps_count = Math.abs(b);
        negate = (b < 0);
    } else{
        summand = b;
        steps_count = Math.abs(a);
        negate = (a < 0);
    }

    int sum = mult_step(summand, steps_count);
    return negate ? -sum : sum;
}

    也就是说，首先我们深入到b元素的链中，然后我们开始往回爬，积累总和。

    让我解释一下我们谈论的是哪种耙子：

    1. 乘数可以是负数。如果不考虑这一点，就会出现无限递归。

    2. 对于大b，链将比堆栈可以容纳的更长。因此，应取最小的因素作为链的长度。

    • 3

  2. 与快速求幂算法类似，它是可能的： 

    public static int mul(int a, int b){
    if (b < 0) return -mul(a, -b); // обработка отрицательных значений
    if (b == 1) return a;          // тривиальные условия выхода 

    if ((b & 1) == 1)  return a + mul(a, b-1); // обработка нечётных
    return mul(a, b >> 1) << 1;                // логарифмический спуск на чётных
}

    js上的工作演示： 

    function mul(a, b) {
  if (b < 0) return -mul(a, -b);
  if (b == 1) return a;
  if ((b&1) == 1)  return a + mul(a, b-1);
  return mul(a, b >> 1) << 1;
  // за счёт деления на 2 мы получаем всего logN итераций
}

[
  [2, 7],
  [3, 8],
  [-13, -17],
].forEach(([a, b]) => console.log(
  a, b, 
  mul(a, b), 
  mul(a, b) === a*b
));

    • 1

  3. 也可以这样：

    int mult(int min, int max) {
    if (min == max) {
        return max;
    }
    return mult(++min, max);
}

    但这一切都取决于你需要做什么样的操作。

    • -2

相关问题