這個遞歸函數做什麼？

Question

這個函數有什麼作用？你如何評價它？

如何追蹤它？如何理解遞歸方法？

我只是無法理解遞歸，而考試日期即將到來，而且我知道爲了理解遞歸，我必須先了解遞歸。

但我只是不能寫一個稍微複雜的遞歸方法，任何人都可以幫助我使用最簡單的英文單詞。

public class BalancedStrings { 

    public static void printBalanced(String prefix, int a, int b) { 
     if (a > 0) 
      printBalanced(prefix + "a", a - 1, b); 
     if (b > 0) 
      printBalanced(prefix + "b", a, b - 1); 
     if (a == 0 && b == 0) 
      System.out.println(prefix); 
    } 

    public static void printBalanced(int n) { 
     if (n % 2 == 0) { 
      printBalanced("", n/2, n/2); 
     } 
    } 

    public static void main(String[] args) { 
     printBalanced(4); 
    } 
} 

Answer 1

到printBalanced()電話是遞歸調用。識別遞歸的方法是當一個函數自己調用時。使用樹繪製時，遞歸最好理解：

樹的樹枝將繼續，直至結束條件得到滿足，在這種情況下是a == 0 && b == 0創造更多的功能。您提供的函數看起來像是在遞歸地打印字符串「prefix」，並連接指定數量的「a」和「b」字符。當變量a和b達到0，遞歸停止，結果使用System.out.println(prefix);

在主函數要傳遞的整數4 printBalanced(int n)該呼叫printBalanced(String prefix, int a, int b)用參數，如該印刷：printBalanced("",2,2);

的總的結果是前綴用的均衡數量和b的

Answer 2

你停止條件並置是

a == 0 & b == 0 

直到這一條件得到滿足，你遞歸調用函數，降低A和B，直到他們都爲0

嘗試把一些斷點到printBalanced（），所以你可以看到它是如何工作的。

Answer 3

在最基本的計算機科學意義上，遞歸是一個自我調用的函數。 遞歸的實際用法很少。

樹的遍歷
圖形
樂星/解析
排序

遞歸的基本思路是你把原來的問題，並將其分成自身小（更容易解決）的情況下，解決這些較小的情況下， （通常再次使用相同的算法），然後將它們重新組裝到最終解決方案中。

例如，考慮計算數

function factorial(int n) 
{ 
    int fact = 1; 
    for(int i = 2; i <= n; i++) 
    { 
    fact = fact * i; 
    } 
    return fact; 
} 

Answer 4

的階乘它可以幫助您通過每次調用printBalanced之前放置print語句來遞歸的下面的C代碼，並打印語句作爲每個printBalanced方法定義的第一行。見下文：

public class BalancedStrings { 

    public static void printBalanced(String prefix, int a, int b) { 
     System.out.println("printBalanced called prefix = " + prefix + " a = " + a + " b = " + b); 
     if (a > 0) { 
      System.out.println("printBalanced calling printBalanced with prefix = " + prefix + " a-1 = " + (a-1) + " b = " + b); 
      printBalanced(prefix + "a", a - 1, b); 
     } 
     if (b > 0) { 
      System.out.println("printBalanced calling printBalanced with prefix = " + prefix + " a = " + a + " b-1 = " + (b-1)); 
      printBalanced(prefix + "b", a, b - 1); 
     } 
     if (a == 0 && b == 0) 
      System.out.println(prefix); 
    } 

    public static void printBalanced(int n) { 
     System.out.println("printBalanced called n = " + n); 
     if (n % 2 == 0) { 
      printBalanced("", n/2, n/2); 
     } 
    } 

    public static void main(String[] args) { 
     printBalanced(4); 
    } 
} 

另外，printBalanced也說成是過載的方法，因爲它有兩個「方法簽名」這基本上意味着它比定義一次以上，每一個方法定義具有一組不同的變量傳遞給該方法。

基本上，printBalanced會一直調用自己，直到變量a和b遞減爲零。然後它將打印輸出的結果前綴，使其不斷積累。另外，所有這些魔法都可能發生，因爲每個方法調用都會將前綴a和b的當前狀態推送到調用堆棧上。當方法最終返回而不進行遞歸調用時，堆棧將被解除。

我希望這有助於！遞歸可能很難理解。您還可以通過自己玩電腦來手動跟蹤電話，並通過執行寫在紙面上的方法來追蹤將被壓入電話堆棧的前綴a和b的值。

這裏是與跟蹤打印程序的輸出包括：

C:\Users\>java BalancedStrings 
printBalanced called n = 4 
printBalanced called prefix = a = 2 b = 2 
printBalanced calling printBalanced with prefix = a-1 = 1 b = 2 
printBalanced called prefix = a a = 1 b = 2 
printBalanced calling printBalanced with prefix = a a-1 = 0 b = 2 
printBalanced called prefix = aa a = 0 b = 2 
printBalanced calling printBalanced with prefix = aa a = 0 b-1 = 1 
printBalanced called prefix = aab a = 0 b = 1 
printBalanced calling printBalanced with prefix = aab a = 0 b-1 = 0 
printBalanced called prefix = aabb a = 0 b = 0 
aabb 
printBalanced calling printBalanced with prefix = a a = 1 b-1 = 1 
printBalanced called prefix = ab a = 1 b = 1 
printBalanced calling printBalanced with prefix = ab a-1 = 0 b = 1 
printBalanced called prefix = aba a = 0 b = 1 
printBalanced calling printBalanced with prefix = aba a = 0 b-1 = 0 
printBalanced called prefix = abab a = 0 b = 0 
abab 
printBalanced calling printBalanced with prefix = ab a = 1 b-1 = 0 
printBalanced called prefix = abb a = 1 b = 0 
printBalanced calling printBalanced with prefix = abb a-1 = 0 b = 0 
printBalanced called prefix = abba a = 0 b = 0 
abba 
printBalanced calling printBalanced with prefix = a = 2 b-1 = 1 
printBalanced called prefix = b a = 2 b = 1 
printBalanced calling printBalanced with prefix = b a-1 = 1 b = 1 
printBalanced called prefix = ba a = 1 b = 1 
printBalanced calling printBalanced with prefix = ba a-1 = 0 b = 1 
printBalanced called prefix = baa a = 0 b = 1 
printBalanced calling printBalanced with prefix = baa a = 0 b-1 = 0 
printBalanced called prefix = baab a = 0 b = 0 
baab 
printBalanced calling printBalanced with prefix = ba a = 1 b-1 = 0 
printBalanced called prefix = bab a = 1 b = 0 
printBalanced calling printBalanced with prefix = bab a-1 = 0 b = 0 
printBalanced called prefix = baba a = 0 b = 0 
baba 
printBalanced calling printBalanced with prefix = b a = 2 b-1 = 0 
printBalanced called prefix = bb a = 2 b = 0 
printBalanced calling printBalanced with prefix = bb a-1 = 1 b = 0 
printBalanced called prefix = bba a = 1 b = 0 
printBalanced calling printBalanced with prefix = bba a-1 = 0 b = 0 
printBalanced called prefix = bbaa a = 0 b = 0 
bbaa