Выход из рекурсивной функции

Question

Итак, скажем, у меня есть несколько узлов. Каждый узел имеет список узлов, к которым он может перейти. Этот список узлов может включать сам. Мне нужно создать все возможные пути, которые узел может принимать, которые имеют длину n.

Например: допустим несколько вещей.

• У меня есть узел А и узел В
• мне нужны все возможные пути, которые не являются три длинные (не короче)
• Узел может пойти к себе и узел В
• Узел B может идти к себе и узел а

Предполагая, что тогда все пути я могу построить являются:

1. А.А.
2. AAB
3. ABA
4. ABB
5. BAA
6. BAB
7. BBA
8. ВВВ

Это код, я прямо сейчас; он работает, но в моем фактическом случае мне нужно, чтобы пути были длинными с восемью узлами. Это, очевидно, приводит к некоторым проблемам с производительностью. Я попал в MemoryError, работающий на 32-битной версии Python2.7. Я еще не пробовал 64-битную версию. Очевидная проблема - моя текущая реализация. Я думал, что, возможно, использование урожая/генераторов поможет некоторым. Не так ли? Если да, то как я мог бы реализовать использование урожая в моем случае?

Также я не ограничен Python 2, если у Python 3 есть некоторые функции, которые достигнут того, что я прошу. Python 2 - это то, что на моем самом эффективном компьютере.

PARTS = 3 

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

    if depth >= 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 

Answer 1

можно преобразовать текущее решение генератора самым простым способом путем изменения возвращения вызовов урожайности ... что может быть достаточно ... это не может также .. есть некоторые библиотеки graphtraversal там, как хорошо, что может решить это очень красиво, если ваша цель - просто решить проблему.

PARTS = 3 

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

    if depth >= 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