我的解決方案遞歸嗎？ （學習遞歸）

Question

我正在練習解決遞歸類的問題。

我解決此站點上的問題：http://www.w3resource.com/javascript-exercises/javascript-recursion-functions-exercises.php

的問題我指的是規定：編寫JavaScript程序來獲取整數的範圍（X，Y）。 實施例：範圍（2,9） 預期輸出：[3，4，5，6，7，8]

之前看溶液我提出了這樣的：

var range = function (start, end) { 
    var result = []; 
    var accumulator = start; 

    var accumulate = function() { 
    accumulator++; 
    if (accumulator === end) { 
     return; 
    } else { 
     result.push(accumulator); 
    } 
    accumulate(); 
    }; 

    accumulate(); 
    return result; 
}; 

將溶液在網站上是這樣的：

var range = function(start_num, end_num) 
{ 
    if (end_num - start_num === 2) 
    { 
    return [start_num + 1]; 
    } 
    else 
    { 
    var list = range(start_num, end_num - 1); 
    list.push(end_num - 1); 
    return list; 
    } 
}; 

我的解決方案在技術上仍然遞歸嗎？最近我有一個類似的測驗答案，我被告知我的解決方案基本上是迭代的。

Answer 1

儘管您使用遞歸，但您只是以遞歸的形式編寫了一個循環。

我打算從純粹的學術觀點來回答這個問題。如果你想避免中間狀態（result），並使用純功能性的結構，我會寫這樣

function range(start, end) { 
    function recRange(current, end) { 
    if (current > end) 
     return []; 
    return [current].concat(recRange(current + 1, end)); 
    } 
    return recRange(start + 1, end - 1); 
} 
console.log(range(2, 9)); 
// [ 3, 4, 5, 6, 7, 8 ] 

如果你看到這裏，我們創建了range功能，遞歸創建一個新的中的新功能數組在每次迭代（記住：這不是高性能的代碼，你可以簡單地使用循環，並有效地解決這個問題）。

遞歸的基本條件是current < end。一旦滿足，遞歸停止並返回一個空數組。在所有級別中，具有current值的新數組與遞歸調用的結果連接在一起。因此，呼叫的評價大致瞭解這樣

[3].concat(recRange(3 + 1, end)); 
[3].concat([4].concat(recRange(4 + 1, end))); 
... 

末，當遞歸解開，該值將是這樣的

[3].concat([4].concat([5].concat([6].concat([7].concat([8].concat([])))))) 
[3].concat([4].concat([5].concat([6].concat([7].concat([8]))))) 
[3].concat([4].concat([5].concat([6].concat([7, 8])))) 
[3].concat([4].concat([5].concat([6, 7, 8]))) 
[3].concat([4].concat([5, 6, 7, 8])) 
[3].concat([4, 5, 6, 7, 8]) 
[3, 4, 5, 6, 7, 8] 

，並且將作爲結果返回。

Answer 2

我的解決方案在技術上仍然是遞歸的嗎？

是。你正在使用尾遞歸;然而，由於沒有任何參數被傳遞到accumulate（），我可以看到爲什麼有人會說它基本上是迭代的。您可以輕鬆地用循環替換遞歸調用。遞歸算法通常利用堆棧。

由於Javascript的關閉，與其他語言（如C++或Java或C＃）相比，很難理解JavaScript中的遞歸概念。

要理解遞歸，您必須先了解遞歸。 :)

Answer 3

爲了讓您的解決方案遞歸的，它應該返回一些價值並以某種方式結合遞歸調用的結果形成原始調用的返回值。

讓我說明了一個例子，通過修改您的解決方案：

var range = function (start, end) { 

    var accumulate = function (accumulator) { 
    if (accumulator === end - 1) { 
     return [accumulator]; // Stop condition 
    } else { 
     // Recursive block 
     var result = accumulate(accumulator+1); // recursive call 
     result.unshift(accumulator); // combine result 
     return result 
    } 
    }; 

    return accumulate(start); 
}; 

修改後的累積函數將返回一個元素列表的停止條件，它處理最簡單的情況下，當蓄電池到達最後一個值返回。

在示例range(2,9)中，停止條件將返回[8]。

然後在主叫方，遞歸塊

 var result = accumulate(accumulator+1); 
     result.unshift(accumulator); 
     return result 

將採取列表[8]，並preprend的accumulator（7）的電流值，所以它會返回[7,8]。

...和accumulator(7)調用者，將獲得[7,8]和值6 preprend到列表，返回[6,7,8]。

最後，原來致電accumulator(2)的電話會產生預期結果[2,3,4,5,6,7,8]。