遞歸 - 試圖瞭解

Question

我有一個方法：

public static int maxFind(int [] a, int length) 
{ 
    if (length == 1){ 
      return a[0]; 
    } 

    // recursively maxFind method on length-1 
    int result = maxFind(a, length - 1); 

    if (a[length - 1] > result) 
    return a[length - 1]; 
    else 
    return result; 

} 

我已經完成了這項工作，並從當我看到那個方法的教程經過一段時間，我總是忘了遞歸的想法。我認爲如果有人會向我解釋這一方法的每一步 - 我會一勞永逸地提出這個想法。

例子 - 我的改編是：{1,1,0,2）

什麼是這裏的步驟，當我們運行這個方法？結果的價值是什麼，（a，長度爲1）的作用是什麼？ （我試過調試器，但它沒有幫助我）

Answer 1

我會試着一步一步解釋：

首先調用與參數{1,1,0,2}和4個方法

1）max_find（[1,1,0,2]，4）=>長度不是1，以便max_find將再次與長度被稱爲= 4-1

2）max_find（[1,1 ，0,2]，3）=>長度不是1，所以max_find將再次被調用，長度= 3-1

3）max_find（[1,1,0,2]，2）=>長度不是1，以便max_find將再次與長度被稱爲= 2-1

4）max_find（[1,1 ，0,2]，1）=>長度爲1，所以將返回一個[0]，即1

5）現在代碼形式步驟3評估步驟4的結果=> a [2-1 ]不是> 1，所以它返回1

6）現在的代碼形式的步驟2從步驟評估結果3 =>一個[3-1]不> 1，所以它返回1

7 ）現在代碼表單步驟1評估結果fr OM步驟2 =>一個[4-1]> 1，所以它返回一個[4-1]，這是2

完成

Answer 2

這個想法基本上是你做了完全相同的東西，只是輸入數據的一點點改變。

代碼本身很簡單：

• 第一if檢查遞歸結束
• 的int result線做遞歸
• 你lookes的最大元素，並返回它的結束。

Answer 3

讓我看看我是否可以在這個問題上提出一些看法。

在考慮遞歸時，它有助於（至少是我）以更具說明性的方式思考程序，也就是說，考慮您要完成的內容，而不是考慮算法的每一步需要完成它。

讓我們來看看你的例子，你需要在一個數組中找到最大值，所以我們將在較小的問題中分解這個問題。

如果數組的大小爲1，那麼只有一個元素...所以一個是最大的。簡單。

找到最大值的問題可以描述爲：列表的一個元素與所有其他元素的最大值之間的較大值。

這就是你在做的其他代碼。您將算法應用於數組，從位置0到長度1，然後比較返回值。

這些電話將創建一個遞歸樹，意義，會有多個呼叫「嵌套」，直到每個呼叫與長度= 1（基礎情況）完成，並且然後，算法將開始重建的答案。

真正理解遞歸算法的最好方法是抓住一張紙並模擬程序，在紙上爲每次調用寫入數組的值和「length」的值，然後弄清楚在每次通話最終達到基本情況後發生。

對於{1,1,0,2}，你基本上得到調用鏈，是這樣的：

max(maxFind({1,1,0}), 2) 

凡maxFind（{1,1,0}）歸結爲：

max(maxFind({1,1}), 0) 

和maxFind（{1,1}）是

max(1,1) = 1 

然後這個開始沸騰起來（這是從上述相反的順序）：

max(1, 0) = 0 
max(1, 2) = 2 

那麼結果將是2

Answer 4

什麼是對結果的值

那麼這就是遞歸點：沒有一個值結果，這可能是什麼讓你感到困惑。結果的值依次爲1,1,1,1,2。

當我們運行此方法時，這裏的步驟是什麼？

這裏發生的事情：用遞歸方法工作時

What is the max of: {1} ? Result is: 1 
What is the max of: {(1), 1} ? Result is: 1 
What is the max of: {(1, 1), 0} ? Result is: 1 
What is the max of: {(1, 1, 0), 2} ? Result is: 2 

注意調試的確不是小事。它有時幫助更多的打印方法調用「縮進」的深度遞歸級別，像這個問題我回答在這裏：

How do I solve the 'classic' knapsack algorithm recursively?

（你需要以某種方式保持「深度跟蹤的過程'遞歸調用）

和（a，長度-1）的作用是什麼？ （我已經嘗試了調試，但 它沒有幫助我）

調試器可能不會因爲爲了節省內存在Java中的方法是使用一個「竅門」幫助您：基本輸入被縮短表明你不應該分析整個數組。但是你仍然遞歸地將整個數組傳遞給方法。這是一個「窮人獲得少一個元素的清單的功能性方式」; ）

下面是一個鏈接，顯示如何找到不同語言的lot中的列表的最大值。他們中的一些，像OCaml的一個，表示以函數形式：OCaml中的

http://rosettacode.org/wiki/Greatest_element_of_a_list

三線（來源：維基百科）：

let my_max = function 
    [] -> invalid_arg "empty list" 
    | x::xs -> List.fold_left max x xs