CODEWITHSUNDEEP
javascriptarraysalgorithmrecursion
st123
st123

Reputation: 264

why is this recursive solution not working?

The question is the following :

Write a function called productOfArray which takes in an array of numbers and returns the product of them all.

Why does this solution not work:

function productOfArray(arr){
    if (arr.length === 1) {
        return arr[0];
     }
     if (arr.length > 1){
     var last = arr.length - 1
     arr.pop()
     return arr[last] * productOfArray(arr)
}

And is there a better way to solve this recursively without altering the array?

Upvotes: 1

Views: 88

Answers (3)

VLAZ
VLAZ

Reputation: 28981

is there a better way to solve this recursively without altering the array?

Honestly, recursion is not the best way to go about this. Using Array#reduce is the idiomatic way of handling this:

arr.reduce(
    (a, b) => a * b, // apply the operation
    1                // use the identity element for the operation
)                    //   which is the number 1 for multiplication

However, since you're asking for how to do it with recursion without modifying the array, here it is:

function productOfArray(arr) {
  if (arr.length === 0) { //terminal condition
    return 1;             // produce the identity element for multiplication
  }

  return arr[0] //first element
    *           //multiplied by
    productOfArray(arr.slice(1)) //the rest of the elements multiplied
}

const arr1 = [2, 3, 4];
const arr2 = [3, 3, 10];
const arr3 = [5, 3, 7];

console.log("2 * 3 * 4 =", productOfArray(arr1));
console.log("3 * 3 * 10 =", productOfArray(arr2));
console.log("5 * 3 * 7 =", productOfArray(arr3));

console.log("arr1 unchanged:", arr1);
console.log("arr2 unchanged:", arr2);
console.log("arr3 unchanged:", arr3);

Using Array#slice makes a new array, so the initial one is untouched:

const input = [2, 3, 4];
const result1 = input.slice(1);
const result2 = result1.slice(1);
const result3 = result2.slice(1);

console.log("result1:", result1);
console.log("result2:", result2);
console.log("result3:", result3);

And because we terminate with an array of zero elements, we exit after there is nothing left to multiply. With an input of [2, 3, 4] the recursion will effectively evaluate 2 * 3 * 4 * 1.

Note: this implementation does mean that productOfArray([]) (empty array) produces 1. Whether this is acceptable or not may vary - it's a nice neutral value. The benefit is that you do get to finish the recursion with an empty array, otherwise with a terminal condition of arr.length === 1, passing an empty array will result in infinite recursion. Unless it's handled as yet another condition:

if (arr.length === 0) {
  return 1; //or zero? Or whatever makes sense
}

if (arr.length === 1) {
  return arr[0];
}

However, just handling one more condition basically doubles the code of the function. And assuming you want to return 1 anyway, it's unnecessary code. However, it might be worth doing if you want to consider the product of an empty array to be zero.

Finally, the same logic can be implemented using a destructuring of the function's parameter instead of using .slice()

function productOfArray([head, ...tail]) {
  if (head === undefined) {
    return 1;
  }

  return head * productOfArray(tail);
}

const arr1 = [2, 3, 4];
const arr2 = [3, 3, 10];
const arr3 = [5, 3, 7];

console.log("2 * 3 * 4 =", productOfArray(arr1));
console.log("3 * 3 * 10 =", productOfArray(arr2));
console.log("5 * 3 * 7 =", productOfArray(arr3));

console.log("arr1 unchanged:", arr1);
console.log("arr2 unchanged:", arr2);
console.log("arr3 unchanged:", arr3);

As Scott Sayuet points out in a comment the above can even be shortened to:

const prod = ([x, ...xs] = []) => 
    x == undefined ? 1 : x * prod (xs)

Upvotes: 2

phi-rakib
phi-rakib

Reputation: 3302

You are poping before putting it somewhere. Put it in tmp variable and then multiply it.

function productOfArray(arr) {
  if (arr.length === 1) {
    return arr[0];
  }
  if (arr.length > 1) {
    var last = arr.length - 1;
    var tmp = arr[last];
    arr.pop();
    return tmp * productOfArray(arr);
  }
}

console.log(productOfArray([2, 5, 1, 2]));

Upvotes: 0

ibrahim mahrir
ibrahim mahrir

Reputation: 31682

arr[last] will be undefined because the number at that index does not exist anymore because of the pop call. Also, pop will return the item it removes, so you don't need the indexing at all, just use what pop returns like so:

var last = arr.pop();                   // remove the last number from the array and store it in the variable 'last'
return last * productOfArray(arr);      // use it here

Upvotes: 2

Related Questions