# 8.5 Recursive Multiply

### yuliakononchuk ・3 min read

CrackingTheCodingInterview (6 Part Series)

######
**NB: This post is a part of the series of solving the challenges from 'Cracking The Coding Interview' book with JavaScript. I'll post only the challenges I've figured out on my own - and will try to describe my reasoning behind the solution. Any ideas on how to solve it differently or in a more optimal way are very welcome 😊**

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

The easiest approach is to add each number one by one. We can choose the smallest number out of 2 arguments - and add the other number to it, one number at a time:

```
function multiply(a,b) {
const max = Math.max(a,b);
const min = Math.min(a,b);
function recursiveMultiply(number, multiplier) {
return (
multiplier === 1 ?
number :
number + recursiveMultiply(number, multiplier - 1)
)
}
return recursiveMultiply(max, min);
}
```

This algorithm uses addition *n* times, where *n* is the smallest of 2 arguments of multiplication function. Also the time complexity of this algorithm is *O(n)*: we need to do something n times. Can we do better than that? The task requires to use the minimal amount of additions - and the time complexity can probably be improved as well 🤔

The second approach that I took seems to be a bit more optimal indeed. Similarly as in the previous case, I consider the bigger argument to be multiplicand (let's call it *m*), and the smaller one - multiplier (*n*). But in addition to this, I also create an array of pre-calculated values, in which I fill in only the indices that represent the power of 2. For instance, for *m = 9* and *n = 7* the array will look like this:

Each index in this array actually equals a multiplier of `m`

: eg a number at index 4 would actually be *m * 4* (or, in other words, *(m + m) + (m + m)*). We can do that with *log _{2}n* operations: each time we will be doubling the array length and the max number.

Note that we're stopping when the `index * 2 <= n`

, and there's a reason for that. The sum of (some of the) numbers in this array will be used to get to the final result (`9 * 7`

, in our example). We're stopping at the index `4`

, which means the max number we'll calculate for the array would be `9 * 4`

. If we would go on and calculate the next number as well, the next number would be `9 * 4 + 9 * 4 = 9 * 8`

- which would exceed the `9 * 7`

that we need to calculate at the end (`9 * 8`

can not one of the numbers that sum up to `9 * 7`

).

The next thing to do is to actually (recursively) use these pre-calculated numbers, and that is what `recursiveMultiply()`

function does in the code below:

```
function multiply(a,b) {
const max = Math.max(a,b);
const min = Math.min(a,b);
let values = [, max]
let index = 1;
//Fill in array of values for all indices = 2^n
while (index * 2 <= min) {
const newIndex = index * 2;
values[newIndex] = values[index] + values[index];
index = newIndex;
}
// Recursively add the numbers from the array of values
function recursiveMultiply(number, multiplier, valuesArray){
if (multiplier === 0) { return 0; }
const multLog = Math.log2(multiplier);
const closestMaxIndex = Math.pow(2, Math.floor(multLog));
const rest = recursiveMultiply(number, multiplier - closestMaxIndex, valuesArray);
return valuesArray[closestMaxIndex] + rest;
}
return recursiveMultiply(max, min, values);
}
```

For `9 * 7`

, we would start with index 7 (the value of *n*) and search for the closest number that would be a power of 2 (smaller or equal to 7). 7 is not a power of 2, so we need to go down until 4. This chunk does exactly that:

```
const factorLog = Math.log2(factor);
const closestMaxIndex = Math.pow(2, Math.floor(factorLog));
```

Finally, we take the number from the pre-calculated array that is stored under `closestMaxIndex`

index (index 4 in this case) - and sum up this number with the rest that still needs to be calculated. So, if we needed to calculate `9 * 7`

, and `9 * 4`

is already known, the rest to be calculated is `9 * 3`

: index 3 will be an argument of next iteration of `recursiveMultiply`

. With the next recursive steps we will get `9 * 2`

and `9 * 1`

- and those numbers will sum up exactly to the result that we need to reach: `(9 * 4) + (9 * 2) + (9 * 1) = 9 * 7`

.

When looking at complexity, this alternative solution uses only *2 * log _{2}n* sums - and has a

*O(log*) time complexity 🙌 The bigger the argument get, the more benefit will this approach bring.

_{2}nCrackingTheCodingInterview (6 Part Series)