递归函数中的 Python 命名空间

Question

与我如何到达那里相比，我的问题相对简单。每次函数调用自身时，Python 中的递归函数是否会创建一个新的命名空间？

我在阅读归并排序时遇到了这个教程:https://interactivepython.org/runestone/static/pythonds/SortSearch/TheMergeSort.html#lst-merge

def mergeSort(alist):
    print("Splitting ",alist)
    if len(alist)>1:
        mid = len(alist)//2
        lefthalf = alist[:mid]
        righthalf = alist[mid:]

        mergeSort(lefthalf)
        mergeSort(righthalf)

        i=0
        j=0
        k=0
        while i < len(lefthalf) and j < len(righthalf):
            if lefthalf[i] < righthalf[j]:
                alist[k]=lefthalf[i]
                i=i+1
            else:
                alist[k]=righthalf[j]
                j=j+1
            k=k+1

        while i < len(lefthalf):
            alist[k]=lefthalf[i]
            i=i+1
            k=k+1

        while j < len(righthalf):
            alist[k]=righthalf[j]
            j=j+1
            k=k+1
    print("Merging ",alist)

alist = [54,26,93,17,77,31,44,55,20]
mergeSort(alist)
print(alist)

我对分而治之的理解已经足够好了，但目前我无法解决的是我在上面提出的问题。我可以按照代码进行操作，但我不太了解使用 lefthalf 作为传递到 mergeSort 的递归函数调用的参数。

我知道当在底部第一次调用合并排序时，alist 被分成 [54, 26, 93, 17] 和 [17, 77, 31, 44, 55, 20]。这些是左半边和右半边。然后在左半部分调用 mergeSort。这是我感到困惑的地方。对 mergeSort 的递归调用是否创建了一个全新的命名空间，这就是为什么传入的左半部分不会与函数中定义的左半部分发生冲突？

我知道这个问题的答案非常简单和基本，因此非常感谢您的耐心。提前致谢!

Answer 1

Does the recursive call to mergeSort create a whole new namespace, [...]?

是的。

每当解释器遇到对函数的调用时，它都会创建一个框架对象，并将其推送到框架堆栈。每次创建框架时，都会为该框架提供自己的私有(private)命名空间，其中重新定义框架中的每个变量。

在您的情况下，每次 mergeSort()被调用时，Python 会创建一个新的框架对象，并将其推送到框架堆栈。每次 Python 通过对 mergeSort() 的调用创建一个框架时, lefthalf被重新定义。

打几个电话到 print() ，可以看到 lefthalf的值每次调用 mergeSort() :

 This is the 1 recursive call to mergeSort()
 lefthalf is:  [54, 26, 93, 17]
 alist is:  [54, 26, 93, 17, 77, 31, 44, 55, 20]
  This is the 2 recursive call to mergeSort()
  lefthalf is:  [54, 26]
  alist is:  [54, 26, 93, 17]
   This is the 3 recursive call to mergeSort()
   lefthalf is:  [54]
   alist is:  [54, 26]
    This is the 4 recursive call to mergeSort()
     This is the 5 recursive call to mergeSort()
      This is the 6 recursive call to mergeSort()
      lefthalf is:  [93]
      alist is:  [93, 17]
       This is the 7 recursive call to mergeSort()
        This is the 8 recursive call to mergeSort()
         This is the 9 recursive call to mergeSort()
         lefthalf is:  [77, 31]
         alist is:  [77, 31, 44, 55, 20]
          This is the 10 recursive call to mergeSort()
          lefthalf is:  [77]
          alist is:  [77, 31]
           This is the 11 recursive call to mergeSort()
            This is the 12 recursive call to mergeSort()
             This is the 13 recursive call to mergeSort()
             lefthalf is:  [44]
             alist is:  [44, 55, 20]
              This is the 14 recursive call to mergeSort()
               This is the 15 recursive call to mergeSort()
               lefthalf is:  [55]
               alist is:  [55, 20]
                This is the 16 recursive call to mergeSort()
                 This is the 17 recursive call to mergeSort()
[17, 20, 26, 31, 44, 54, 55, 77, 93]
>>>