瞭解這個遞歸函數

Question

你好同胞程序員。

一段時間以來，遞歸編程一直是我至少理解的事情之一。因爲我決定，我需要用一些時間，理解和編程幾個基本的例子。問題是我有這個任務，我解決了，但不太明白它是如何工作的。 -

如果有人能幫助我理解它，我將不勝感激。

謝謝，提前。

• Teilmann

分配：

甲dominopiece有大小2 * 1。一塊板子的長度爲n，寬度爲2.創建一個返回方法的遞歸方法，而一個板子可以被dominopieces覆蓋。

我的方法：

public static int dominobrik(int n){ 
    int sum; 

    if(n >= 0 && n <= 2){ 
     sum = n; 
    } else { 
     sum = dominobrik(n-1) + dominobrik(n-2); 
    } 

    return sum; 

} 

Answer 1

爲了幫助人們理解這種遞歸調用，我真的認爲很好地打印出來的東西真的有幫助。

該程序的輸出已根據遞歸深度縮進。

在這裏做時要達到爲5，寬度所有溶液中取出8次的路徑：

dominobrik(n-2) + dominobrik(n-1) 

（請注意，對於每一個新的路徑，遞歸調用第一將兩個橫向件如果可能的話）

（也注意，這是比你發佈的代碼，你寫了不同的（N-1），然後再（N-2），但它確實沒有太大變化）

So far the board is: 
..... 
..... 

    So far the board is: 
    --... 
    --... 

      So far the board is: 
      ----. 
      ----. 

       Finished board: 
       ----| 
       ----| 


      So far the board is: 
      --|.. 
      --|.. 

       Finished board: 
       --|-- 
       --|-- 


       So far the board is: 
       --||. 
       --||. 

        Finished board: 
        --||| 
        --||| 


    So far the board is: 
    |.... 
    |.... 

      So far the board is: 
      |--.. 
      |--.. 

       Finished board: 
       |---- 
       |---- 


       So far the board is: 
       |--|. 
       |--|. 

        Finished board: 
        |--|| 
        |--|| 


      So far the board is: 
      ||... 
      ||... 

       So far the board is: 
       ||--. 
       ||--. 

        Finished board: 
        ||--| 
        ||--| 


       So far the board is: 
       |||.. 
       |||.. 

        Finished board: 
        |||-- 
        |||-- 


        So far the board is: 
        ||||. 
        ||||. 

         Finished board: 
         ||||| 
         ||||| 

Answer 2

在基本情況下，如果n = 1，只有1的方式來安排主板上的多米諾骨牌，那就是水平。凡n = 2，有2種方法來安排多米諾骨牌。你既可以垂直排列，也可以水平排列。

對於情況下n = 3，3種方式是：

1. 1水平地橫跨頂部，和兩個垂直下方;
2. 1水平橫跨底部，2垂直位於上方;
3. 或全部3個水平堆疊。

注意，在n = 3情況下，你有反覆兩者的n = 2箱子的安排，但這些，你已經添加從n = 1情況安排。回想一下，n = 1唯一有效的安排是一個水平多米諾骨牌。 n = 3中的每個案例都至少有1個水平多米諾骨牌。

您可以將其擴展到n = 4的情況。採取上述所有可能的組合n = 3，然後將所有組合添加到n = 2，在給出問題約束的情況下適當堆疊它們。

我希望我能說明這一點，但它可能有助於在平方紙上繪出它們。

Answer 3

不要說你知道n的答案，你想要的答案爲n + 1。

對於n的一些解決方案，您將最後一個多米諾骨牌垂直放置，對於其他多米諾骨牌，最後兩個多米諾骨牌將水平堆疊放置。

如果最後兩個多米諾骨牌是水平的，你所能做的就是垂直添加你的n + 1多米諾骨牌。但是，如果最後一個多米諾骨牌是垂直的，那麼您也可以垂直添加它，或者您可以用之前的多米諾骨牌水平翻轉它。

我不僅會跟蹤給定的n有多少種解決方案，還會跟蹤多少個解決方案以最後一個多米諾骨牌水平/垂直終止。

我會讓你找出其餘的，因爲這是作業。另外我還沒有真正想出完整的解決方案。這可能會變成你所發佈的解決方案。