Memory error in recursive function (Python 2.7.3)

Question

I'm running into a memory error in one of my recursive function.

def allPaths(self, adjMat, start, stop, flag=[0], walks=[]):
    walks = walks + [start]
    if start == stop:
        return [walks]
    loc = 0
    flag=flag*len(adjMat)
    output = []
    for value in adjMat[start]:
        if value > 0.0:
            if flag[loc] < 3:
                flag[loc]+=1
                paths = self.allPaths(adjMat, loc, stop, flag, walks)
                for k in paths:
                    output.append(k)
        loc += 1
    return output

One example input is fine but I get a memory error with different matrix.

>>>print test.allPaths([[0.0, 0.9, 0.0, 0.0, 0.0, 0.0, 0.1, 0.0],
          [0.0, 0.0, 1.0, 0.0, 0.0, 0.0, 0.0, 0.0],
          [0.0, 0.0, 0.0, 1.0, 0.0, 0.0, 0.0, 0.0],
          [0.0, 0.0, 0.0, 0.8, .15, .05, 0.0, 0.0],
          [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 1.0],
          [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 1.0],
          [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 1.0],
          [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0]],0,7)
[[0, 1, 2, 3, 3, 3, 4, 7], [0, 1, 2, 3, 3, 3, 5, 7], [0, 1, 2, 3, 3, 4, 7], [0, 1, 2, 3, 3, 5, 7], [0, 1, 2, 3, 4, 7], [0, 1, 2, 3, 5, 7], [0, 6, 7]]

>>>print test.allPaths([[0.0, 1.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0],
          [0.0, 0.0, 0.0, 1.0, 0.0, 0.0, 0.0, 0.0],
          [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 1.0],
          [0.8, 0.0, 0.0, 0.0, .05, .15, 0.0, 0.0],
          [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 1.0],
          [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 1.0],
          [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0],
          [0.9, 0.0, 0.1, 0.0, 0.0, 0.0, 0.0, 0.0]],0,7)

The error seems to occur at the line "flag=flag*len(adjMat)". Any suggestions?

I'm not sure if this is the problem, but one thing you should probably avoid is to use mutable default arguments like `[0]` and `[]`, as they are only evaluated once on function definition (not every time you call the function as you might expect). See the explanation and discussion [here](http://stackoverflow.com/questions/1132941/least-astonishment-in-python-the-mutable-default-argument). — andersschuller, Jul 10 '13 at 20:55

score 1 · Accepted Answer · answered Jul 10 '13 at 20:59

Each recursive call increases the size of the flag list by a factor of len(adjMat).

The first call to the function uses a flag list with len(adjMat) elements and passes it to the recursive call. There the list will be multiplied by len(adjMat), resulting in len(adjMat) * len(adjMat) elements. With a few recursive calls this can quickly get out of hand and you probably run out of memory to store this excessively large flag list.

Memory error in recursive function (Python 2.7.3)

1 Answers1