Java递归方法是如何工作的？

Question

我对Java编程比较陌生，也刚刚开始学习递归，但我似乎无法理解这种方法是如何在我的脑海中工作的。

   private static int mystery(int w) {
    {
        if (w < 0) return 0;
        int x = mystery (w-2);
        return w - x;
    }
}

无论何时放入一个像100这样的变量，它都会输出50。当输入200时，它输出100。当输入为2时，输出为2。当输入为25时，输出为13。我不确定这个方法是如何工作的，我正在试着理解它。

按照我目前的观点，如果你放入100，它将绕过第一个return语句，因为它大于0。当它到达第二行时，它会做100- 2，这会带来98，然后转到第三行，做100 - 98 =2，然后返回到原始调用。

我知道我在方法的第二行搞砸了，这就是谜团(w-2)。我假设它会再次将w-2的结果带回方法的开头，并且它会一遍又一遍地重复该方法，直到w小于0，无论答案如何，它都应该再次输出0。但事实并非如此，我也不知道为什么。

有人能解释一下这是怎么回事吗？

Answer 1

你遗漏的是，在第二行，它不只是w- 2，而是将自己称为w- 2的，直到调用返回。如果w不小于0，则第二个调用调用自身，依此类推，直到值小于0，然后返回。如果你想像一下，执行过程会是这样的：

mystery(10)
    > skip first line
    > x = mystery(8)
        > skip first line
        > x = mystery(6)
            > skip first line
            > x = mystery(4)
                > skip first line
                > x = mystery(2)
                    > skip first line
                    > x = mystery(0)
                        > skip first line
                        > x = mystery(-2)
                            > return 0
                        > return 0 - 0 (0)
                    > return 2 - 0 (2)
                > return 4 - 2 (2)
            > return 6 - 2 (4)
        > return 8 - 4 (4)
    > return 10 - 4 (6)

以w= 10为例。我希望你现在能更好地理解它。

Answer 2

   private static int mystery(int w) {
    {
        if (w < 0) return 0;
        int x = mystery (w-2);
        return w - x;
    }
}

让我们想象一下，我们调用mystery(3)。会发生什么呢？w<0)为false，所以我们不返回0。在下一行中，我们使用值3-2=1作为参数调用名为mystery的函数。尽管我们调用的这个函数恰好是我们刚刚调用的那个函数，但它仍然是一个普通的函数调用，并且它返回一个值。它通过调用名为mystery的函数来实现这一点，这次使用值-1作为参数。这次w<0是真的，所以我们只返回0。现在，我们回到对mystery的第二个调用中，并且设置了x= 0。所以调用返回w-0= 1，这让我们回到第一个调用，现在x= 1，所以我们返回w-x = 3-1 = 2。

您可能希望花几分钟时间使用w=4完成此工作，并查看您得到了什么-这将帮助您理解递归调用是如何工作的。完成此操作后，我建议您在函数中添加一条或两条print语句，以告知您所在的位置以及正在发生的事情，这也会有所帮助-但首先要在纸上完成。

Answer 3

给出的两个答案都很好。这两种方法都侧重于如何掌握什么是递归。递归的问题是，对于一个不知道递归是什么，或者不知道有人知道递归的人来说，这是非常不自然的。就像一条蛇一次又一次地吃自己。

理解递归的最好方法是写下对递归方法的调用，方法是在调用时忽略当前状态，并在调用后写回结果。你将调用堆叠起来，这也是根本不使用递归的方法。

因此，一开始不要太努力地去理解递归，但首先要关注程序流。如果你已经看过足够多的递归，它就会来到你身边。