遞歸，無法理解輸出

爲什麼我會在輸出中獲得額外的1 * 1，並且它有點向後？有點初學者在這裏遞歸，會愛上一個詳細的答案。遞歸，無法理解輸出

class Program 
{ 

    public static long Factorial(int n) 
    { 
     if (n == 0) 
      return 1; 

     Console.WriteLine("{0} * {1}", n, Factorial(n - 1)); 
     return n * Factorial(n - 1);  
    } 
    static void Main(string[] args) 
    { 
     long a = 0; 
     a = Factorial(3); 
     Console.WriteLine(a); 
    } 
}

輸出

來源

2017-06-18 yosu

我投票關閉這一問題作爲題外話，因爲被調試的幫助：這個代碼是如何工作的？ – danihp

@danihp基本上有人（@yosu）犯了一個錯誤，這也可能發生在其他人身上。所以這甚至可以幫助其他人，有一個類似的問題。它不是那麼廣泛，它只是調試幫助，這是一個關於遞歸的相當緊湊的問題。 – MetaColon

@MetaColon代碼有一個很大的錯誤，因爲這個輸出沒有意義。 OP要求忽略這個錯誤。這是家庭作業。 OP應該爲自己做。它們是雙遞歸，應該是簡單的。 – danihp

你的下一行遞歸調用函數兩次，一旦輸出，然後再次。這就是輸出完全混亂的原因，因爲你從Console.WriteLine()方法中調用它，然後立即在return聲明中再次調用它。

此外，因子零爲1，因此我在WriteLine()方法中添加了一點三元語句檢查，以便輸出在數學上是正確的。

Console.WriteLine("{0} * {1}", n, Factorial(n - 1)); // Calling it once 
return n * Factorial(n - 1); // Calling it again, oops!

這裏有一個輕微的調整，這將有助於：

public static long Factorial(int n) 
{ 
    if (n == 0) 
     return 1; 
    Console.WriteLine("{0} * {1}", n, (n>1?n-1:n)); 
    return n * Factorial(n - 1);  
} 

static void Main(string[] args) 
{ 
    long a = Factorial(3); 
    Console.WriteLine(a); 
}

息率

來源

2017-06-18 16:11:17 TomServo

這個問題要求詳細的答案。 – MetaColon

這是因爲有第二個因子循環在日誌輸出回事：

Console.WriteLine("{0} * {1}", n, Factorial(n - 1));

這需要計算te因子（n-1）之前它打印任何東西。因爲遞歸的每一步現在都會觸發兩個遞歸，所以它比您預期的複雜得多！

所以階乘（3）：

開始記錄「3 *階乘（2）」 - >但需要制定出階乘（2）
- 階乘（2）開始記錄「2 *階乘（1） - >但需要制定出階乘（1）
  - 階乘（1）開始記錄」 1 *階乘（0） - >但需要制定出階乘（0）
    - 階乘（0）返回1
  - 現在階乘（1）可打印「1 * 1」（你的第一行輸出的。）
  - 現在階乘（1）需要計算階乘（0）其返回值...
    - 階乘（0）返回1
- 階乘（2）可以登錄「2·1」（你的第二行輸出。）
- 階乘（2）現在需要計算階乘（1）返回
  - 階乘（1）開始記錄「1 *階乘（0） - >但需要制定出階乘（0）
  - ...等等，等等

如果將其更改爲類似：

Console.WriteLine("{0} * Factorial({1})", n, n - 1);

然後你會得到更像你期待的日誌。

（如果你正在學習遞歸，這可能是有趣的，你通過與調試工作，並看到程序的流程如何去，以及爲什麼它會導致輸出，你看到的。）

來源

2017-06-18 16:24:38

但是，現在您的日誌記錄朝着錯誤的方向（如3 * 2; 2 * 1; 1 * 0），這可能會造成混淆。而且，更令人困惑的是，如果您僅對您的日誌付款，您將擁有1 * 0，導致1。 – MetaColon

取決於'錯誤'方向的意思！如果你對函數調用的順序感興趣，這是正確的方向 - 但同意它是有爭議的。我提出的建議給出了輸出'1 * Factorial（0）'而不是'1 * 0' - 但是再一次，記錄最清楚的依賴於目的。 –

碰巧，你的錯誤與遞歸無關。你的問題是，你調用了一個方法兩次，而不是保存它的價值。如果你不打印結果，你甚至不會意識到這一點。作爲@JLK指出，你在這個片段中調用它兩次：通過代碼

Console.WriteLine("{0} * {1}", n, Factorial(n - 1)); 
return n * Factorial(n - 1);

讓我們一步，這樣我們就可以理解輸出：

Factorial (3); 
-> output 3 * {Factorial (2)}   // 3 * 2 (4) 
    -> output 2 * {Factorial (1)}  // 2 * 1 (2) 
     -> output 1 * {Factorial (0)} // 1 * 1 (1) 
     <- 1 
     Factorial (0) 
     <- 2 
     Factorial (1) 
     -> output 1 * {Factorial (0)} // 1 * 1 (3) 
     <- 1 
     Factorial (0) 
     <- 1 
    <- 1 
    Factorial (2) 
    -> output 2 * {Factorial (1)}  // 2 * 1 (6) 
     -> output 1 * {Factorial (0)} // 1 * 1 (5) 
     <- 1 
     Factorial (0) 
     <- 1 
     Factorial (1) 
     -> output 1 * {Factorial (0)} // 1 * 1 (7) 
     <- 1 
     Factorial (0) 
     <- 1 
    <- 2

這可能是一個有點混亂，但這對於遞歸是正常的。所以基本上所有你需要做的是改變代碼片段一點點：

var factorial = Factorial (n - 1); 
Console.WriteLine("{0} * {1}", n, factorial); 
return n * factorial;

輸出則是：

如果您想了解更多關於遞歸，我d建議this網站。這不是關於C＃，但它是一個很好的學習遞歸的網站。如果你想在遞歸中做很多事情，我不會推薦C＃，因爲它是一種命令式語言。對於遞歸函數語言更適合。如果你仍然想保持接近C＃，或至少使用.Net框架，我建議使用F#，這是C＃的功能等價物。

C＃和遞歸的主要問題是，C＃不支持Tail recursion。這可以很容易地導致StackOverflows，當你做更深的遞歸調用（例如無限遞歸循環）。這是因爲每次你調用一個函數時，你調用該函數的代碼地址被壓入堆棧。所以每次你做一個遞歸調用時，代碼地址都被推送到堆棧。所以，如果你有例如這樣的功能：

void rec() => rec();

你在更短的通過調用它獲得的StackOverflow比在C＃中的第二個。尾遞歸至少部分解決了這個問題：如果遞歸調用是函數中的最後一次執行，它不會推送調用者的代碼地址。因此，在F＃這個一直運行：

let rec r() = 
    r() 
r()

（我不會去深入到F＃的語法，有足夠的在線教程）。我說它只解決了部分問題，因爲這個：

let rec r() = 
    r() 
    () 
r()

導致StackOverflow再一次。我不知道任何編程語言，如果情況並非如此，那麼您只需習慣使用尾遞歸。

您可以在this後閱讀更多關於功能/遞歸語言。

來源

2017-06-18 16:38:01 MetaColon

你應該向右功課，從記分牌複製。你必須恰克：

Console.WriteLine("{0} * {1}", n, Factorial(n - 1));

通過

Console.WriteLine("{0} * {1}", n, n - 1);

這個錯誤做出錯誤的輸出。

來源

2017-06-18 16:52:16 danihp

遞歸，無法理解輸出

回答

相關問題