Суммирование элементов массива с использованием двоичной рекурсии

Question

Я не начинал понимать линейную рекурсию, а затем я думал, что занимаюсь сортировкой алгоритмов, а затем быстро сортировать, где у меня были проблемы с рекурсией. Поэтому я решил работать с более простой, например, двоичной суммой, которую я нашел в Интернете. Я понимаю, что рекурсия, как и все вызовы функций, выполняется один раз - время и не в одно и то же время (это то, что делает многопоточность, но не относится к моей проблеме при трассировке). Поэтому мне нужно выполнить весь рекурсивный вызов A ПЕРЕД рекурсивным вызовом B, но я теряюсь в миксе. Кто-нибудь думает об этом. Например, Я использовал размер, n = 9, где elems - все, чтобы сохранить его простым.

/** 
* 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)); 
} 

Answer 1

То, что я лично делаю, начинается с массива размера 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.

теперь в случае 1 добавляются 2 элемента внутри индексов от 0 до 2, а также 2 элемента, добавленные в индексы 2-4.

Теперь эти два результата добавляются в этом случае.

Теперь мы можем больше понять технику рекурсии, иногда понимание снизу вверх проще, чем в этом случае!

Теперь рассмотрим ваш вопрос массив из 9 элементов: 1 2 3 4 5 6 7 8 9

п = 9 => CEIL (9/2) = 5, этаж (9/2) = 4

Теперь первый вызов (верхний вызов) из binarySum (массив, 0, 9)

Теперь п = размер не является 1

, следовательно, рекурсивный вызов ....

возвращение binarySum (array, 0, 5) + binarySum (массив, 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] 

который является суммой.

Чтобы понять, что сделано для основного экземпляра проблемы, и вы можете быть уверены, что то же самое произойдет с второстепенным экземпляром проблемы.

Answer 2

Это example объясняет двоичную сумму с трассой в Java

след основан на индексе массива, где 0 - это ваш начальный индекс и 8 является длиной массива