Java - 理解遞歸

Question

有人可以向我解釋爲什麼打印出來1 2 3 4 5？我想它會打印出4 3 2 1 0，但我的書和日食都說我錯了。

public class whatever { 

    /** 
    * @param args 
    */ 
    public static void main(String[] args) { 
     xMethod(5); 

    } 

    public static void xMethod(int n){ 
     if (n>0){ 
      xMethod(n-1); 
      System.out.print(n + " "); 
     } 
    } 


} 

Answer 1

這是很簡單，這些都是

main 
    xMethod(5) 
     xMethod(4) 
      xMethod(3) 
      xMethod(2) 
       xMethod(1) 
        xMethod(0) 
       print 1 
      print 2 
      print 3 
     print 4 
    print 5 

所以你看到的來電印刷品是1,2,3,4,5

Answer 2

這是正確的代碼

System.out.print(n + " "); 
xMethod(n-1); 

Answer 3

它首先調用自身遞歸只有當遞歸調用結束它打印。 所以，想想它稱之爲第一完成 - 這是當n = 0 則n = 1等

這是一個堆棧，從堆棧中取（遞歸調用後）後打印，這樣的順序顛倒。 如果在放入堆疊前打印，則訂單將被保留。

Answer 4

System.out.print(n + " "); 
xMethod(n-1); 

它將打印5 4 3 2 1.因爲它會首先打印，然後調用xMethod。

對你來說

xMethod(n-1); 
System.out.print(n + " "); 

這將達到終止條件，那麼POP操作並打印。所以1 2 3 4 5

Answer 5

此 xMethod第（n-1）; System.out.print（n +「」）;

應該是：

 System.out.print(n + " "); 
     xMethod(n-1); 

Answer 6

xMethod被稱爲直到n是0。該堆棧將是xMethod(5)->xMethod(4)->xMethod(3)->xMethod(2)->xMethod(1)->xMethod(0)。當它完成xMethod(0)時，它將彈出到xMethod(1)的下一行，打印1。然後重複此操作，直至退出xMethod(5)。

如果你去和擴大各xMethod因爲它是所謂的代碼看起來是這樣的：

{ 
    nA = 5 // What n was set at first 
    if (nA>0){ 
     { 
      // Instead of xMethod(n-1), 
      // we're setting nB to nA - 1 and 
      // running through it again. 
      nB = nA - 1 // nB is 4 

      if (nB>0){ 
       { 
        nC = nB - 1 // nC is 3 
        if (nC>0){ 
         { 
          nD = nC - 1 // nD is 2 
          if (nD>0){ 
           { 
            nE = nD - 1 // nE is 1 
            if (nE>0){ 
             { 
              nF = nE - 1 // nF is 0. 
              if (nF>0){ 
               // This will never execute b/c nF is 0. 
              } 
             } 
             System.out.print(nE + " "); // prints 1 
            } 
           } 
           System.out.print(nD + " "); // prints 2 
          } 
         } 
         System.out.print(nC + " "); // prints 3 
        } 
       } 
       System.out.print(nB + " "); //prints 4 
      } 
     } 
     System.out.print(nA + " "); //prints 5 
    } 
} 

Answer 7

1 public static void xMethod(int n){ 
    2 if (n>0){ //the base condition 
    3   xMethod(n-1); //function is again called with one value less than previous 
    4   System.out.print(n + " "); //now print 
    5  } 
    6 } 

現在看線＃3，由於沒有打印b再次調用該功能，因此從＃3行開始，呼叫再次到達＃1行。這意味着n是5，但是新的呼叫需要n = 4，並且它繼續前進，直到線2指示n現在小於0.

當條件＃2失敗時，它到達第＃ 5，然後是第6行，這意味着函數已經結束執行，此時n = 1。

現在應該在哪裏返回呼叫？在最後一個函數被調用的第＃3行，它將從執行第4行的堆棧彈出，該行打印n的值，即1 2 3 4 5.

Answer 8

這是調用堆棧的結果。以下是n = 5致電後的樣子。由於此調用鏈的底部實際上是堆棧的頂部，所以將您的頭旋轉180度。

• xMethod（5）
  • xMethod（4）
    • xMethod（3）
      • xMethod（2）
        • xMethod（1）
          • xMethod（0）

在遞歸調用，你有兩個案例 - 基本情況和遞歸情況。這裏的基本情況是n == 0，並且不會發生進一步的遞歸。

現在，當我們開始從這些調用回來時會發生什麼？也就是發生了什麼後的遞歸步驟？我們開始做System.out.print()。由於存在防止遞歸和當n == 0打印時的情況，所以我們既不遞歸也不打印。

所以，你得到1 2 3 4 5作爲輸出的原因是由於電話正在從堆棧中彈出的方式。

Answer 9

爲了解釋遞歸是如何工作的，讓我們來看看階乘計算的樣本：

int factorial(int i) { 
    if (i == 0) { 
     return 1; 
    } 
    return i * factorial(i - 1); 
} 

例如，讓我們的5因素值：

int result = factorial(5); 

記住退出值：

if (i == 0) { 
    return 1; 
} 

並返回值：

i * factorial(i - 1) 

只要看看迭代（根據返回值）：

5*factorial(4) -> 4*factorial(3) -> 3*factorial(2) -> 2*factorial(1) -> 1*factorial(0) 

事實上，它是：

5*(4*(3*(2*(1*factorial(0))))) 

原因factorial(4) == 4*factorial(3), factorial(3) == 3*factorial(2)等

最後一次迭代是factorial(0)，等於1（查看退出值）。

在結果：

5*(4*(3*(2*(1*1)))) = 120