Java中的遞歸它如何工作？

請在下面的代碼中解釋遞歸語句的工作原理。Java中的遞歸它如何工作？

int factR(int n) { 
    int result; 

    if(n==1) return 1; 

    result = factR(n-1) * n; 
    return result; 
}

我的理解是：

在上面的語句factR(n-1)方法調用本身，直到結束。假設我們想得到6的階乘，它將作爲參數發送給這個方法。它將被接收作爲參數n，然後的n值將被檢查;如果它是1，那麼將返回1。但如果它不是1，就像我們的情況那樣，它是6，那麼遞歸語句就會運行。

現在我面臨的問題是，第一次n-1變成5並且乘以n，保持值6，那麼它變成30.現在30那裏去哪裏？

然後該方法將自行調用，此時n-1變爲4，然後乘以n，其中IF保持值「6」，然後是4 * 6 = 24，我認爲這是錯誤的。因爲如果我們通過這種方式然後在下次調用過程將會像，n-1將成爲3 * n的IF保持相同的值，即6，然後它會成爲3×6 = 18，然後出現下一個電話和n-1變爲2，如果我們相乘並假設n保持值6然後2 * 6 = 12，並在最後一次調用n-1 = 1 * N = 6，我的意思是很清楚，n-1將減小值n-1即6-1 = 5然後5-1 = 4然後4-1 = 3然後3-1 = 2和2-1 = 1。但問題是，當方法調用它時，每次都會乘以n的值是多少？

如果說的是，當第一乘法發生即，「N-1」成爲5然後由6 = 30乘以和30被存儲在「n」個則在下一呼叫5-1 = 4 * 30 = 120 ，然後4-1 = 3 * 120 = 360，然後3-1 = 2 * 360 = 720，和最後1 * 720 = 720然後如何爪哇確定把所得到的值返回到可變n？

如果我把另一個語句來檢查什麼是可變result的值每次方法調用本身以這種方式，就像這樣：

int factR(int n) { 
    int result; 

    if(n==1) return 1; 

    result = factR(n-1)*n ; 
    System.out.println(result); 
    return result; 
}

然後我得到這樣的輸出：

2 
6 
24 
120 
720 
Factorial of 6 is 720

我不明白它在第一次調用時如何產生2。價值2，然後6,24,120和720從哪裏來？我認爲我在代碼的工作中受到嚴重阻礙。

來源

2015-11-18 Aurang Zeb Khan

您是否嘗試調試代碼？ – TheLostMind

你是錯誤的方式。在你的情況下，它不會首先得到'30'。它將以'1 * 2'開始 - >將結果傳遞給調用者methot'* 3' - >將結果傳遞給調用方法'* 4'，依此類推。遞歸調用的每次調用都被放到堆棧上，當堆棧到達不進行任何進一步遞歸的地步時，該堆棧從頂部（最後一個調用）一直回到底部（第一個調用）。 – SomeJavaGuy

2不是第一個電話，是第2個電話，它只是你的第一個電話在返回println之前做的返回。 – valepu

-1

的方法真的應該構建這樣找到的n階乘：

int factorial(int n) 
{ 
    if (n == 1) 
     return 1; 

    return n * factorial(n - 1); 
}

這不是一個很好的主意，在我看來實例化一個遞歸函數裏面新的變數，因爲他們」由於範圍的原因，每次調用都會重置。

來源

2015-11-18 14:36:03

它與他的方法非常相似，只需少量代碼，只要他能夠用打印語句調試他的代碼 – SomeJavaGuy

@KevinEsche是的，我知道，我個人發現實例化因變量而最終超出範圍的變量是不好的做法;增加了更多的困惑。 –

那真的沒有回答 –

什麼，你可能會在這裏錯過了是n是一個局部變量的函數。這意味着每次調用函數（可能通過遞歸或不通過）都會得到一個新變量n，其中包含該函數的參數。因爲它是一個值類型，所以它被複制而不是對原始值的引用。因此，在一次調用中對其進行的任何更改都不會影響其他（遞歸）調用中的變量。

因此，您的函數首先獲得6的副本，並將其作爲副本減去1作爲函數的下一個調用。該呼叫獲得6-1=5的「副本」並再次減少 - 等等。當它到達1時，它也會返回1。然後通過調用堆棧重新運行，並將最後一次調用的結果與本次調用中的局部變量相乘。所以1得到乘以2並得到返回。該結果將乘以3等等。最後你最終得到階乘。

來源

2015-11-18 14:41:34

函數展開，直到達到終止語句（n == 1）。所以假設n = 6，那麼我們有factR(n-1) * n = factR(5) * 6，但factR(5)是什麼？那麼它只是factR(4) * 5，所以我們看到factR(5) * 6 = (factR(4) * 5) * 6。現在注意factR(1) = 1，我們得到

factR(6) = factR(5) * 6 
     = (factR(4) * 5) * 6 
     = ((factR(3) * 4) * 5) * 6 
     = (((factR(2) * 3) * 4) * 5) * 6 
     = ((((factR(1) * 2) * 3) * 4) * 5) * 6 
     = ((((1 * 2) * 3) * 4) * 5) * 6 
     = (((2 * 3) * 4) * 5) * 6 
     = ((6 * 4) * 5) * 6 
     = (24 * 5) * 6 
     = 120 * 6 
     = 720

來源

2015-11-18 14:42:03 Sunde

在java中，我們有一種叫堆棧。

每次方法被另一個方法調用時，它都會被添加到堆棧中。

________ 
|factR(1)| = <prints nothing> 
________ 
|factR(2)| = 2 
________ 
|factR(3)| = 6 
________ 
|factR(4)| = 24 
________ 
|factR(5)| = 120 
________ 
|factR(6)| = 720

這基本上意味着，對於factR(6)方法來完成，factR(5)必須完成，對於factR(5)來完成，factR(4)必須完成等。

在factR(6)您打電話給factR(5)，然後等待它完成，因爲結果取決於它。

但是，在factR(5)中，您也進行了遞歸調用，您必須等待。

依此類推，直到我們打了極限factR(1)，這將直接返回1.

隨着factR(1)完整，factR(2)就可以打印出結果，並將結果返回到它的父方法，並依此類推，直到factR(6)打印出來並返回結果

來源

2015-11-18 14:55:03

bruno_cw這個問題，在閱讀了Mukesh Kumar的上述答案之後，你的回答真的很容易理解，而且坦率地說，它和清楚的單詞本身一樣清晰:-)，我希望知識能夠在這樣一個美麗的方式由你，謝謝 –

非常感謝！ :) –

Java中的遞歸它如何工作？

回答

相關問題