归并排序（Python）：递归如何记忆返回位置与递归前数组状态？

Great question—this is exactly the kind of deep dive that turns surface-level understanding into real mastery of recursion! Let’s break this down using call stacks, the invisible engine that makes recursion’s "memory" work.

The Short Answer #

Recursion doesn’t "remember" anything on its own—your programming language’s call stack handles all the state tracking for you. Every time you make a recursive call, the language saves a snapshot of the current function’s state (parameters, local variables, and crucially, where to resume execution once the call finishes) in a stack frame. When a recursive call completes (like merging the smallest left/right subarrays), the stack pops that frame, and execution picks up right where it left off in the parent call.

Let’s Walk Through Merge Sort Step-by-Step #

Let’s use a simple example with the array [3, 1, 4, 2] and a simplified merge sort function to see how this works:

def merge_sort(arr, left, right):
    if left >= right:
        return  # Base case: single element is sorted
    
    mid = (left + right) // 2
    print(f"Calling merge_sort on left half: indices {left} to {mid}")
    merge_sort(arr, left, mid)  # Step 1: Sort left half
    
    print(f"Calling merge_sort on right half: indices {mid+1} to {right}")
    merge_sort(arr, mid+1, right)  # Step 2: Sort right half
    
    print(f"Merging halves: {left}-{mid} and {mid+1}-{right}")
    merge(arr, left, mid, right)  # Step 3: Merge sorted halves

Here’s How the Call Stack Tracks Execution #

1. We start with merge_sort(arr, 0, 3) (the full array). Since 0 < 3, we calculate mid=1, then call merge_sort(arr, 0, 1).

   • The call stack pushes a frame for merge_sort(0,3), which remembers: "After the left half call finishes, I need to run the right half call (line 8), then merge (line 11)."

2. In merge_sort(arr,0,1), mid=0, so we call merge_sort(arr,0,0).

   • The stack pushes a frame for merge_sort(0,1), remembering: "After left half call finishes, run right half call (line 8), then merge (line 11)."

3. merge_sort(arr,0,0) hits the base case (left >= right) and returns immediately.

   • The stack pops the merge_sort(0,0) frame, and execution resumes in merge_sort(0,1) at line 8: we call merge_sort(arr,1,1).

4. merge_sort(arr,1,1) hits the base case and returns.

   • Stack pops that frame, execution resumes in merge_sort(0,1) at line 11: we merge the halves 0-0 and 1-1 into [1,3]. Then merge_sort(0,1) returns.

5. Now we’re back in merge_sort(0,3) at line 8: we call merge_sort(arr,2,3). This repeats the same process—breaking down to merge_sort(2,2) and merge_sort(3,3), merging them into [2,4], then returning to merge_sort(0,3).

6. Finally, merge_sort(0,3) runs line 11: merging [1,3] and [2,4] into the sorted array [1,2,3,4].

The Key Detail: Return Addresses #

Every stack frame includes a return address—this is the exact line of code the interpreter will jump back to when the current function call ends. For example:

• The frame for merge_sort(0,3) has a return address pointing to line 8 (right half call) after the first recursive call completes.
• The frame for merge_sort(0,1) has a return address pointing to line 8 (right half call) after its first recursive call completes.

This is how recursion "picks up where it left off"—the call stack holds all the context needed to resume execution in the parent function.

Why This Makes Sense Compared to Other Recursion #

You already know Fibonacci or factorial recursion—this is the exact same mechanism! The difference is that merge sort uses a divide-conquer approach: it drills down to base cases first, then works its way back up merging results, while Fibonacci branches out into multiple recursive calls that resolve in a different order. But the call stack is doing the same job in both cases: saving state and return addresses.

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