使用二進制遞歸求和數組的元素

我沒有開始理解線性遞歸，然後我認爲我在排序算法上練習，然後快速排序是遞歸問題。所以我決定用一個更簡單的工具，例如我在網上找到的一個二進制和。我明白，像所有函數調用一樣，遞歸一次只執行一次，而不是同時執行（這是多線程做的事情，但在跟蹤時不是我關心的事情）。所以我需要執行所有的遞歸調用B之前的遞歸調用B，但我迷失在混合中。有沒有人介意完全追蹤它。例如，我已經習慣了尺寸，n = 9，其中elems都是1來保持簡單。使用二進制遞歸求和數組的元素

/** 
* Sums an integer array using binary recursion. 
* @param arr, an integer array 
* @param i starting index 
* @param n size of the array 
* floor(x) is largest integer <= x 
* ceil(x) is smallest integer >= x 
*/ 
public int binarySum(int arr[], int i, int n) { 
    if (n == 1) 
     return arr[i]; 
    return binarySum(arr, i, ceil(n/2)) + binarySum(arr,i + ceil(n/2), floor(n/2)); 
}

來源

2012-06-09 user784423

我嘗試的長度像斐波那契例如在這個網站上追蹤但它對我來說變成了一場噩夢。請參閱：http://cis.stvincent.edu/html/tutorials/swd/recur/recur.html。我會感謝大家的幫助。 – user784423

我個人做的是從大小爲2的數組開始。有兩個元素。

return binarySum（arr，i，ceil（n/2））+ binarySum（arr，i + ceil（n/2），floor（n/2））除了將數組拆分爲2並添加這兩個要素。 - 案例1

現在，這個簡單的起點將是遞歸較高的情況下的最低水平。

現在增加n = 4。數組被分成2：0-2和2-4的索引。

現在索引0到2內的2個元素被添加到情況1中，所以索引2-4中添加了2個元素。

現在在這種情況下添加這兩個結果。

現在我們能夠做出更多的遞歸技術的意義，有時瞭解自下而上的是在這種情況下更容易！

現在您的問題考慮9個元素的數組：1 2 3 4 5 6 7 8 9

N = 9 =>小區（9/2）= 5，地板（9/2）= 4

現在第一呼叫binarySum的（頂部呼叫）（陣列，0，9）

現在爲n =大小不是1

因此遞歸調用....

返回binarySum（數組，0，5）+ binarySum（array，5，4 ）

現在第一binarySum（陣列，0，5）運行在所述陣列的所述第一5個元素和第二binarySum（數組，5,4）在陣列的最後4個元素

因此操作陣列分區可以看作是這樣的：1 2 3 4 5 | 6 7 8 9

第一功能找到的元素的總和：1 2 3 4 5

和第二函數發現加入6 7 8 9

並且這兩個元素的總和一起返回，作爲頂級通話的答案！

現在這個1 + 2 + 3 + 4 + 5和6 + 7 + 8 + 9是如何工作的？我們再次遞歸....

所以跟蹤看起來像

      1 2 3 4 5 | 6 7 8 9 

      1 2 3 | 4 5       6 7 | 8 9 

    1 2 | 3    4 | 5   6 | 7   8 | 9

[1 | 2] _ __ [3] _ __ [4 5] _ __ [6 7] __ _ [8 9]

直到這一點，我們很好..我們只是遞歸地調用函數。

但現在，我們打基礎案例！

if（n == 1） return arr [i];

[1 + 2] _ ___ [3] __ _ _ [4 + 5] _ ___ [6 + 7] __ _ _ [8 + 9]

[3 + 3] _ ___ [9] __ _ _ [13 + 17]

 [6   +   9]      [30] 

        [15    +     30] 

            [45]

其總和。

因此，爲了理解看到問題的主要實例做了什麼，您可以確定相同的事情將發生在問題的次要實例上。

來源

2012-06-11 06:44:29 phoenyx

這example解釋了跟蹤在Java

跟蹤是基於陣列的索引的二進制總和，其中0 - 是你的起始索引和8是陣列

enter image description here

來源

2014-07-31 17:04:26

儘管這個鏈接可能回答這個問題，但最好在這裏包含答案的重要部分，並提供供參考的鏈接。如果鏈接頁面更改，則僅鏈接答案可能會失效。 –

@EugenePodskal我編輯它 –

使用二進制遞歸求和數組的元素

回答

相關問題