Yielding from a recursive function
<p>So let us say I have a few nodes. Each node has a list of nodes it can go to. This list of nodes can include itself. What I need to do is build all possible paths a node can take that are of n-length.</p>

<p>For example: Let's assume a few things. </p>

<ul>
<li>I have node A and node B</li>
<li>I need all possible paths that are three long (No shorter)</li>
<li>Node A can go to itself and node B</li>
<li>Node B can go to itself and node A</li>
</ul>

<p>Assuming that then all paths I can build are:  </p>

<ol>
<li>AAA  </li>
<li>AAB  </li>
<li>ABA  </li>
<li>ABB  </li>
<li>BAA  </li>
<li>BAB  </li>
<li>BBA  </li>
<li>BBB      </li>
</ol>

<p>This is the code I have right now; it works, but in my actual case I need the paths to be eight long with quite a few nodes. This obviously leads to some performance problems. I hit a MemoryError running on a 32bit version of Python2.7. I haven't tried the 64bit version yet. The obvious problem at hand is my current implementation. I thought maybe using yield/generators would help some. Would it? If so how would I even implement using yields in my case?</p>

<p>Also I'm not limited to Python 2 if Python 3 has some features that would achieve what I'm asking. Python 2 just happens to be what is on my best performing computer.</p>

<pre><code>PARTS = 3

def dive(node, depth=0):
    combos = []

    if depth &gt;= PARTS - 1:
        if node.key:
            return ((node.key,),)
        return ()

    for next_ in node.next_nodes:
        for combo in dive(next_, depth=depth+1):
            if not node.key:
                continue
            combos.append((node.key,) + combo)
    return combos
</code></pre>

<p>you could convert your current solution to a generator the easiest way by changing the return calls to yields ... that may be enough ... it might not also.. there are some graphtraversal libraries out there as well that may solve this very nicely if your goal is simply to solve the problem</p>

<pre><code>PARTS = 3

def dive(node, depth=0):
    combos = []

    if depth &gt;= PARTS - 1:
        if node.key:
            #return ((node.key,),)
            yield ((node.key,),)
        #return ()
        yield ()
    for next_ in node.next_nodes:
        for combo in dive(next_, depth=depth+1):
            if not node.key:
                continue
            combos.append((node.key,) + combo)
    #return combos
    yield combos

for result in dive(node):
    print result
</code></pre>

python recursion