8.5 Recursive Multiply
Tags: javascript, programming, algorithms, recursion
Published: 2019-10-23 16:58:12

######**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: 

```javascript
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:

![Alt Text](https://thepracticaldev.s3.amazonaws.com/i/imwoxdlg70co9xdzndu0.png)

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<sub>2</sub>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: 

```javascript
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:

```javascript
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<sub>2</sub>n_ sums - and has a _O(log<sub>2</sub>n_) time complexity 🙌 The bigger the argument get, the more benefit will this approach bring.