Need help understanding how this recursive function is working

Question

Here's a function (credit to user Abbot, for providing it in another question)

def traverse(ftp):

    level = {}
    for entry in (path for path in ftp.nlst() if path not in ('.', '..')):
        ftp.cwd(entry)
        level[entry] = traverse(ftp) 
        ftp.cwd('..')
    return level

Here's what I don't understand: When python enters the function it creates an empty dictionary (level). In the for loop, it stores a directory name as a key in the dictionary. as for the that key's value, python enters the function again and searches for a directory and it becomes that key's value.

But, how is the level dictionary remembering the values inside? I mean, shouldn't it be reset/emptied everytime python enters the function?

Answer 1

No. Every "instance" of the function has its own copy of level and there are no side effects between the various copies of level.

Take this folder tree:

root
 `-home
    |- lyrae
    |   |- ftp.py
    |   `- http.py
    `- badp

Here's the (simplified) execution flow when you call ftp on root:

• ftp(root) creates an empty level dictionary
• ftp(root) enumerates subfolders: (home).
• ftp(root) picks the first subfolder and changes directory into it.
• ftp(root) sets level[home] to the result of ftp in the current folder.

---

• ftp(home) creates an empty level dictionary
• ftp(home) enumerates subfolders: (lyrae, badp).
• ftp(home) picks the first subfolder and changes directory into it.
• ftp(home) sets level[lyrae] to the result of ftp in the current folder.

---

• ftp(lyrae) creates an empty level dictionary
• ftp(lyrae) enumerates subfolders: ().
• ftp(lyrae) is out of subfolders to parse and returns level.

---

• ftp(home) completes the assignment: levels = {'lyrae': {}}
• ftp(home) changes to the next folder.
• ftp(home) sets level[badp] to the result of ftp in the current folder.

---

• ftp(badp) creates an empty level dictionary
• ftp(badp) enumerates subfolders: ().
• ftp(badp) is out of subfolders to parse and returns level.

---

• ftp(home) completes the assignment: levels = {'lyrae': {}, 'badp': {}}
• ftp(home) is out of subfolders to parse and returns level.

---

• ftp(root) completes the assignment: levels = {'home': {'lyrae': {}, 'badp': {}}}
• ftp(root) is out of subfolders to parse and returns level.

Answer 2

These other answers don't quite explain enough I think. Each recursive entrance into this function creates a new local level dictionary. But crucially, also returns it. This means that the local version of level from each recursion becomes a dictionary tree of levels. Once the recursion is unrolled you're left with a tree of dictionaries which refer to each other. This means that the local variables that get created don't get garbage collected because there's a reference to the top most level dictionary on the stack that's been returned from the outer most function.