# Recursive Multiply

Posted: 23 Feb, 2021

Difficulty: Moderate

#### You are given two positive integers. Your task is to multiply the two numbers using recursion by performing a minimum number of operations. Note that you can use addition, subtraction, and/ or bit shifting, but you cannot use the multiplication or division operation.

##### Input Format :

```
The very first line of input contains an integer ‘T’ denoting the number of test cases.
The first and the only line of every test case contains two space-separated positive integers ‘M’ and ‘N’.
```

##### Output Format :

```
For each test case, print the result obtained after multiplying these two numbers.
```

##### Note :

```
The result can be very large. So, print the answer modulo 1000000007.
You do not need to print anything, it has already been taken care of. Just return the result.
```

##### Constraints :

```
1 <= T <= 10
1 <= M, N <= 10^8
Time Limit: 1 sec
```

Approach 1

- 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.

Approach 2

- 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.**

- Then the other half of the product is the same as the first half, i.e.
- 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].**

Approach 3

- 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.**

- Then the other half of the product is the same as the first half, i.e.
- 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.**

Approach 4

- 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.**

- Then the required answer is the double of the previously calculated result. So, return
- Otherwise, the multiplier (i.e. N) is odd. So, the required answer is
**halfProduct + halfProduct + M.**