Python Forum

I'm going to try explaining what I understand here, and hopefully someone can help me understand this. I'm running python 3.6.1 on CentOS 7.

I'm looking at 2 pieces of code, one is a recursive Depth First Search algorithm, and the other is a recursive fibonacci algorithm that uses memoization to store fibonacci numbers that have already been calculated. The DFS algorithm takes a list named 'path' as a parameter, and the fibonacci algorithm takes a dictionary named 'memo' as a parameter. I'll post the code for the algorithms and then continue with my question.

DFS and Related Classes

class Node(object):
    def __init__(self, name):
        self.name = name
    def getName(self):
        return self.name
    def __str__(self):
        return self.name

class Digraph(object):
    def __init__(self):
        self.nodes = []
        self.edges = {}
    def addNode(self, node):
        if node in self.nodes:
            raise ValueError('Duplicate node')
        else:
            self.nodes.append(node)
            self.edges[node] = []
    def addEdge(self, edge):
        src = edge.getSource()
        dest = edge.getDestination()
        if not (src in self.nodes and dest in self.nodes):
            raise ValueError('Node not in graph')
        else:
            self.edges[src].append(dest)
    def childrenOf(self, node):
        return self.edges[node]
    def hasNode(self, node):
        return node in self.nodes
    def __str__(self):
        result = ''
        for src in self.nodes:
            for dest in self.edges[src]:
                result = result + src.getName() + '->' + dest.getName() + '\n'
        return result[:-1] # remove the trailing newline

def printPath(path):
    """Assumes path is a list of nodes"""
    result = ''
    for i in range(len(path)):
        result += str(path[i])
        if i != len(path) - 1:
            result += '->'
    return result

def DFS(graph, start, end, path, shortest, toPrint = False):
    """Assumes graph is a Digraph; start and end are nodes;
        path and shortest are lists of nodes"""
    path = path + [start]
    if toPrint:
        print('Current DFS path:', printPath(path))
    if start == end:
        return path
    for node in graph.childrenOf(start):
        if node not in path: #avoid cycles
            if shortest == None or len(path) < len(shortest):
                newPath = DFS(graph, node, end, path, shortest, toPrint)
                if newPath != None:
                    shortest = newPath
    return shortest

Recursive Fibonacci

def fastFib(n, memo = {}):
    """Assumes n is an int >= 0, memo used only by recursive calls
    Returns fibonacci of n"""
    if n == 0 or n == 1:
        return 1
    try:
        return memo[n]
    except KeyError:
        result = fastFib(n-1, memo) + fastFib(n-2, memo)
        memo[n] = result
        return result

Now, when studying fastFib, I initially thought that whenever memo was updated with a newly calculated fib(n), that updated memo was only visible inside of the frame associated with the recursive call to fasFib() that calculated the value. Someone explained to me that mutable types are passed by reference, and that there is only one memo and it exists in the frame of the initial call. Any updates to the contents of memo made by further recursive calls actually update that one memo from the initial frame, and so its contents are visible to in all of the other frames arising from the recursive calls to fastFib.

I thought I understood this until I studied the DFS algorithm. I would have expected path to behave in DFS the same way memo did in fastFib. It doesn't. When the contents of path get updated, the new content is only visible in the frame associated with the recursive call to DFS that updated path. So, now I'm confused. I do realize that this is actually what allows DFS to return to a previous node and check a different pathway in a graph. But I don't understand why. And now I'm not sure I understand why memo behaves the way it does.

I could use some help wrapping my head around this.

In DFS, the line path = path + [start] creates a new list every time it is called. After this line, the old value of path is no longer available in the current scope. On the contrary, fastFib's recursive calls always use the same dictionary instance.

Thank you! Basic enough thing in hindsight but I swear I was willing to spend all my remaining time in the course trying to get this.