CODEWITHSUNDEEP
javascriptarraysrecursion
Jordan Chong
Jordan Chong

Reputation: 23

Javascript - Can you use .shift() to alter an array during recursion?

I wrote a recursive function to determine if an array contained the necessary elements to be added and form a target number. While doing so however I encountered an error while trying to remove the first element in the array using .shift() (line 8):

function findCombo(collection, target){
  if(target === 0){
   return true; 
  } else if(collection.length === 0){
   return false; 
  } else{
    var next = collection[0];
    //collection.shift(); **does not work**
    collection = collection.slice(1); //**works**
    return findCombo(collection, target - next) 
           || findCombo(collection, target);
  }
}

When I realized that collection.shift() was the problem I tried changing the array to collection.slice(1) and the program now works. Even now though I don't understand why .shift() did not apply the desired result. Does anyone have any idea why?

Upvotes: 0

Views: 271

Answers (2)

Bergi
Bergi

Reputation: 665256

The problem is that you have only a single collection array that is shared by all calls to findCombo, and shift mutates the array. This means that when the first recursive call findCombo(collection, target - next) empties the array, the second recursive call findCombo(collection, target) will find the (very same) array to be empty, altough the caller did not intend to do that. By using slice, the function doesn't harm the array that was given to it.

You can avoid this problem by restoring the array to its original value after the recursive calls:

var next = collection[0];
collection.shift();
var res = findCombo(collection, target - next) || findCombo(collection, target);
collection.unshift(next);
return res;

but that is a bit ugly. A better idea is to use an extra index argument for the next position to be tried, and not to mutate or clone the array at all:

var next = collection[try];
return findCombo(collection, target - next, try+1) || findCombo(collection, target, try+1);

Upvotes: 1

Arun P Johny
Arun P Johny

Reputation: 388416

Because shift() modifies the original collection object, so when the findCombo(collection, target) method is executed after the findCombo(collection, target - next) the collection object will be empty.

function findCombo(collection, target) {
  snippet.log(target + ':' + collection)
  if (target === 0) {
    return true;
  } else if (collection.length === 0) {
    return false;
  } else {
    var next = collection[0];
    collection.shift(); //**does not work**
    //collection = collection.slice(1); //**works**
    return findCombo(collection, target - next) || findCombo(collection, target);
  }
}
snippet.log(findCombo([1, 2, 3, 4, 5], 20));
<!-- Provides the `snippet` object, see http://meta.stackexchange.com/a/242144/134069 -->
<script src="http://tjcrowder.github.io/simple-snippets-console/snippet.js"></script>

Upvotes: 1

Related Questions