Please help me understand this recursion function

Question

I'm trying to understand this recursion function and better educate myself on recursion in general. I can't seem to follow how this code does it's thing. I'm hoping someone can walk me through this so I can understand what's going on. This function takes the largest value of an array and checks to see if any combination of numbers add up to this value.

function ArrayAdditionI(arr) {
  arr.sort(function(a,b){  //sort array;
    return a - b;
  });
  console.log('Sorted Array: ['+arr+']');
  var largest = arr.pop();  //grab last value aka largest

  function recursion(target, array){
    if(array.length === 0) {  //if array is empty return boolean
        return target === 0;
    }
    var n = array[0];       //first value of array
    array = array.slice(1);
    console.log('Array: [' +array+']');
    console.log('Target: '+target);
    return recursion(target,array) || recursion(target - n, array);   //not exactly sure about this ???
  }
  return recursion(largest,arr);  //call recursion function
}

console.log(ArrayAdditionI([4,6,21,10,20,1]));

Here are the results I get from calling this. I've commented on them to show where I get lost.

Sorted Array: [1,4,6,10,20,21] 
Array: [4,6,10,20]  //first value and largest value removed
Target: 21          //target highest value
Array: [6,10,20]    //first value removed again
Target: 21          //still 21
Array: [10,20]      //another value removed
Target: 21
Array: [20]         //last value in array
Target: 21
Array: []           //empty array.. Why did this not return a false???
Target: 21          
Array: []           //why is it doing this twice?
Target: 11          //where in the world did this come from. I see 21 - 10 but how did that happen?
Array: [20]         //When did this value get added back to the array?
Target: 15          //Totally lost at this point...
Array: []
Target: 15
Array: []
Target: 5
Array: [10,20]      //Where are these values coming from?
Target: 17
Array: [20]
Target: 17          //why does the target keep changing??
Array: []          
Target: 17
Array: []           
Target: 7
Array: [20]
Target: 11          //from 17 to 7 then back to 11?
Array: []
Target: 11
Array: []           //Empty arrays still not returning false??
Target: 1
Array: [6,10,20]    //No idea how these combinations are being generated.
Target: 20
Array: [10,20]
Target: 20
Array: [20]
Target: 20
Array: []
Target: 20
true                //Right answer but how?

Answer 1

I hope this gets you on the right track:

Array: [] //empty array.. Why did this not return a false???

Because the array wasn't empty when the check was done. It became empty when the slice call removed the last item. The calls that follow will return false when array is empty going into the function.

Array: [] //why is it doing this twice?

Because of the expression recursion(target,array) || recursion(target - n, array). Each of them are called with an array with a single item, and will show an empty array when they remove the item.

Target: 11 //where in the world did this come from. I see 21 - 10 but how did that happen?

That's the recursion(target - n, array) being called when target == 21 and n == 10.

Array: [20] //When did this value get added back to the array?

It's not added back, it's a different array. The recursion has reached its limit and it taking a step back to a previous state to try the next possibility.

Target: 15 //Totally lost at this point...

That's the recursion(target - n, array) being called when target == 21 and n == 6.

Array: [10,20] //Where are these values coming from?

That's another step back. Each recursion level stores the state on the stack, so that it can back up to the previous state.

Target: 17 //why does the target keep changing??

Because the code is trying different combinations into the path of the recursion(target - n, array) call. The function is called with a new value for target.

Array: [] //Empty arrays still not returning false??

Yes, they do. Each empty array ends one possible combination, and makes the code back up and try the next combination.

Array: [6,10,20] //No idea how these combinations are being generated.

By tracking back to the state where the array was [4,6,10,20] and slicing off the 4.

true //Right answer but how?

By going into every possible combination and out again until the right one was found.

Answer 2

I'm not sure if you can consider it as an answer, but check it out. This is your own code without hacks and with better diagnostics:

function ArrayAdditionI(arr) {
    arr.sort(function (a, b) { //sort array;
        return a - b;
    });
    console.log('Sorted Array: [' + arr + ']');
    var largest = arr.pop(); //grab last value aka largest

    function recursion(target, array, level) {
        level++;
        console.log("Level: "+level);
        console.log("Entering: " + target + " [" + array + "]");
        if (array.length === 0) { //if array is empty return boolean
            console.log("Array empy, is target 0? " + (target === 0));
            result = (target === 0);
        } else {
            var n = array[0]; //first value of array
            array = array.slice(1);
            console.log('Calling return: target=' + target + ', n=' + n + ', ' + '[' + array + ']');
            var result = recursion(target, array, level);
            if (result === true){ 
                console.log("Path 1: true");
            } else {
                result = recursion(target - n, array, level);
                console.log("Path 2: "+result);
            }
        }
        console.log('Returning level='+level+': '+result);
        console.log(); //spacer
        level--;
        return result;
    }
    return recursion(largest, arr, 0); //call recursion function
}