javascript - 为什么这个回溯递归不去其他分支？

Question

给定一个数组和一个目标（数字），我必须确定是否可以通过添加数组中的元素来达到目标​​。这是我的代码（在 javascript 中）和一些结果：

function check(goal,array) {

  function add(sum, array) {
    if (sum == goal)
      return true;
    else if ((sum > goal)||(!array[0]))
      return false;
    else
        console.log(sum); // check where we are 
      return add(sum + array.shift(),array) || add(sum,array);
  }
  return add(0,array);
}

调用 check(6,[1,3,5]) 后我期望 add() 堆栈发生什么

add(0,[1,3,5])   // log 0
    add(1,[3,5])    //log 1  
        add(1+3,[5])    //log 4
            add(1+3+5,[])  //return false
            add(1+3,[])    //return false
        add(1,[5])  //log 1
            add(1+5,[])   //return true
            add(1,[])       

    add[0,[3,5])
        add(0+3,[5])
            add(0+3+5,[])
            add(0+3,[])
        add(0,[5])  
            add(0+5,[])
            add(0,[])

实际结果：

check(6,[1,3,5])
false
0
1
4
check(3,[1,3,5])
false
0
1
1

它永远不会离开第一个分支！为什么 ？ 编辑： 好的，根据建议，我想最好避免将数组作为参数传递：

function check(goal,array) {

  function add(sum, i) {
    if (sum == goal)
      return true;
    else if ((sum > goal)||(i==array.length))
      return false;
    else
        console.log(sum);
      return add(sum + array[i],i+1) || add(sum,i+1);
  }
  return add(0,0);
}

它在这里工作正常。

Answer 1

它与传递的数组相同，在第一个分支之后它将变为空，因此递归将完成。试一试：

function check(goal,array) {
    function add(sum, array) {
        if (sum == goal)
            return true;
        else if ((sum > goal)||(!array[0]))
            return false;
        else
            print(sum);
        array = array.slice();
        return add(sum + array.shift(),array) || add(sum,array);
    }
    return add(0,array);
}