遵循递归

Question

我正在努力遵循这个“据称简单”的递归过程

void display(int x, int y) {
   int[] a = {0,1,2,3};
   if(x==y) {
      System.out.print(a[x]+" ");
   }
   else {
   int mid=(x+y)/2;
   display( x, mid);
   display( mid+1, y);
}

在第一个打印语句 x=0 和 y=0 和 mid=0 之后， - 我明白这一点。下一个调用似乎是第二个调用 display( mid+1, y);现在突然 y=1 - 这个变化发生在哪里 - 执行 print 语句，然后 y=3 的值。显然调试器不是遵循这个的最佳方法 - 我理解因子示例中发生了什么并且可以在笔和纸上跟随它 - 是否可以看到这个例子中发生了什么？任何帮助将不胜感激。

Answer 1

您应该尝试在函数的开始处打印 x、y 和 mid。

您还可以复制粘贴，如 @Mehrdad 建议的那样，或绘制一棵树（一棵二叉树，因为每个调用都会导致 0 或 2 个以上的调用）。

剧透：

             (0,[1],3)
            /         \
    (0,[0],1)         (2,[2],3)
   /         \       /         \
(0,0)       (1,1) (2,2)       (3,3)

——

我最初写了一些类似的东西，然后认为你可能不需要它。现在我认为您是这样做的：

x 和 y 是函数的参数。因此，每次调用都会有自己独立的 x 和 y。在这种情况下，将有 7 个 x 和 7 个 y（检查树）。

至于“跳跃”，事实证明我很难解释，抱歉，但它很简单：树的一个分支结束，另一个开始。 （因此，当 (1,1) 结束时，(0,[0],1) 也结束，并且 (0,[1],3) code> 进行第二次调用，(2,[2],3) - 这是从 1 到 3 的“跳转”。）

Answer 2

它只是使用“二分搜索”算法按顺序遍历所有元素，然后打印出每个元素。我认为结果只是从索引 x 到 y 的所有元素。

请注意，mid 这个词是一个提示：如果您取两个事物的平均值并得到中间值，那么您的原始变量可能是 start 和 end分别。因此，尝试重写它：

void display(int start, int end)
{
    int[] a = { 0, 1, 2, 3 };
    if (start == end)
    {
        System.out.print(a[start] + " ");
    }
    else
    {
        int mid = (start + end) / 2;
        display(start, mid);
        display(mid + 1, end);
    }
}

它应该看起来更明显一点：将数组分成两半，在每一半上调用自己，当一半的长度为 1 时，打印该位置的值。