JavaScript的遞歸OR如何工作？

問題：數組中任何數字的組合總和數組的最大數量？JavaScript的遞歸OR如何工作？

有一個Coderbyte答案，original source，我不能得到我的頭。我試圖在行動中想象這個功能，但它對我來說沒有意義。這裏是：

function ArrayAdditionI(arr) { 
    arr.sort(function(a,b){ 
    return a - b; 
    }); 
    var largest = arr.pop(); 
    function recursion(target,array){ 
    if(array.length === 0){ 
     return target === 0; 
    } 
    var n = array[0]; 
    array = array.slice(1); 
    return recursion(target,array) || recursion(target - n, array); 
    } 
    return recursion(largest,arr);   
}

因此，給定：

[3,5,-1,8,12]

它應該輸出：

"true"

我的解釋是，return語句會調用各項功能的||左右，隨後從這些等產生的，直到陣列的長度爲0。但是，它是如何檢查最大數量的適當加數？

來源

2016-07-06 pward

雖然不完全一樣，我鼓勵你看看[從雄辯的Javascript的Javascript遞歸（http://stackoverflow.com/q/26205376/1048572）以及從那裏鏈接的其他問題 – Bergi

請注意，'||'運算符沒有特別與遞歸的概念有關。 – Pointy

線

return recursion(target,array) || recursion(target - n, array);

呼叫recursion()第一與目標總和，並與汽提掉所述第一元件的陣列。如果返回true（因爲target爲零且數組爲空），則||的右側將調用而不是。只有當第一次通話返回undefined或false時，纔會進行右側通話。

所以整個過程是首先找到最大的值，然後調用遞歸過程和列表的其餘部分。重複地，遞歸例程撬開第一個值，然後檢查在列表的其餘部分是否存在等於目標的總和或如果總和等於目標減去即撬開第一值在列表的其餘部分。

它有助於略微修改功能，使行爲可以追溯到：

function ArrayAdditionI(arr) { 
    arr.sort(function(a,b){ 
    return a - b; 
    }); 
    var largest = arr.pop(); 
    function recursion(target,array){ 
    if(array.length === 0){ 
     return target === 0; 
    } 
    var n = array[0]; 
    array = array.slice(1); 
    console.log("target: " + target + " n: " + n); 
    var r1 = recursion(target,array), r2 = recursion(target - n, array); 
    console.log("(" + target + ", " + n + ") left: " + r1 + " right: " + r2); 
    return r1 || r2; 
    } 
    return recursion(largest,arr);   
}

如果調用與樣品陣列：

ArrayAdditionI([3,5,-1,8,12]);

你會得到如下跟蹤：

target: 12 n: -1 
target: 12 n: 3 
target: 12 n: 5 
target: 12 n: 8 
(12, 8) left: false right: false 
target: 7 n: 8 
(7, 8) left: false right: false 
(12, 5) left: false right: false 
target: 9 n: 5 
target: 9 n: 8 
(9, 8) left: false right: false 
target: 4 n: 8 
(4, 8) left: false right: false 
(9, 5) left: false right: false 
(12, 3) left: false right: false 
target: 13 n: 3 
target: 13 n: 5 
target: 13 n: 8 
(13, 8) left: false right: false 
target: 8 n: 8 
(8, 8) left: false right: true 
(13, 5) left: false right: true 
target: 10 n: 5 
target: 10 n: 8 
(10, 8) left: false right: false 
target: 5 n: 8 
(5, 8) left: false right: false 
(10, 5) left: false right: false 
(13, 3) left: true right: false 
(12, -1) left: false right: true

因此，||的左側表示意願查看是否可以在考慮其中一個值時找到而沒有的總和，並且右側考慮您是否可以找到總和，假定其中一個值是其中一個組成部分。從前幾行開始，您會看到遞歸跳過前四個值，從最小到最大，直到最後一次調用的數組爲空。目標值仍然是12，所以這沒有奏效。

然後是包含價值的嘗試5（當target是12），給人的7的目標，並與剛剛8它的列表;那也不管用。繼續，只有當流程到達原始調用的右側時，target爲12和n爲-1，事情纔開始查找。因爲12 - -1是13，並且13 - 5是8，並且8 - 8是0，所以有一組值總計到目標。

來源

2016-07-07 00:00:18 Pointy

等等，我仍然沒有得到如何計算任何總和。 – pward

@pward *和*沒有被計算，至少不是直接計算。關鍵是'target - n'的東西。當'n' *確實參與時，這會導致該過程嘗試並找到可能的一組值;左側是檢查'n' *不*參與的時間。 – Pointy

但是如果'n'在第一次出現後被刮掉，那麼函數將如何檢查所有可能的數組組合？ – pward

願這有助於理解||：

true || 1 // => true 
false || 1 // => 1 


function returnTrue() { 
    return true; 
} 

function returnFalse() { 
    return false 
} 

returnTrue() || 1 // => true 
returnFalse() || 1 // => 1

來源

2016-07-07 00:16:45 webdeb

JavaScript的遞歸OR如何工作？

回答

相關問題