Recursive Multiply

• Multiplication of a number is nothing but repeated addition.
• So, a brute force approach could be to recursively add the bigger of the two numbers (M and N) to itself until we obtain the required product.
• Let’s assume that M >= N. Then according to this approach, we recursively add ‘M’ to itself, ‘N’ times.

• The idea behind this approach is the same as the previous one.
• But in the previous approach, we calculate the product of the same numbers, multiple times. This can be seen from the recursion tree as depicted below

• This results in more number of operations being performed.
• We can avoid this by storing the results, which we have already calculated, and using them whenever required, instead of calculating it again.
• Hence, we use the concept of memoization.

Algorithm:

• Let’s assume that M >= N.
• Create a hash table memo, to store the results of the sub-problems.
• Let our recursive function be recursiveProductHelper(M, N, memo), which takes the two positive integers ‘M’ and ‘N’ and a hash table ‘memo’ as its arguments, and returns the product of these two integers (M * N).
• Base Condition 1: If N == 0, we have the multiplier equal to zero, which makes the complete product zero. So, just return 0.
• Base Condition 2: If N == 1, we have the multiplier equal to 1. So, the product is equal to the multiplicand. Hence, return M.
• Base Condition 3: If memo contains an entry for N, then we have already calculated this result before. So, just return memo[N].
• Divide the multiplier (i.e. N) by 2, and store it in another variable say halfN, i.e. halfN = N >> 1.
• Recursively calculate the product for the first half, and store it in a variable say product1, i.e. product1 =  recursiveProductHelper(M, halfN, memo).
• If the multiplier (i.e. N) is even:
  • Then the other half of the product is the same as the first half, i.e. product2 = product1.
• Otherwise, we need to recursively calculate the other half of the product as product2 = recursiveProductHelper(M, N - halfN, memo).
• The required answer is the sum of the two halves.
• Store the answer in the hash table so that we can use it later, if required, i.e. memo[N] = product1 + product2.
• Return memo[N].

• Instead of repeatedly adding the number one at a time, we can reduce the number of operations by calculating only half of the required product and then doubling the result to get the required answer.
• So, in each recursive step, we divide the multiplier by 2 (using right shift operator), calculate the product (recursively) and then double the result obtained to get the actual answer.
• But the above procedure will only work when the multiplier is even.
• In case the multiplier is odd, we cannot just double our calculated result. Instead, we would have to compute the other half recursively.
• The sum of these two halves gives us the required product.

Algorithm:

• Let’s assume that M >= N.
• Let our recursive function be recursiveProductHelper(M, N), which takes the two positive integers ‘M’ and ‘N’ and returns the product of these two integers (M * N).
• Base Condition 1: If N == 0, we have the multiplier equal to zero, which makes the complete product zero. So, just return 0.
• Base Condition 2: If N == 1, we have the multiplier equal to 1. So, the product is equal to the multiplicand. Hence, return M.
• Divide the multiplier (i.e. N) by 2, and store it in another variable say halfN, i.e. halfN = N >> 1.
• Recursively calculate the product for the first half, and store it in a variable say product1, i.e. product1 =  recursiveProductHelper(M, halfN).
• If the multiplier (i.e. N) is even:
  • Then the other half of the product is the same as the first half, i.e. product2 = product1.
• Otherwise, we need to recursively calculate the other half of the product as product2 = recursiveProductHelper(M, N - halfN).
• The required answer is the sum of the two halves. So, return product1 + product2.

• From approach 3, we understood that to calculate the product, we only need to make one recursive call, when the multiplier is an even number.
• And for an odd multiplier we would have to make two recursive calls. But this can be avoided easily.
• If we look closely, we observe that the multiplier in the second recursive call (i.e. N - halfN) will always be one more than the multiplier in the first recursive call (i.e. halfN). To understand this better, look at the following example:
  • We know, product(M, N) = product(M, halfN) + product(M, N - halfN) where halfN = N >> 1.
  • Let M = 20 and N = 17.
  • Then, product(20, 17) = product(20, 8) + product(20, 9).
• Hence, we can calculate the result of the second recursive call by adding the multiplicand (i.e. M) to the result of the first recursive call. In this way, we can avoid the extra recursive call for the odd multiplier.
  • i.e. product(M, N - halfN) = product(M, halfN) + M.
• Therefore, when N is even, product(M, N) = 2 * product(M, N/2).
• And when N is odd, product(M, N) = 2 * product(M, N/2) + M.
• As in this approach, the value of N decreases (by half) in each recursive call, hence, we will never encounter the same sub-problem again. So, there is no need for memoization.

Algorithm:

• Let’s assume that M >= N.
• Let our recursive function be recursiveProductHelper(M, N), which takes the two positive integers ‘M’ and ‘N’ and returns the product of these two integers (M * N).
• Base Condition 1: If N == 0, we have the multiplier equal to zero, which makes the complete product zero. So, just return 0.
• Base Condition 2: If N == 1, we have the multiplier equal to 1. So, the product is equal to the multiplicand. Hence, return M.
• Recursively calculate the half product, and store it in a variable say halfProduct, i.e. halfProduct =  recursiveProductHelper(M, N >> 1).
• If the multiplier (i.e. N) is even:
  • Then the required answer is the double of the previously calculated result. So, return halfProduct + halfProduct.
• Otherwise, the multiplier (i.e. N) is odd. So, the required answer is halfProduct + halfProduct + M.