SomeGuyWithFingers SomeGuyWithFingers - 7 months ago 11
Java Question

Recursion and multiplication

Is this possible guys? This is homework I have, and my teacher obviously believes it is, but it seems to me that it's impossible not to use addition or multiplication outside of the short-multiplication method.


Write (and provide a tester for) a recursive algorithm:

int multiply(int x, int y)

to multiply two positive integers together without using the *
operator. Do not just add x to itself y times!!!

(Hint: Write a recursive method that will multiply an integer by a
value in the range 0 .. 10. Then write a second recursive method to
implement the multiplication algorithm you learned to multiply
multi-digit numbers in elementary school.)


My issue is that once you break down any multi digit number and starting adding those together you have to use multiplication of numbers greater than 10, i.e 22 * 6 is 2 * 6 + 20 * 6 ... so am I totally missing something?

EDIT
I guess I should have added this is the code I have,

public int mult(int x, int y){
return x == 0 ? 0 : (mult(x-1, y) + y);
}


which is perfect, but as far as I understand the instructions, that's breaking do not just add x to itself y times. I personally believe it isn't, but my teacher hasn't been very clear, and I'd like to know if there's some other way that I havn't thought of, sorry for the confusion.

Answer

My interpretation of the assignment is that the teacher would like the student to implement a recursive algorithm to perform Grid method multiplication (the kind we learn in elementary school).

For example, multiplying 34 x 13 would be done like so...

  34
* 13
====
  12
  90
  40
+300
====
 442

I didn't have easy access to a Java development environment, so I wrote the code in C# but the algorithm should be simple enough to convert into Java.

public int Multiply(int x, int y)
{
    if (x < 0) throw new ArgumentException("must be positive integer", "x");
    if (y < 0) throw new ArgumentException("must be positive integer", "y");

    if (x == 0 || y == 0) return 0; // obvious quick-exit condition

    // integer division
    int xDivBy10 = x / 10;
    int yDivBy10 = y / 10;

    bool xIsSingleDigit = xDivBy10 == 0;
    bool yIsSingleDigit = yDivBy10 == 0;

    // base case
    if (xIsSingleDigit && yIsSingleDigit)
    {
        return MultiplySingleDigits(x, y);
    }

    // otherwise, use grid multiplication recursively
    // http://en.wikipedia.org/wiki/Grid_method_multiplication

    if (xIsSingleDigit) // y must not be a single digit
    {
        return (Multiply(x, yDivBy10) * 10) + Multiply(x, y % 10);
    }

    if (yIsSingleDigit) // x must not be a single digit
    {
        return (Multiply(xDivBy10, y) * 10) + Multiply(x % 10, y);
    }

    // else - x and y are both numbers which are not single digits
    return (Multiply(x, yDivBy10) * 10) + Multiply(x, y % 10); // the same code as the "if (xIsSingleDigit)" case
}

// technically, this algorith can multiply any positive integers
// but I have restricted it to only single digits as per the assignment's requirements/hint
private int MultiplySingleDigits(int x, int y)
{
    if (x < 0 || x > 9) throw new ArgumentException("must be in range 0 - 9 (inclusive)", "x");
    if (y < 0 || y > 9) throw new ArgumentException("must be in range 0 - 9 (inclusive)", "y");

    if (x == 0 || y == 0) return 0; // base case
    return x + MultiplySingleDigits(x, y - 1);
}

NOTES:

  • This approach still uses the * operator but not for actually multiplying x and y, it is used to increase other sub-products by multiples of 10
  • Many parts of this code could be simplified/refactored but I specifically left them expanded to make the steps more obvious
Comments