Java快速排序递归无调用却重复执行问题求助

Hey Brian, let's unpack what's going on here—this is a classic case of misunderstanding how recursion unwinds in the call stack. Let's break it down step by step.

The Core Issue: Recursion Doesn't Terminate the Entire Method #

When you call quickSort recursively, that call doesn't stop the parent method dead in its tracks. Here's what actually happens:

• The parent method pauses execution at the recursive call.
• The child quickSort instance runs until it hits its own termination conditions (when the low/high indices cross).
• Once the child finishes, the parent method resumes executing the code after the recursive call.

In your code, the lines you're confused about:

System.out.println("**i=" + i + " **high_index=" + high_index);
// WHY DOES THIS LINE RUN TWICE IN A ROW WITH DIFFERENT VALUES?????
System.out.println("Why run again without call to quickSort()?");

sit right after the first recursive call (quickSort(low_index, j, "Run 1---------")) and before the second recursive check. That means every time a quickSort instance finishes its first recursive branch, it will run these print statements before deciding if it needs to launch the second recursive branch.

Walkthrough of Your Example #

Let's use your input array {7, -5, 3, 2, 1, 0, 45} to trace the flow:

1. The initial call is quickSort(0, 6, "First"). It partitions the array, then calls quickSort(0, 2, "Run 1---------") (after partitioning, j ends up as 2 here).
2. This child quickSort(0,2,...) runs, handles its own partitioning and recursive calls, then exits once its work is done.
3. Now we jump back to the parent quickSort(0,6,...) method, which resumes right after the first recursive call. It runs those two print lines using the parent's local variables—at this point, the parent's i is 4 and high_index is 6, which is why you see those values.
4. The parent then checks if (i < high_index) (4 < 6 is true), so it calls quickSort(4,6,"Run 2---------").
5. When that child finishes, we jump back to the parent one last time, but there's no more code left to run, so it exits.

The "different values" you see belong to different stack frames—each quickSort call has its own copy of i, high_index, and other local variables.

A Simple Analogy #

Think of recursion like stacking plates:

• You stack a plate (call a quickSort method) and work on it.
• When you hit a recursive call, you stack another plate on top and focus on that one.
• When you finish a plate, you take it off the stack and go back to the one below, finishing whatever was left undone on it.

Your print lines are part of that "undone work" on each plate.

How to Make This Visible #

To confirm this flow, add an exit print statement to your quickSort method:

private void quickSort(int low_index, int high_index, String one_two) {
    // ... all your existing code ...
    System.out.println("Exiting quickSort(" + low_index + ", " + high_index + ")");
}

You'll see exits happen in reverse order of calls—this is the call stack unwinding in action.

内容的提问来源于stack exchange，提问作者Brian Wiley