問題遞歸 - 我不明白爲什麼我得到一個反向輸出

Question

我目前正在學習Java遞歸。我已經做了一些練習的代碼。

public class Tester{ 
    public static void main(String[] args){ 
     rec(5); 
    } 
    public static void rec(int x){ 
     if(x<=0){ 
      return; 
     }else{ 
      System.out.print(x+" "); 
      rec(x-1); 
     } 
    } 
} 
// Output: 5 4 3 2 1 

但如果我現在切換System.out.print(x+" ");與rec(x-1);，我得到一個完全不同的輸出，即反向：1 2 3 4 5

這怎麼可能呢？我理解它是這樣的：

我們有整數5，我們通過該方法。 if語句不適用，所以我們將5減去1，並且我們有x=4，我們重複該方法（未達到打印，因此不打印任何內容）。如上所述，我們與x=4一樣。如果聲明不適用，我們將4減少1並重復該方法。我們重複，直到我們有x=0。在這種情況下，我們返回，所以這是方法的結束。我完全不明白我們有什麼反向輸出，我甚至不明白爲什麼我們有輸出......？ ：■

Answer 1

好了，所以讓我們來研究第一種情況下

首先打印語句，然後遞歸調用： 空運行：

x = 5 Prints 5 then calls rec(4) 
x = 4 Prints 4 then calls rec(3) 
x = 3 Prints 3 then calls rec(2) 
x = 2 Prints 2 then calls rec(1) 
x = 1 Prints 1 then calls rec(0) 
x = 0 Base case reached, so method returns in the following sequence-> 
rec(1) -> rec(2) -> rec(3) -> rec(4) -> rec(5) ->main() 

因爲在這種情況下，沒有遞歸調用後執行沒有更多的說法，什麼都沒有發生，並且該方法開始爲第二種情況下返回回 現在： 一是遞歸調用，然後打印語句 幹運行：

x = 5 as x is not less than equal to 0 goes to rec(4) but print statement is now pending execution. It wont happen until the recursive call returns 
x = 4 as x is not less than equal to 0 goes to rec(3) but again print is on hold 
x = 3 as x is not less than equal to 0 goes to rec(2) but still print is on hold 
x = 2 as x is not less than equal to 0 goes to rec(1) but still print is on hold 
x = 1 as x is not less than equal to 0 goes to rec(0) but still print is on hold 
x = 0 as x is now 0, rec(0) returns to rec(1) 

現在REC（1）具有其現在與值執行的掛起的打印statment爲1 然後REC（2）具有其現在與值執行作爲2 然後REC一個掛起的打印語句（ 3）有待執行的打印語句（4）有一個掛起的打印語句，現在執行的值爲4 然後rec（5）有一個掛起的打印語句，現在執行的值爲5 ，然後rec（5）返回主（）

因此，在這種情況下，輸出是1-> 3-> 4-> 5 ，並且在第一種情況下它是5-> 4-> 3-> 2-> 1

希望這有助於你的理解:-)

Answer 2

試試這個：

public class Tester{ 
    public static void main(String[] args){ 
     rec(5); 
    } 
    public static void rec(int x){ 
     if(x<=0){ 
      return; 
     }else{ 
      rec(x-1); 
      System.out.print(x+" "); 
     } 
    } 
} 

的原因是，你首先需要達到逃逸條件（x == 0），然後開始相比，你的方法調用打印倒退模式的數字：

rec(5) 
    rec(4) 
     rec(3) 
      rec(2) 
       rec(1) 
        rec(0) // We stop here 
       System.out.print('1 ') 
      System.out.print('2 ') 
     System.out.print('3 ') 
    System.out.print('4 ') 
System.out.print('5 ') 

Answer 3

你得到的輸出是正確的。

在下面的情況1：

... 
System.out.print(x+" "); 
rec(x-1); 
... 

正確的輸出是：5 4 3 2 1

和在下面的情況2：

... 
rec(x-1); 
System.out.print(x+" "); 
... 

正確的輸出爲：1 2 3 4 5

說明： 在遞歸函數中，每個調用都放在一個堆棧上（因此，在後進先出訂單中執行）。

在情況1中，rec(x)首先打印其參數的值，然後調用rec(x-1)，因此順序恰好是x x-1 x-2 ...。以下是執行順序：

rec(5) 
    print 5 
    rec(4) 
     print 4 
     rec(3) 
      print 3 
      rec(2) 
       print 2 
       rec(1) 
        print 1 
        rec(0) 
         rec(0) return 
        rec(1) return 
       rec(2) return 
      rec(3) return 
     rec(4) return 
    rec(5) return 

在案例2中，在rec(x)功能首先打印其參數前調用rec(x-1)。情況2中的執行順序如下：

rec(5) 
    rec(4) 
     rec(3) 
      rec(2) 
       rec(1) 
        rec(0) 
         rec(0) return 
        print 1 
        rec(1) return 
       print 2 
       rec(2) return 
      print 3 
      rec(3) return 
     print 4 
     rec(4) return 
    print 5 
    rec(5) return 

我希望這可以幫助您瞭解上述兩種情況下的輸出結果。我也鼓勵你閱讀下面的計算器答案here，它們描述了遞歸函數如何更詳細地工作。