难以理解多次递归调用

Question

function max(arr, first, last){
if (first==last) return arr[first];
mid=first+(last-first)/2;
a=max(arr, first,mid);
b=max(arr, mid+1,last);
if (a<b) return b;
return a;
}

我无法理解这个递归函数，因为我不太明白分配变量时流程是如何工作的。我的理解是，当a=max(arr, first,mid);a 将继续调用该函数直到基本情况发生时 - 所以我可以安全地假设这种情况发生

b=max(arr, mid+1,last);     
if (a<b) return b;
    return a;`

直到'a'调用完毕才执行？当流程到达“b”并开始递归调用时，它是否会影响a=max(arr, first,mid);- 因为它将对 a 应用不同的值？

我对查找最大值的理解是，a 将在前半部分找到最大元素，b 将在后半部分找到最大元素，但我不明白它如何做到这一点，直到if (a<b) return b; return a;在当a和b都有值时，我的想法是它会检查这一点，以便它可以找到a中的最大值和b中的最大值，然后比较两半的最大值以找到arr中的最大元素？

抱歉，如果问题含糊不清，我只是想更好地理解递归

Answer 1

您试图通过一步一步地追踪每一个调用来理解它是如何工作的。不要这样做，这很混乱。

查看一个调用做了什么，而不必担心当前调用的函数中发生了什么max()。是的，它调用了自己，甚至调用了两次。这两个调用都是返回值的函数调用，就当前的调用而言max()，它们也可能只是数字。

如果我用以下内容替换分配a和b的行：

a = 13;
b = 42;

那么你就不会有任何困难理解它的作用了。如果我用这个替换它们：

a = max_implemented_with_a_for_loop(arr, first, mid);
b = max_implemented_with_a_for_loop(arr, mid+1, last);

那么你也不会遇到麻烦。递归版本没有那么不同。

像这样的递归函数的工作原理是，将一个大问题分解为更小的子问题，解决子问题，然后组合解决方案来解决大问题。它使用自身来解决子问题，如果我们没有基本情况，就会出现障碍 - 到了某个点，您将无法进一步细分问题，并且您需要另一种方法来解决这些微小的子问题。但这并不是什么大问题，因为太小而无法再划分的子问题很容易解决。基本情况只是注意到我们有一些容易直接解决的问题和/或无法进一步划分，并处理它。