java - 理解这个递归函数

Question

各位程序员大家好。

一段时间以来，递归编程一直是我了解最少的事情之一。因此我决定，我需要花一些时间来理解和编写一些基本示例。问题是我已经解决了这个任务，但不太明白它是如何工作的 -.-

如果有人能帮助我理解它，我将不胜感激。

提前致谢。

• 泰尔曼

作业:

多米诺骨牌的大小为 2*1。一 block 木板的长度为 n，宽度为 2。创建一个递归方法返回方法数，而一 block 木板可以被多米诺骨牌覆盖。

我的方法:

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:
                         |||||
                         |||||