algorithm - 无法理解用两个不同的输入递归调用相同的方法

Question

我最近开始接触递归。我浏览了一些可用的在线文档，但无法理解当我们使用不同的输入调用相同的方法时递归调用是如何工作的。

假设，如果我见过树

return find(node.left) + find(node.right);

我无法理解它是如何工作的。

在一般的递归中，每个调用都会在堆栈中占有一席之地，当达到基本条件时，我们会计算并返回结果。 我尝试做一个小程序，其中我从两个具有不同索引的不同调用者调用相同的方法，如果达到基本条件，则添加两个返回值。

if(n==0){
        return arr[n];
    }

    else {
        return calculateSum(arr, n-1) + arr[n];
    }

代码运行良好。现在我继续前进并尝试这样的事情。

它让我堆栈溢出。

if(n==1){
        return arr[n];
    }

    else {
        return calculateSum(arr, n-1) + calculateSum(arr, n-2);
    }

我完全无法理解它是如何发生的，我从这个主题中遗漏了什么无法完全理解它。

我已经根据提供的建议更改了我的代码。但是无法理解流程。 n-2 是如何运作的。我给了一些打印品。请在下面找到打印品和代码。

private static int calculateSum(int[] arr, int n, String caller){

    if(n<=1){
        System.out.println(caller+" : "+n+ " : "+arr[n]);

        return arr[n];
    }

    else {
        return calculateSum(arr, n-1," minus one") + calculateSum(arr, n-2,"minus two");
    }


}

打印:

减一:1:2

减二:0:1

减二:1:2

减一:1:2

减二:0:1

减一:1:2

减二:0:1

减二:1:2

数组的总和:13

如果有人可以帮助我了解它是如何工作的。我想知道 minus two 值是如何在开始时变成 0 然后变成 1 的，以及为什么 minus one 在 minus two 之后被再次调用一次达到基本条件。

注意:我已经删除了带有 return 语句的 arr[n]。所以，现在我想了解这个呼唤以及它是如何运作的。

Answer 1

你的程序的最后一个版本有很多问题，其中最重要的是总和中包含的数组的唯一元素是 arr[1]。

然而，堆栈溢出的原因是可能会在第二个参数为 0 的情况下生成对 calculateSum 的调用(例如，当 n==2 时的第二次递归调用) ，这将无法通过基本情况测试，并且由于后续递归调用的 n 值更小，因此永远不会成功。

我发现思考递归最有帮助的方法是想象其他人已经编写了一个函数来解决该问题的“较小”版本(例如，任何子树，或任何较小的 n 值) ; 任何合适的)。编写你的函数并利用那个函数，确保 a) 每当你调用它时，它都是一个较小版本的问题，并且 b) 如果你有一个足够小的问题版本你可以在没有递归调用的情况下解决，不要进行递归调用。 (请注意，如果您将此技术应用于最后一段代码，您可以看到，即使递归调用正常工作，您也会对数组的大部分进行重复计算。很明显，您的早期版本是正确。)

神奇之处在于:通过执行我上面描述的操作，您已经编写了您认为其他人已编写的函数。