递归实际上如何在Java中工作? [英] How does Recursion actually work in Java?

问题描述

我对本次递归还很陌生，至少我知道这是一种技巧一个方法在执行过程中会自行调用，但我对它的实际使用方式感到困惑有效.

I'm just new to this Recursion and I know at least that it is a technique by which a method calls itself during execution but I am quite confused on how it actually works.

在学校的书中，实现阶乘功能是第一个示例给出了.

From the book at school, implementing the factorial function is the first example that was given.

//int n = 5;
private static int factorial(int n) {
    if(n == 0) {
        return 1;
    }   
    else
        return n * factorial(n - 1);
}

我知道这种析因如何工作，但是我不确定我是否正确理解它.对于每次调用，方法都引用自身，将 n 乘以阶乘参数 n-1 ，直到达到 1 .

I get how this factorial works somehow but I am not completely sure if I understood it correctly. For every call the method refers to itself, n is multiplied to the factorial parameter n - 1 until it reaches 1.

这就是我在脑海中追溯这种递归的方式

This is how I trace this recursion in my mind

5 * factorial(5 - 1) = 20 //first call
20 * factorial(4 - 1) = 60 //second call
60 * factorial(3 - 1) = 120 //third call
120 * factorial(2 - 1) = still 120 // fourth call

120 is the last returned value;

给出的另一个示例是使用递归而不是使用普通循环来打印从1到n的数字.

And another example that was given is printing numbers from 1 to n using recursion instead of using the ordinary loop.

//int n = 10;
private static void printNumbers(int n) {
    if(n >= 1) {
        printNumbers(n - 1);
        System.out.print(n + " ");
    }
}

这将输出: 1 2 3 4 5 6 7 8 9 10

现在，让我感到困惑的是为什么输出从 1 开始?因为根据我的理解，输出应该从 9 一直到 1 .

And now, the thing confuses me here is why the ouput starts at 1? Because from how I understand it the output should start at 9 up to 1.

因为据我所知，开始时 n = 10 ，然后是 10>1 ，因此当然它将再次调用自身，然后 10-1 ，然后打印 9 ，然后再次调用自身，并再次调用 9-1 然后打印 8 ，依此类推...

Because from I understood it, at start the n = 10 and then 10 > 1 so of course it will call itself again then 10 - 1 then print 9 and then calls itself again and 9 - 1 then print 8 and so on...

任何人都可以简单地向我澄清一下，并将我的错误理解更正为我提到的示例.我在这里有些困惑，我在StackOverflow上看到的关于递归的大多数帖子都没有真正的帮助(但是，如果您知道在这里有一个关于递归的真正好而清晰的答案，请给我链接).

Can anyone please clarify this to me simply and correct my mistaken understanding to the examples I've mentioned, I am a little confused here and most of the post I can see here on StackOverflow about recursion is not really helping (But if there is a real good and clear answer about recursion in here that you know of, do give me the link).

谢谢...

推荐答案

看一下这个示例，该示例与您的示例不同，但是可以帮助您了解操作顺序如何影响递归.之所以起作用，是因为返回行上的操作顺序.

Take a look at this example which is different than yours but will help you understand how the order of operations affects recursion. It works because of the order of operations on the line of the return.

public int getRSquare(int n){
    if(n==0){
        return 1;
    }
    return getRSquare(n-1)*n;
} 

每次调用此方法时，都会发生的第一件事是对getRSquare(n-1)的递归调用.在乘以返回的值之前会发生这种情况.下面的示例调用getSquare(3)，然后再调用getSquare(2)，然后再调用getSquare(1)，然后再调用getSquare(0).仅在此之后，才适用基本情况n == 0，并且不会进行递归，而是返回1.然后，此返回值将与上一次调用的n相乘，在很多情况下，n是一个不同的值.

You will see with each call of this method, the first thing to occour is the recursive call to getRSquare(n-1). This happens before it multiplies what is returned. The example below calls getSquare(3) then getSquare(2) then getSquare(1) then getSquare(0). It is only after this that the base case n==0 applies and no recursion happens, but a 1 is returned. This returned value is then multiplied with the n of the previous call which is in many cases a different value.

result = getSquare( n=3);        
               getSquare(n=2)     
                      getSquare(n =1)     
                             getSquare(0)
                              Return a 1,
                         return returned value multiplied by n  (n is a 1 prev returned value is 1 = 1)
                  return returned value multiplied by n  (n is a 2 prev returned value is 1 = 2)
          return returned value multiplied by n  (n is a 3 prev returned value is 2 = 6)

您将看到上述对getSquare(3)的调用将返回6.请记住，n对于每个函数调用都是局部的，因此每次调用getSquare方法都会有自己的n，因为递归n每次变小，当我们返回时，n会变大，因为那是它在上一次方法激活时的值.

You will see the above call to getSquare(3) will return a 6. Remember that n is local to each function call so each activation of the method getSquare will have its own n, as we recurse n gets smaller each time, as we return back up, n gets larger because that's the value it had at the previous method activation.

作为一项练习任务，我建议您使用这种方法，以便了解在切换操作顺序时会发生什么情况:

As a practice task, I recommend is you use this approach so see what happens when you switch the order of operations such as:

public int getRSquare(int n){
    if(n==0){
        return 1;
    }
    return n * getRSquare(n-1);
} 

这篇关于递归实际上如何在Java中工作?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！