Алгоритм глубины дерева работает как определение функции, но не как определение метода

Question

Я написал алгоритм для рекурсивного получения глубины дерева. В определении функции, она работает:

def tree_depth_f(tree): 
    """Counts the maximum depth of a tree."""   
    def recursive_count(node): 
     """Recursive count function.""" 
     childs = tree[node] 
     if childs == None: 
      return 0 
     else: 
      maxh = 0 
      for i in xrange(len(childs)): 
       h = recursive_count(childs[i]) 
       if maxh < h: 
        maxh = h     
      return int(1 + maxh) 

    root = tree['root'] 
    depth = recursive_count(root) 
    return depth 

Но тот же алгоритм, как определение метода не работает:

class MyClass: 
    def __init__(): 
     pass 

    def tree_depth(self, tree): 
     """Counts the maximum depth of a tree."""   
     def recursive_count(node): 
      """Recursive count function.""" 
      self.childs = tree[node] 
      if self.childs == None: 
       return 0 
      else: 
       self.maxh = 0 
       for i in xrange(len(self.childs)): 
        self.h = recursive_count(self.childs[i]) 
        if self.maxh < self.h: 
         self.maxh = self.h     
       return int(1 + self.maxh) 

     self.root = tree['root'] 
     self.depth = recursive_count(self.root) 
     return self.depth 

tree это словарь списков. Это, как я проверяю эти коды:

tree = {0: [1], 1: [2], 2: [3, 4], 3: None, 4: None, 'root': 0} 
m = MyClass() 
print "As a function:", tree_depth_f(tree) 
print "As a method:", m.tree_depth(tree) 

Вот графическое представление tree в этом примере:

Определение функции работает нормально, но когда я использую метод определение, я получаю следующее сообщение об ошибке:

TypeError: 'NoneType' object has no attribute '__getitem__' 
    at Answer.py. in recursive_count on line 102 
    at Answer.py. in recursive_count on line 102 
    at Answer.py. in recursive_count on line 102 
    at Answer.py. in tree_depth on line 108 
    at Answer.py. in <module> on line 157 

Линия 102, 108 и 157 в исходной точке коды к ним:

102: self.h = recursive_count(self.childs[i]) 
108: self.depth = recursive_count(self.root) 
157: print "As a method:", m.tree_depth(tree) 

После много отладки, я обнаружил, что, когда определение метода находит лист (узел которого self.childs является None) и начинает возвращаться из рекурсии, self.childs родительского узла None тоже. Понятия не имею почему. Определение функции работает нормально. Не могли бы вы, ребята, помочь мне?

Answer 1

Вы изменяете self.childs, который здесь эффективно действует как глобальная переменная (поскольку она записывается на объект, который сохраняется через разные вызовы рекурсивной функции). У вас нет одного объекта на узел, у вас есть один объект, период. Таким образом, нет «self.childs родительского узла», у вас есть только один self.childs, на одном self. Когда рекурсия выходит из ветви return 0, переменная self.childs равна None.

В вашем функциональном коде ваш childs является локальной переменной, поэтому каждый вызов функции получает отдельную копию; вам действительно нужно это, будь то по методу или по функции.

Просто удалите self., чтобы не было переменной childs. Действительно, нет необходимости, чтобы какая-либо из переменных была переменными экземпляра, поскольку вы не используете объектно-ориентированную функциональность.