這個簡單的遞歸代碼發生了什麼？

-2

我似乎無法理解爲什麼由我怎麼看它下面的代碼打印這個簡單的遞歸代碼發生了什麼？

，它應該打印的2個二進制位的排列。

請不要修復我的代碼。我想要解釋爲什麼它現在就是這樣。

public static String addZ(int n) 
{ 
    String str =""; 
    if(n==0) 
     return ""; 
    str += "0" + addZ(n-1)+"\n"; 
    str += "1" + addZ(n-1); 
    return str; 
}

來源

2016-12-27 naor.z

那麼，沒有主（）它不能打印任何東西。 – FredK

它看起來像你傳遞'n = 2'到這個，並打印輸出。在第一次調用方法時，前兩行來自代碼中的第一個「str + =」，接下來的兩行來自第二個「str + =」。你爲什麼不通過'n = 1'看看會發生什麼？然後你會注意到'n = 2'如何給你兩次相同的輸出，還有額外的'0'和'1'。 –

我嘗試了一種「模式替換」：對於n = 1，我們得到「0 \ n1」。讓我們稱它爲x。對於n = 2，我們得到「0x \ n1x」，即「00 \ n1 \ n10 \ n1」。希望它有幫助... – Matthias

如果這與家庭作業有關，您應該如此標記它。

您的代碼使用類似0{prev}\n1{prev}的格式生成文本，其中{prev}是遞歸調用的結果。請注意，此換行符成爲遞歸結果的一部分，因此將「中斷」其他調用的結果。讓我告訴你我的意思。

n == 0是基本情況，並且硬編碼爲返回空字符串（""）。

n == 1是第一個可以遞歸的情況。由於{prev}是空字符串，因此返回0\n1。這打印爲

0 
1

n == 2接下來。 {prev}是0\n1，所以這產生00\n1\n10\n1。當你注意，這是打印

n == 3是最後一步，我會展示。 {prev}是00\n1\n10\n1，所以它產生000\n1\n10\n1\n100\n1\n10\n1，打印作爲

作爲視覺輔助，我會用不同的括號來包裝在打印輸出中的不同遞歸回報。捲曲括號包裹n == 0結果，方括號n == 1結果和括號包裹n == 2結果。

0(0[0{} 
1{}] 
1[0{} 
1{}]) 
1(0[0{} 
1{}] 
1[0{} 
1{}])

編輯

的OP說，這不是一個家庭作業，所以我改變了我的答案提供樣本的Java程序，將打印所有號碼從0到2^bits - 1.

public class Main { 
    public static void main(String[] args) { 
     String binaryNumbers = buildBinaryNumbersString(4); 
     System.out.println(binaryNumbers); 
    } 

    private static String buildBinaryNumbersString(int bits) { 
     return recursivelyBuildBinaryNumbersString(bits, ""); 
    } 

    private static String recursivelyBuildBinaryNumbersString(int bits, String prefix) { 
     String result; 
     if (bits <= 0) { 
      result = prefix; 
     } else { 
      result = 
       recursivelyBuildBinaryNumbersString(bits - 1, prefix + "0") + 
       "\n" + 
       recursivelyBuildBinaryNumbersString(bits - 1, prefix + "1"); 
     } 
     return result; 
    } 
}

（您可能會注意到，我改變了主意，換行需要是在基本情況下，這將導致不具有潛在的外來尾隨newling返回值。）

個

此代碼打印

這個代碼是你的差不多，但不同的是什麼使得它的工作。你的代碼可以被認爲是試圖在一個值的下面構建所有的二進制字符串，然後試圖擴展這些值來包含下一個更高的位（儘管代碼沒有成功完成）。通過將「迄今爲止的數字」前置到0或1的下一個位的值，該代碼被寫入以便在多個遞歸路徑中重複使用。因此，recursivelyBuildBinaryNumbersString()的呼叫對於相同的bits值將有很大的不同，取決於通過的prefix。考慮的是所有這些prefix值產生什麼時候bits總是1：

prefix: result 
000: 0000\n0001 
001: 0010\n0011 
010: 0100\n0101 
011: 0110\n0111 
100: 1000\n1001 
101: 1010\n1011 
110: 1100\n1101 
111: 1110\n1111

見這八個前綴及其八個輸出組合如何產生全部十六排列的四個位？

值得注意的是，這項技術用於傳遞迄今爲止通過遞歸調用編寫的結果。這種技術與使用遞歸調用將結果返回給調用鏈一樣有用。值得一提的是，這種技術對於尾遞歸至關重要。對於支持尾遞歸（而非Java）的語言，並且函數的返回值是對同一函數的遞歸調用時，可以編寫遞歸函數，以便該函數執行的最後一個操作是tail call。鬆散地說，這意味着調用函數的堆棧條目不再需要，因爲被調用函數的堆棧條目足以生成調用函數的返回。這允許調用函數的堆棧條目被被調用函數的堆棧條目覆蓋，消除了堆棧溢出的危險。我不知道是否每個遞歸函數都可以用等價的使用tail調用的遞歸函數替換，但即使如此，我也發現了通過調用鏈向下傳遞state-in-progress的想法非常有用。

來源

2016-12-27 21:41:05 sadakatsu

感謝您的解釋，沒有它不是一個家庭作業，你可以把它泄漏出去。 –

如果你想了解遞歸函數是如何工作的，最好把它看作一棵樹。對於功能：

public static String addZ(int n) 
{ 
    String str =""; 
    if(n==0) 
     return ""; 
    str += "0" + addZ(n-1)+"\n"; 
    str += "1" + addZ(n-1); 
    return str; 
}

馬上我們可以看到，這兩個str +=其實只是一個調用追加到字符串如下："0" + addZ(n-1) + "\n" + "1" + addZ(n-1)。

現在，如果我們添加一些記錄到控制檯中，我們得到了一個樹是這樣的：

str += "0" + addZ([n=2] n-1)+"n"; 
    str += "0" + addZ([n=1] n-1)+"n"; 
     addZ(n = 0) = "" 
    str += "1" + addZ([n=1] n-1); 
     addZ(n = 0) = "" 
str += "1" + addZ([n=2] n-1); 
    str += "0" + addZ([n=1] n-1)+"n"; 
     addZ(n = 0) = "" 
    str += "1" + addZ([n=1] n-1); 
     addZ(n = 0) = ""

此輸出的好處是，你可以直接把它捲起來

str += "0" + {addZ([n=2] n-1) = "0" + "" + "\n" + "1" + ""} +"\n"; 
    str += "0" + {addZ([n=1] n-1) = ""} +"\n"; 
     addZ(n == 0) = "" 
    str += "1" + {addZ([n=1] n-1) = ""}; 
     addZ(n == 0) = "" 
str += "1" + {addZ([n=2] n-1) = "0" + "" + "\n" + "1" + ""}; 
    str += "0" + {addZ([n=1] n-1) = ""}+"\n"; 
     addZ(n == 0) = "" 
    str += "1" + {addZ([n=1] n-1) = ""}; 
     addZ(n == 0) = ""

因此

addZ(n = 2) = "0" + {"0" + "" + "\n" + "1" + ""} +"\n" "1" + {"0" + "" + "\n" + "1" + ""} 
addZ(n = 2) = "00\n1\n10\n1"

這是你的輸出：

如果你想用的n大值的經驗，我會建議添加日誌到您的代碼像這樣：https://dotnetfiddle.net/MqqnuM

來源

2016-12-27 21:41:55 jrbeverly

用您所添加的功能遞歸，直到到達調用堆棧的頂部基本情況下，你開始從堆棧彈出呼叫。

在addZ(2)的情況下，str被聲明爲空字符串，然後賦值爲「0」+ addZ（2-1）或addZ（1）的返回值。

addZ(1)聲明它自己的空str，它的值爲「0」+ addZ（1-1）或addZ（0）的返回值。

ADDZ（0）是基準的情況下，返回空String到addZ(1)

addZ(1)仍然僅具有「0」的值，其它增加了換行字符「\ n」個一海峽

addZ(1)然後將值「1」添加到str + addZ（0）的返回值，正如我們從上面知道的那樣，它是一個空字符串。

addZ(1)返回-STR與addZ(2)具有「0 \ N1」

addZ(2)繼續通過添加新行字符爲str的值。

此時str =「00 \ n \ 1 \ n」，這就是您的輸出示例顯示的內容。

addZ(2)然後將「1」+ addZ（2-1）或addZ（1）的返回值添加到str。

從以上，我們知道addZ(1)最終返回「0 \ N1」

STR現在持有價值「00 \ n \ 1 \ N10 \ N1」，功能完成。

基本上，只要按照邏輯。如果你很難將時間花在遞歸上，它也可能有助於用調試器來完成它。

來源

2016-12-27 22:07:49 Coop

這個簡單的遞歸代碼發生了什麼？

回答

相關問題