Java简单递归解释

Question

我实现了一个非常简单的递归方法，将两个数相乘在一起。我很难理解递归的基本知识。

有没有人能向我解释（如果可能的话，逐行解释）这段代码是如何工作的？我尤其感到困惑的是，基大小写被写为返回0，而实际上返回的是实际的乘法。

    public static int multiply(int n, int m) {
    if (m == 0) {
        return 0; //Base case
    }
    return multiply(n, m - 1) + n; //Recursive Case - Decrements m, while adding n
}

谢谢你的帮助

Answer 1

我会尽量让这个答案初学者友好。首先我回答你的这部分问题：

我尤其感到困惑的是，基大小写被写为返回0，而实际上返回的是实际的乘法。

在基本大小写中返回的值取决于如何实现算法。这里为了计算n*m，我们将这个乘法扩展为加法。几个例子将使这一点更加清楚。

2*3 = 2 + 2 + 2 + 0
4*1 = 4 + 0
5*5 = 5 + 5 + 5 + 5 + 5 + 0
n*m = n + n + n + ... + (m times) + 0

这就是为什么我们在基本情况下返回0，我们必须停止递归而不对结果做任何改变，这只有当我们添加0时才有可能。

以下是该程序的工作原理：

public static int multiply(int n, int m) {
if (m == 0) {
    return 0; //Base case
}
return multiply(n, m - 1) + n;

让我们取n=4和m=3。

我们对该方法的第一个调用是multiply(4，3)。然后我们继续，基础条件是假的，所以我们跳过它。

然后我们进入这一部分:返回multiply(n,m-1)+n。我们对同一个函数进行另一次调用。多个（4,2)。我们再次跳过基本情况。下面是一张表：

multiply(4, 3) -> return multiply (4, 2) + 4
multiple(4, 2) -> return multiply (4, 1) + 4
multiple(4, 1) -> return multiply (4, 0) + 4
multiple(4, 0) -> 0

在替换我们得到的返回值时,

multiple(4, 3) -> return 0 + 4 + 4 + 4 
multiple(4, 2) -> return 0 + 4 + 4
multiple(4, 1) -> return 0 + 4
multiple(4, 0) -> return 0

如果我们的第一个调用是multiply(n,m)，那么最后返回的值是：

multiply (n, m) -> return 0 + n + n + n + ... + (m times)

我希望我帮了你。试着自己构建一个类似的关系，这样你就会更好地理解它。下面是关于递归的进一步解释的链接：

https://www.geeksforgeeks.org/recursion