這個遞歸如何工作？

Question

這是從鋒的Javascript的例子：

通過從數字1開始並重復地或者通過3加入5或 乘法，可以產生新的數的無限量。 你會如何編寫一個函數，給定一個數字，試圖找出產生該數字的加法和乘法序列的一個 序列？

我無法理解遞歸在這裏工作的方式，想知道是否有人可以寫出幾次如何找到調用或其他解釋。

function findSequence(goal) { 
    function find(start, history) { 
    if (start == goal) 
     return history; 
    else if (start > goal) 
     return null; 
    else 
     return find(start + 5, "(" + history + " + 5)") || 
      find(start * 3, "(" + history + " * 3)"); 
    } 
    return find(1, "1"); 
} 

console.log(findSequence(24)); // => (((1 * 3) + 5) * 3) 

Answer 1

函數運行一個相當簡單的brute force search與backtracking：在每次調用級別它試圖將5的數目，並查看是否從所得的數開始讓你的目標。如果是，則返回結果;否則，該數字乘以3，並且從該新數字繼續搜索目標。隨着遞歸的進行，產生該數字的表達式的文本表示被傳遞給下一個調用級別。

爲14搜索去如下：

(1, "1") 
(5, "1+5") 
(10, "(1+5)+5") 
(15, "((1+5)+5)+5") <<= Fail 
(30, "((1+5)+5)*3") <<= Fail 
(15, "(1+5)*3") <<= Fail 
(3, "1*3") 
(8, "(1*3)+5") 
(13, "((1*3)+5)+5") 
(18, "(((1*3)+5)+5)+5") <<= Fail 
(39, "(((1*3)+5)+5)*3") <<= Fail 
(24, "((1*3)+5)*3") <<= Fail 
(9, "(1*3)*3") 
(14, "((1*3)*3)+5) <<= Success! 

Answer 2

此函數以1開始，然後嘗試要麼添加5至它或者通過3乘以如果是等於目標，函數結束並且打印出表達找到。如果不是，則會使用該級別的值遞歸調用自身，直到找到匹配或值變得太高。

這有幫助嗎？

Answer 3

有人可能會寫出幾次如何找到調用。

在這裏你去：

find(1, "1") -> find(3, "(1 * 3)") 
      -> find(8, "((1 * 3) + 5)") 
      -> find(24, "(((1 * 3) + 5) * 3)") 

Answer 4

簡單地說，find(start,goal)將遞歸只要goal值尚未達到調用。在每次調用中，當前編號將被多重加3或增加5. history變量將字符串與執行的操作一起存儲。當前操作會在每次迭代中附加到該字符串。

說明：

function findSequence(goal) { 

    // This inner function will be called recursively. 
    // 'history' is a string with the current operations "stack" 
    function find(start, history) { 
    if (start == goal)   // if goal is achieved, simply return the result 
           // ending the recursion 
     return history; 
    else if (start > goal)  // return null to end the recursion 
     return null; 
    else 
     // One of the 'find' calls can return null - using || 
     // ensures we'll get the right value. 
     // Null will be returned if 'start+5' or 'start*3' is 
     // greater than our 'goal' (24 in your example). 
     // The following line is where a recursion happens. 
     return find(start + 5, "(" + history + " + 5)") || 
      find(start * 3, "(" + history + " * 3)"); 
    } 

    // Start with '1' 
    return find(1, "1"); 
} 

Answer 5

加入5和由3像二叉樹相乘的無限組合的思考。頂部是最容易計算的數字，1（實際上是「無需採取措施」的答案）。向下一級，左側是1+5，右側是1*3。在每個級別上，公式解析爲新的值（具有更復雜的歷史）。這個公式導航通過那棵樹，直到找到一個等於goal的節點。如果樹的某個分支上的節點產生的值大於目標值，那麼它將返回空值（從而停止進一步回收該分支，這是因爲兩個操作都只會增加值，所以一旦最終結果大於沒有結果指向繼續尋找），如果一個節點的值等於目標，那麼它將作爲答案返回（以及它用於達到的路徑）。當值小於那麼兩條路徑都可能有答案，所以它會在每條路徑上調用find。這裏是JavaScript的「truthy」布爾邏輯進來的地方。通過使用||（OR）運算符，JavaScript將首先查看樹的+5側。如果返回0或空值，則將執行另一個調用（查看*3）。如果任何回報評估爲非false值，則它將返回到堆棧並且搜索將結束。

Answer 6

的find本體具有三個出口的路徑，兩塊對應於停止遞歸該遞歸一個條件和一個：

if (start == goal) 
    return history; // stop recursion: solution found 
else if (start > goal) 
    return null; // stop recursion: solution impossible 
else 
    // ... 

第三條路實際上是一個「分支」，因爲它遞歸兩次（一次嘗試加法，一次乘法）：

return find(start + 5, "(" + history + " + 5)") || 
     find(start * 3, "(" + history + " * 3)"); 

那麼這裏發生了什麼？

首先，請注意，這兩個find調用中的每一個都將評估爲非空字符串（操作歷史）或null。由於非空字符串是「真值」，並且null是「僞造」值，因此我們利用這一點將它們與||運算符結合起來;此運算符評估爲第一個操作數是否真實，否則評估爲第二個操作數。

這意味着首先會評估第一個遞歸分支（+5）。如果有一系列以加5開始並達到目標的操作序列，則將返回該序列的描述。否則，如果有一個從3開始到達目標的序列，那麼將返回該歷史記錄的描述。

如果沒有辦法達到目標，那麼返回值將是第二個分支產生的null。

Answer 7

要學習這一點，最好的方法是跟蹤JavaScript調試器中的代碼。

您之前使用過調試器嗎？這真的很有趣，也很有啓發性，也很容易。

只需添加一條debugger;語句，您希望代碼停止。

debugger; 
console.log(findSequence(24)); 

現在在Chrome與開發工具打開加載頁面：您打電話之前findSequence()一個好地方會。您的代碼將停止在該行debugger;行。找到可讓您進入代碼的按鈕（位於Watch Expressions面板右上方）。點擊該按鈕進入findSequence()呼叫。每次單擊它時，它都會進入下一行代碼，其中包括進入每次遞歸調用。

只要代碼停止，您可以將鼠標懸停在任何變量上查看它，或者查看右側面板中的變量。還有一個Call Stack可以顯示你在遞歸調用中的確切位置。

我確定有人可以向你解釋遞歸，但是如果你通過在調試器中逐步調試代碼來體驗它，你將學到更多東西。

Answer 8

如果你擺脫漂亮的印刷材料，該代碼是一個小更易於閱讀：

function findSequence(goal) { 
    function find(start) { 
     if (start == goal) { 
      return true; 
     } else if (start > goal) { 
      return false; 
     } else { 
      return find(start + 5) || find(start * 3); 
     } 
    } 

    return find(1); 
} 

外功能，findSequence，動態地創建一個名爲find一個新函數，其中goal摘自父函數的範圍。爲清晰起見，您可以將其重寫爲：

function findSequence(start, goal) { 
    if (start == goal) { 
     return true; 
    } else if (start > goal) { 
     return false; 
    } else { 
     return findSequence(start + 5, goal) || findSequence(start * 3, goal); 
    } 
} 

現在，您可以更清楚地看到發生了什麼。遞歸步驟在最後的return語句中，該語句在每個步驟都嘗試start + 5和start * 3並選擇最終返回true的分支。

手動按照findSequence(1, 23)的邏輯，你就會明白它是如何工作的。

Answer 9

讓我們離開歷史參數，我們稍後再討論它。

遞歸擴展爲所有可能的操作。 它以1作爲start開頭。

1. 我們首先檢查，如果我們到達了目的地：goal，如果我們did-返回true，這意味着我們所採取的方法是正確的。

2. 其次，我們問 - 我們是否超越了界限（goal）？如果我們這樣做了，我們應該返回false，因爲這條道路不能幫助我們。

3. 否則，讓我們嘗試我們兩家possiblities（我們使用或者是因爲我們需要至少一個）：

   • 調用相同的功能，但設置start到start + 5
   • 調用相同的功能，但設置start到start * 3

歷史變量保持我們採取的步驟。所以如果一個函數調用識別出它返回它start == goal。

Answer 10

goal是你的目標，它的設置爲24

goal == 24 

現在有這樣的內部函數find()檢查，看看是否start等於24;不是。 它還檢查，看看是否開始是大於24，這也是不正確的，

find(1 "1") 
1 == 24 //false 
1 > 24 //false 

所以它擊中它調用再次找到else語句，這就是從else if()空值的用武之地。如果返回值爲null，則它調用||直到它最終找到正確的答案。

return find(6, "(1 + 5)") 
     find(11, "((1 + 5) + 5)") 
     find(16, "(((1 + 5) + 5) +5)") 
     find(21, "((((1+5) + 5) + 5) +5)") 
     //next one returns null! 
     //tries * by 3 on 21, 16, and 11 all return null 

因此它切換到||。

return find(3, "(1 * 3)") 
     find(8, "((1 * 3) +5)") 
     //some calls down +5 path but that returns null 
     find(24, "(((1 * 3) + 5) * 3)") 

終於！我們有一個真實的回報，並且我們記錄了我們在歷史變種var中所取的路徑。

Answer 11

你只需要創建調用樹摸不着頭腦：

findSequence(24) 
    find(1, "1") 
     find(1 + 5, "(1 + 5)") 
      find(6 + 5, "((1 + 5) + 5)") 
       find(11 + 5, "(((1 + 5) + 5) + 5)" 
        find(16 + 5, "((((1 + 5) + 5) + 5) + 5)" 
         find(21 + 5, "(((((1 + 5) + 5) + 5) + 5) + 5)" 
          start > goal: return null 
         find(21 * 3, "(((((1 + 5) + 5) + 5) + 5) + 5)" 
          start > goal: return null 
        find(16 * 3, "((((1 + 5) + 5) + 5) * 3)" 
         start > goal: return null 
       find(11 * 3, "(((1 + 5) + 5) * 3)" 
        start > goal: return null 
      find(6 * 3, "((1 + 5) * 3)") 
       find(18 + 5, "(((1 + 5) * 3) + 5)") 
        find(23 + 5, "((((1 + 5) * 3) + 5) + 5)") 
         start > goal: return null 
        find(23 * 3, "((((1 + 5) * 3) + 5) * 3)") 
         start > goal: return null 
       find(18 * 3, "(((1 + 5) * 3) * 3)") 
        start > goal: return null 
     find(1 * 3, "(1 * 3)") 
      find(3 + 5, "((1 * 3) + 5)") 
       find(8 + 5, "(((1 * 3) + 5) + 5)") 
        find(13 + 5, "((((1 * 3) + 5) + 5) + 5)") 
         find(18 + 5, "(((((1 * 3) + 5) + 5) + 5) + 5)") 
          find(23 + 5, "((((((1 * 3) + 5) + 5) + 5) + 5) + 5)") 
           start > goal: return null 
          find(23 + 5, "((((((1 * 3) + 5) + 5) + 5) + 5) + 5)") 
           start > goal: return null 
         find(18 * 3, "(((((1 * 3) + 5) + 5) + 5) * 3)") 
          start > goal: return null 
        find(13 * 3, "((((1 * 3) + 5) + 5) * 3)") 
         start > goal: return null 
       find(8 * 3, "(((1 * 3) + 5) * 3)") 
        return "(((1 * 3) + 5) * 3)" 
      find(3 * 3, "((1 * 3) * 3)") 
       find(9 + 5, "(((1 * 3) * 3) + 5)") 
        find(14 + 5, "((((1 * 3) * 3) + 5) + 5)") 
         find(19 + 5, "(((((1 * 3) * 3) + 5) +5) + 5)") 
         return "(((((1 * 3) * 3) + 5) +5) + 5)" 
         find(19 * 3, "((((1 * 3) * 3) + 5) *3)") 
          start > goal: return null 
       find(9 * 3, "(((1 * 3) * 3) * 3)") 
        start > goal: return null