Java 方法调用自身.. 递归？

Method calling itself.. recursive?

提问by Oscar F

public static int m(int i, int j)    
{     
  if ( i > j)    
    return 0;    
  else    
  {
    i++;    
    m(i++, j);
  }
  return i;    
}

I had two questions. 1.) What is returned by out.print(m(3,8));and 2.) How many times is the method m called? The answers should be 5 and 7 respectively.

我有两个问题。1.) 返回的是什么out.print(m(3,8));和 2.) 方法 m 被调用了多少次？答案应分别为 5 和 7。

When I worked out question 1, I came out with 5 but the way I did it was incorrect because the method was not called 7 times, it was only called twice. The way I did this was I went straight to the else statement since (i > j)was false at the start and method m was called again this time with (4, 8)I figured it was still false so I went back to the line where m is called and the variable i changed to 5 because of the i++in m(i++, j). After that it would return 5 for the Value of i.

当我解决问题 1 时，我得出了 5，但我的方法是不正确的，因为该方法没有被调用 7 次，它只被调用了两次。我这样做的方式是我直接进入 else 语句，因为(i > j)在开始时是错误的，这次再次调用了方法 m，(4, 8)我认为它仍然是错误的，所以我回到调用 m 的行和我更改的变量到 5 因为i++在m(i++, j). 之后它将为 i 的值返回 5。

That was obviously wrong so I added some out.prints for the values of i throughout the program to see how the value was changing and it went from 3 to 9 with an out.print(i);at the beginning of method m. An out.print(i);right before return i;showed the values started to go backwards from 10 to 5 and the method was called 7 times. How does this work?

这显然是错误的，所以我在整个程序中为 i 的值添加了一些 out.prints 以查看值是如何变化的，它从 3 变为 9 并out.print(i);在方法的开头使用 an m。一个out.print(i);正确的前return i;表现开始倒退10至5价值观和方法被调用7次。这是如何运作的？

EDIT: After logging it, I was able to come up with some logic to it but I would like someone to clarify that it is correct.

编辑：记录后，我能够想出一些逻辑，但我希望有人澄清它是正确的。

method m is called with 3,8 at the start. After, it calls itself with 4,8 then 5,8....until 9,8 where the if statement becomes true and the method returns 0. It called itself 6 times so it starts go backwards or decrement-ing 6 times so since m(i++, j) is post(the i) then i becomes 10 and 10 is returned, then 9, then 8, then 7, 6, and finally 5. When it returned 10 that was 1, 9 was 2, 8 was 3, 7 was 4, 6 was 5, and 5 was 6. So since it was 6 when i = 5, that was the value that was returned. Is this correct? And if it is, a more in depth explanation would be nice to have.

方法 m 在开始时以 3,8 调用。之后，它用 4,8 然后 5,8....直到 9,8 调用自己，if 语句变为真，方法返回 0。它调用自己 6 次，所以它开始向后或递减 6 次因为 m(i++, j) 是 post(the i) 然后 i 变成 10 并且返回 10，然后是 9，然后是 8，然后是 7、6，最后是 5。当它返回 10 是 1 时，9 是 2, 8是 3，7 是 4，6 是 5，5 是 6。所以因为当 i = 5 时它是 6，这就是返回的值。这样对吗？如果是这样，更深入的解释会很好。

采纳答案by nhgrif

To better understand what's happening, it might help to refactor the code as such:

为了更好地理解发生了什么，将代码重构如下可能会有所帮助：

public static int m(int i, int j) {
    static int calls = 0;     
    System.out.println("entering.  count: " + calls);
    calls++;

    System.out.println("i = " + i);
    System.out.println("j = " + j);

    if (i > j) { 
        System.out.println("returning 0");
        return 0;
    } else {
        i++;    
        m(i++, j);
    }

    System.out.println("returning " + i);
    return i;    
}

Note that I haven't modified any of the actual logic. All I've done is add some statements to print values, and a variable to keep track of the number of times the method is called.

请注意，我没有修改任何实际逻辑。我所做的只是添加一些语句来打印值，并添加一个变量来跟踪调用方法的次数。

回答by 75inchpianist

The reason you are seeing the value decrement is because before you print the last 'i', this value is only incremented in local scope (the first i++ in your else condition).

您看到值递减的原因是因为在打印最后一个 'i' 之前，该值仅在局部范围内递增（else 条件中的第一个 i++）。

When your m function returns to its caller, i is no longer i+1 as it was in the child, thus you see the decrementing values until the root 'm' call is returned.

当您的 m 函数返回到它的调用者时， i 不再是子代中的 i+1 ，因此您会看到递减值，直到返回根 'm' 调用。

回答by Palec

I'll analyze the function in general case, the specific argument values will be used at the end only. Running the function and watching what it does via debugger or debug prints is handy when you have such tools, but in certain cases you have to rely on your brain only. E.g. it is really hard to pull debug info from FPGA(you need to simulate its work). When being interviewed for a job, you typically get a computer to test the code – your analytic skills are being tested. That's why I highly recommend using pencil & paper approach before looking at what the code really does when executed.

我将在一般情况下分析该函数，仅在最后使用特定的参数值。当您拥有此类工具时，运行该函数并通过调试器或调试打印观察它的作用会很方便，但在某些情况下，您只能依靠您的大脑。例如，从FPGA 中提取调试信息真的很困难（你需要模拟它的工作）。在接受工作面试时，您通常会得到一台计算机来测试代码——您的分析技能正在被测试。这就是为什么我强烈建议在查看代码在执行时真正做了什么之前使用铅笔和纸的方法。

Question 1: Return value

问题 1：返回值

When trying to analyze complicated code, knowing what you can neglect is the key to success.

在尝试分析复杂的代码时，知道可以忽略什么是成功的关键。

Here you know that

在这里你知道

• the code is single-threaded,
• there are no global variables, no side-effects for the world outside the current call,
• return value of the recursive call is not used.

• 代码是单线程的，
• 没有全局变量，对当前调用之外的世界没有副作用，
• 不使用递归调用的返回值。

So there is no need to think about what mess could come from other threads, you can analyze the single call without thinking of how recursive calls would influence it (apart from returning a value) and you can forget about the recursive call unless it is infinite recursion (which will not let your program terminate) because it has no effect other that consuming time.

因此，无需考虑其他线程可能带来什么混乱，您可以分析单个调用而无需考虑递归调用将如何影响它（除了返回值）并且您可以忘记递归调用，除非它是无限的递归（它不会让您的程序终止），因为它除了消耗时间之外没有任何影响。

The recursion is not infinite as iis always incremented before the recursive call and the recursion stops when i > j.

递归不是无限的，因为i它总是在递归调用之前递增，并且递归在 时停止i > j。

Knowing that, deciding what the return value is is pretty easy. The function can be reduced to

知道了这一点，决定返回值是很容易的。该函数可以简化为

public static int m(int i, int j)
{
    if (i > j)
        return 0;
    else
        i += 2;
    return i;
}

Because return terminates execution of the function, this can be even further reduced to

因为 return 终止函数的执行，这甚至可以进一步简化为

public static int m(int i, int j)
{
    return (i > j) ? 0 : i + 2;
}

giving you the answer to question 1. When called as m(3, 8), the result is 0because iis less than j.

给出问题 1 的答案。当调用 as 时m(3, 8)，结果是0因为i小于j。

Question 2: Number of calls

问题 2：调用次数

The recursion is linear – at most one recursive call is made in each call. So you have to count how many calls it takes till the bottom of recursion is reached.

递归是线性的——每次调用最多进行一次递归调用。因此，您必须计算到达递归底部所需的调用次数。

The bottom of recursion is the first branch of the condition. Therefore you count how many times a call is made till i > j.

递归的底部是条件的第一个分支。因此，您计算呼叫的次数，直到i > j。

jhas the same value in each of the calls. There is no command to change its value, it is always passed to the recursive call unchanged. iis always incremented before the recursive call once and after the call once (i++is postincrement, taking the effect after the original value is used). Only the first increment is relevant for the recursive call.

j在每个调用中具有相同的值。没有命令可以改变它的值，它总是不变地传递给递归调用。i总是在递归调用一次之前和调用一次之后递增（i++是后递增，在使用原始值后生效）。只有第一个增量与递归调用相关。

For the sake of counting recursive calls, the function can be reduced to

为了计数递归调用，该函数可以简化为

public static void m(int i, int j)
{
    if (i > j)
        return;
    else
        m(i + 1, j);
}

From this, it is obvious that iis successively incremented by 1, till it's greater than j.

由此可知，i连续递增 1，直到大于j。

In m(3, 8), the calls are

在 中m(3, 8)，调用是

• m(3, 8),
• m(4, 8),
• m(5, 8),
• m(6, 8),
• m(7, 8),
• m(8, 8)and
• m(9, 8).

• m(3, 8),
• m(4, 8),
• m(5, 8),
• m(6, 8),
• m(7, 8),
• m(8, 8)和
• m(9, 8).

So there are 7 of them.

所以有7个。

If the parameters given had bigger difference, general solution would be handy. So let's explore it. It would be quick.

如果给出的参数有较大的差异，通用解决方案会很方便。所以让我们来探索一下。会很快的。

If initially i > j, only one call is made, obviously. Otherwise… how many numbers do you meet when counting from ito j + 1? (j + 1) - i + 1 = j - i + 2. Plus one at the is is for the topmost call. That's the general answer.

如果最初i > j，显然只进行一次调用。否则……从ito数时，你遇到了多少个数字j + 1？(j + 1) - i + 1 = j - i + 2. 加一个是用于最顶层的呼叫。这是一般的答案。