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

level is a local variable. Every "run" of the function has its own variable called level, so the variables don't interfere with each other.

Answer 2

The scope of level is limited to the function only. Even if a function calls itself, it doesn't mean that that function call's internal variables (a different level) is the same as this one's.

Answer 3

variable level exists only in the scope of a function, at the end of function local variables discarded, so for each execution of traverse there will be it's own level dictionary. Nothing will be re-written or over-written.

Answer 4

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 5

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.