2012-12-12 88 views
1

是有遞歸函數和存儲棧之間有直接的關係,更多的解釋認爲代碼:遞歸函數和內存堆棧之間的關係是什麼?

public static int triangle(int n) { 
    System.out.println(「Entering: n = 」 + n); 
    if (n == 1) { 
     System.out.println(「Returning 1」); 
     return 1; 
    } else { 
     int temp = n + triangle(n - 1); 
     System.out.println(「Returning「 + temp); 
     return temp; 
    } 
}​ 
在這個例子中

,其中將值2,3,4,5存儲,直到函數返回?請注意,它們將在LIFO中返回(LastInFirstOut)是處理內存堆棧的遞歸的一個特例還是它們總是在一起?

+1

如果您指的是調用堆棧,那麼每個調用都會在調用堆棧上創建一個條目,並且每個返回都將刪除條目。 –

+2

你從哪裏得到那些實際上不能在Java中使用的花式引用? –

+0

正如你所看到的'n == 1'是特殊情況,不會遞歸。 –

回答

1

是的,遞歸函數和內存堆棧之間存在直接關係,因爲一些具有高限制的函數會因爲達到堆棧大小限制而導致程序崩潰,並且函數會覆蓋程序代碼的一部分(這就是我們所說的堆棧-溢出)。

R:遞歸

我:迭代

first call: 
R | I 
|_| |_| 

second call: 
R | I 
|_| |_| 
|_| 

third call: 
R | I 
|_| |_| 
|_| 
|_| 
. 
. 
. 
n call : 
R | I 
|_| |_| 
|_| 
|_| 
. 
. 
. 
|_| 

我希望這是有道理的,迭代通話功能將被壓入堆棧做過一次從堆棧和下來電會熄滅加載一個類似的函數,另一方面,遞歸函數加載到堆棧並調用它自己並在每次調用時重新加載堆棧,然後當達到停止條件時它們開始關閉(LIFO最後一個被稱爲第一個)。

所以,現在要具體到你的問題,如你所說的n值將在停留條件滿足時保存在存儲器中,然後最後一個函數將顯示n,然後退出以將手賦予正好調用它也會顯示它自己的n值,同樣的事情會重複直到第一個函數被調用,然而迭代函數會顯示一個計數器n的值(只有一個變量被使用,我們正在改變它的值)。

下面是關於計算器的好文章,

非常深或無限遞歸主要文章:無限遞歸堆棧溢出的 最常見的原因是過深或無限遞歸 。像Scheme這樣的語言實現了尾部呼叫 優化,允許無限遞歸的特定排序 - 遞歸 - 發生 - 沒有堆棧溢出。這是有效的,因爲 尾遞歸調用不佔用額外的堆棧空間。

http://en.wikipedia.org/wiki/Stack_overflow

0

臨時變量n將位於堆棧上,將作爲返回地址作爲調用n-1的參數。這些都在同一個堆棧上。

0

由於QuentinQK解釋,局部變量n將消耗堆棧空間以及函數的返回地址 - 對於短moment-的返回值,並移交給遞歸函數的所有paramters消耗空間在堆棧上。這發生在每個遞歸級別上。所以這取決於遞歸的深度(這個函數自己調用的頻率),堆棧的多少最終會被調用,並且它會不會爆發。

因爲這個原因,它是必不可少的最後一個條件。在你的例子中,它是這個三角形「if (n==1)' condition where the recursion is stopped when that value is reached. It only works along with the n-1 in the parameter list of the recursive call of」。

但你真的想知道什麼?

2

假設這是一個C++類的方法,調用三角(n)的將數據推送到看起來堆棧等:

  • function code
  • int *returnAddress
  • int n

在哪裏在函數返回之前,返回值不會被賦值。 R.S.肖爲Call Stack wikipedia pagehere提供了一個很好的示例。

這個數據被遞歸到調用堆棧的頂部,每遞歸一次,所以最後一次調用三角形(n)的代碼將位於頂部。存儲在*returnAddress中的值是內存中需要執行結果以展開遞歸的地方。

換句話說,結果本身(例如:三角形(1)爲1,三角形(2)爲3)結束於堆棧的function code部分,而不是在內存中的特定命名位置。如果你運行一個調試器,你應該能夠通過在triangle功能代碼中放置一個斷點來跟蹤你的returnAddress的位置。

順便說一句,這不是一個遞歸的特例。這是經典的教科書案例。