Recursive Multiply

Recursive Multiply

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

Solution

递归

Code

// Use the solution from the book to help understanding
int minProduct(int a, int b) {
    int bigger = a < b ? b : a;
    int smaller = a < b ? a : b;
    return minProduct(smaller, bigger);
}

int minProductHelper(int smaller, int bigger) {
    if (smaller == 0)
        return 0;
    else if (smaller == 1)
        return bigger;

    int s = smaller >> 1; // Divide by 2
    int halfProd = minProductHelper(s, bigger);

    if (smaller % 2 == 0){
        return halfProd + halfProd;
    }
    else {
        return halfProd + halfProd + bigger;
    }
}