1

我还没有开始理解线性递归，然后我想我练习排序算法，然后快速排序是我遇到递归问题的地方。所以我决定使用一个更简单的方法，例如我在网上找到的二进制和。我知道递归，就像所有函数调用一样，一次执行一次，而不是同时执行（这是多线程所做的，但在跟踪时我不关心）。所以我需要在递归调用B之前执行所有递归调用A，但我迷失了。有没有人介意完全追踪它。例如，我使用的大小为 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));
}
4

2 回答 2

2

我个人做的是从一个大小为 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 => ceil(9/2) = 5，地板(9/2) = 4

现在首先调用（顶部调用） binarySum(array, 0, 9)

现在 n = 大小不是 1

因此递归调用....

返回 binarySum(array, 0, 5) + binarySum(array, 5, 4)

现在第一个 binarySum(array, 0 ,5) 对数组的前 5 个元素进行操作，第二个 binarySum(array,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) 返回 arr[i];

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

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

      [6          +           9]                      [30]

                  [15                +                 30] 

                                   [45]

这是总和。

所以为了理解，看看对问题的主要实例做了什么，你可以确定同样的事情也会发生在问题的次要实例上。

于 2012-06-11T06:44:29.297 回答
0

这个例子 解释了 java 中带有跟踪的二进制和

跟踪基于数组的索引，其中 0 - 是您的起始索引，8 是数组的长度

在此处输入图像描述

于 2014-07-31T17:04:26.727 回答