我如何使遞歸軌跡打印出來？

所以我試圖打印出斐波那契數列的遞歸函數的軌跡。我如何使遞歸軌跡打印出來？

我的輸出應該是這樣的：

enter image description here

不過，我不確定如何格式化這個。我不知道從哪裏開始。我已經試過這樣：

private static int fibCount; 

public static long fibonacci(int n) { 
    fibCount++; 
    long result; 
    if (n == 0 || n == 1) { 
     result = n; 
     System.out.printf("fib(%s)-->%s%n", n, result); 
    } else { 
     result = fibonacci(n - 1) + fibonacci(n - 2); 
     System.out.printf("fib(%s)%n", n); 
    } 
    return result; 
} 

public static void main(String args[]) { 
    fibonacci(5); 
}

打印出

fib(1)-->1 
fib(0)-->0 
fib(2) 
fib(1)-->1 
fib(3) 
fib(1)-->1 
fib(0)-->0 
fib(2) 
fib(4) 
fib(1)-->1 
fib(0)-->0 
fib(2) 
fib(1)-->1 
fib(3) 
fib(5)

我覺得我需要使用fibCount變量（我做到了，只是因爲我認爲缺口將依靠它），但我不知道我是否應該或如何。

來源

2015-01-14 Tetramputechture

嘗試以下操作：

分手了你的遞歸調用（這樣你就可以打印之間的當前呼叫）
通在depth參數來跟蹤多少縮進

public static long fibonacci(int depth, int n) { 
    String indent = new String(new char[depth]).replace('\0', ' '); 
    long result; 
    if (n == 0 || n == 1) { 
     result = n; 
     System.out.printf(indent + "fib(%s)-->%s%n", n, result); 
    } else { 
     long first = fibonacci(depth+1, n - 1); 
     System.out.printf(indent + "fib(%s)%n", n); 
     long second = fibonacci(depth+1, n - 2); 
     result = first + second; 
    } 
    return result; 
} 

public static void main(String args[]) { 
    fibonacci(0, 5); 
}

輸出：

fib(1)-->1 
    fib(2) 
    fib(0)-->0 
    fib(3) 
    fib(1)-->1 
fib(4) 
    fib(1)-->1 
    fib(2) 
    fib(0)-->0 
fib(5) 
    fib(1)-->1 
    fib(2) 
    fib(0)-->0 
fib(3) 
    fib(1)-->1

來源

2015-01-14 22:23:41 aioobe

您應該保留一種縮進計數器，每當您輸入斐波納契函數時遞增，每當您離開它時遞減。

然後，在打印時，請在實際打印之前將該計數器的當前值放置爲多個空格。爲了更好地觀看，您可以放置兩倍的空間，但這只是個人選擇。

來源

2015-01-14 22:19:24 Iamsomeone

您需要在每次調用時傳入縮進級別。每次求助時，都可以增加縮進。

public static long fibonacci(int n) { 
    return fibonacci(n, 1); 
} 

public static long fibonacci(int n, int indent) { 
    System.out.printf("%"+indent+"s", ""); 
    long result; 
    if (n == 0 || n == 1) { 
     result = n; 
     System.out.printf("fib(%s)-->%s%n", n, result); 
    } else { 
     result = fibonacci(n - 1, indent + 2) + fibonacci(n - 2, indent + 2); 
     System.out.printf("fib(%s)%n", n); 
    } 
    return result; 
}

來源

2015-01-14 22:22:42

您不能在格式字符串中將'0'作爲寬度傳遞。另外，OP在當前呼叫的「中綴」打印輸出之後。 – aioobe

我假設在現實世界中，你只把在跟蹤這樣的（特別是使用一個靜態變量）作爲臨時措施調試，並在投入生產之前刪除代碼。如果你想把它留在生產代碼中，我會尋找一個不同的解決方案。首先，如果您打算爲此使用靜態變量，則需要確保每個遞歸調用在之後恢復其值。這可能是最好做這在finally塊，以確保恢復總是發生，即使有一個return隱藏在代碼中的某個地方（或者在例外的情況下）：

public static long fibonacci(int n) { 
    int saveFibCount = fibCount; 
    fibCount++; 
    try { 
     fibCount++; 
     long result; 
     if (n == 0 || n == 1) { 
      result = n; 
      System.out.printf("fib(%s)-->%s%n", n, result); 
     } else { 
      result = fibonacci(n - 1) + fibonacci(n - 2); 
      System.out.printf("fib(%s)%n", n); 
     } 
     return result; 
    } finally { 
     fibCount = saveFibCount; 
    } 
}

其次，要獲得這到你的縮進：不幸的是，Java沒有一個內置的方法來返回一串n空格。你可以寫一個很輕鬆了（在Apache的共享提供或使用方法，我認爲），並利用它們是這樣的：

 if (n == 0 || n == 1) { 
      result = n; 
      System.out.printf("%sfib(%s)-->%s%n", blanks(4*fibCount), n, result); 
     } else { 
      result = fibonacci(n - 1) + fibonacci(n - 2); 
      System.out.printf("%sfib(%s)%n", blanks(4*fibCount), n); 
     }

其中blanks(b)返回b空白的字符串。您可以使用StringBuilder創建空字符串，或者類似的東西：

String blanks = String.format("%" + numOfBlanks + "s", "");

[注：根據另一個答案評論，這並不工作，如果numOfBlanks 0]

或者你可以用一個String fibIndent取代fibCount，而不是fibCount++使用

fibIndent += " ";

保存以前的版本之後。

要考慮的另一件事是：如果這是生產代碼，我建議將另一個參數傳遞給遞歸例程，而不是使用靜態變量。試圖用遞歸例程來處理靜態變量，即使在單線程的程序中，也很麻煩且容易出錯。遞歸參數應該是一個值參數或一個不可變的對象，在將它傳遞給下一個調用之前，它將被每個調用複製。在這種情況下，「遞歸深度」（您的fibCount）可能是參數。我不建議將引用傳遞給所有遞歸調用將共享的對象，因爲這與使用靜態變量（雖然更安全）相比，幾乎具有錯誤傾向。

[注：我花了很多我的職業生涯的一個遞歸下降編譯工作，所以很多這些問題都對我很熟悉]

[最後：我知道這只是練習，但不要使用遞歸來計算斐波那契數。這樣做給你一個指數算法，而不是一個線性算法，因爲它是一個簡單的循環。這是因爲遞歸算法執行大量冗餘工作，計算結果的相同參數的倍數倍。]

來源

2015-01-14 22:31:27 ajb

我如何使遞歸軌跡打印出來？

回答

相關問題