Python Namespaces in Recursive Functions

Question

My question is relatively simple compared to how I got there. Do recursive functions in Python create a new namespace each time the function calls itself?

I was doing some reading on mergesort and came across this tutorial: 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)

I'm understanding the divide-and-conquer well enough, but what I can't get past at the moment is the question I asked above. I can follow the code, but I'm not quite understanding the use of lefthalf as the argument that gets passed into the recursive function call of mergeSort.

I get that when mergeSort is first called way down at the bottom, alist gets chopped into [54, 26, 93, 17] and [17, 77, 31, 44, 55, 20]. These are lefthalf and righthalf. Then mergeSort gets called on lefthalf. This is where I get confused. Does the recursive call to mergeSort create a whole new namespace, and is that why the lefthalf that gets passed in doesn't collide with the lefthalf defined within the function?

I know the answer to this is really simple and fundamental, so your patience is much appreciated. Thanks in advance!

Answer 1

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

Yes.

Whenever the Interpreter encounters a call to a function, its creates a frame object, which is pushed to a frame stack. Each time a frame is created, that frame is given its own private namespace, where each variable in the frame is re-defined.

In your case, each time mergeSort() is called, Python creates a new frame object, and pushes it to the frame stack. Each time Python creates a frame from a call to mergeSort(), lefthalf is re-defined.

With a few well placed calls to print(), you can see the value of lefthalf at each call to 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]
>>> 

Answer 2

Yes, a function call (any function call, not just recursive ones) creates a new namespace. BUT, when given as parameters, objects are passed by reference (in your example, the object is a list).

So, the new namespace get its own copy of this reference but it still refers to the same object as in the calling function, and if you change the content of that object, you will notice the change in the calling function.

Not sure I'm being clear enough. Here is a nice diagram that may help understanding how this works.