Profondeur de parcours de traversée de l'arbre Python dépassée

Question

J'ai une arborescence de segments qui contient des données pour une plage de nombres (structure de données choisie here). Voici le code:

class SegmentTree: 
    def __init__(self, N): 
     def _init(b, e): 
      if b is e: 
       data = foo() # No dependency 
       return Node(b, e, data, None, None) 
      else: 
       mid = (b + e)/2 

       L = _init(b, mid) 
       R = _init(mid + 1, e) 

       data = foo() #Data depends on L and R 

       return Node(b, e, data, L, R) 

     self.root = _init(1, N) 

Cela échoue pour N autour de 300 avec une profondeur de récursivité maximale dépassée erreur. Y at-il un moyen de créer l'arbre de manière itérative au lieu de récursivement?

Answer 1

Le vrai problème n'est pas la profondeur de récursivité de votre algorithme, qui devrait être d'environ 10 pour une valeur de 300, mais que vous comparez les nombres avec is. Les contrôles de mots clés pour l'identité des objets is, tandis que == contrôles pour l'égalité:

>>> 300 == 299+1 
True 
>>> 300 is 299+1 
False 

En raison de que votre état if qui devrait mettre fin à la récursion ne sera jamais vraie et la fonction gardera récursion, même si b et e sont égaux .

Si vous modifiez le if ce problème devrait disparaître:

if b == e: 
    ... 

Pour un petit nombre le problème pourrait ne pas se produire parce que Python "caches" and reuses the objects pour ints jusqu'à une certaine taille.

Answer 2

En général, la conversion de la récursivité en itérative consiste à gérer la pile (ou la file d'attente) manuellement.

Quelque chose comme:

while stack is not empty: 
    item = pop from stack 

    do processing (such as adding onto the node) 

    push L and R onto the stack 

La pile ne pousse en mémoire, puisque pour chaque élément que vous poussent comme des champignons, vous poussez deux.