I try to understand how recursion works. Here is an example of how to multiply two numbers using a loop:

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

Please tell me how to redo this cycle using recursion? (using addition only)

    3 answers 3

    The solution to the forehead is quite trivial, but even here the presence of a rake must be taken into account:

     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; }

    That is, first we go down into the chain of b elements, and then we begin to rise back, accumulating the amount.

    Let me explain what kind of rake was discussed:

    1. Multipliers can be negative. If this is not taken into account, there will be endless recursion.

    2. For large b, the chain will be longer than the stack can accommodate. Therefore, as the length of the chain must take the smallest of the factors.

      By analogy with the fast exponentiation algorithm :

       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; // логарифмический спуск на чётных }

      Working demo on 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 ));

      • @And, please comment on - vp_arth

      You can still like this:

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

      But it all depends on what operations you need to do.

      • 3
        I highly doubt that it works. You do max-min iterations, but still return the unchanged max .. - vp_arth
      • @vp_arth, so try it, by the way, I tried it and everything works as it should. - And
      • Badly tried - vp_arth am
      • one
        Not only is the answer incorrect, it’s not at all clear why here ++min , if the parameters in java are not passed by reference. - Suvitruf ♦
      • one
        But how does this differ from int mult(int min, int max) { return max; } int mult(int min, int max) { return max; } ? Or even int mult(int min, int max) { return min<=max?max:mult(min, max); } int mult(int min, int max) { return min<=max?max:mult(min, max); } including buffer overflow. Where is the multiplication here? - vp_arth