Создание итеративной функции вместо рекурсивной в python

Question

def sum(root): 
    if root.children == []: 
     return root.value 
    else: 
     temp = 0 
     for n in root.children: 
      temp += sum(n) 
     temp+= root.value 
    return temp 

Я получил свою функцию, чтобы работать рекурсивно, и я пытаюсь найти простой способ сделать это итеративно. Я просто пытаюсь найти руководство относительно того, буду ли я использовать цикл while или что.

Answer 1

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

Единственная разница между стеком и очередью заключается в том, что вы либо сначала обрабатываете глубину элементов (стек), либо сначала задыхаетесь (очередь).

Ваш рекурсивный код глубины первого, так чтобы повторить то же самое поведение итеративно использовать стек:

def sum_nodes_iteratively(root): 
    elements = [root] 
    total = 0 
    while elements: 
     element = elements.pop() 
     elements.extend(element.children) 
     total += element.value 
    return total 

Демо:

>>> class Node(object): 
...  def __init__(self, value, children): 
...   self.value = value 
...   self.children = children 
... 
>>> def sum_nodes_iteratively(root): 
...  elements = [root] 
...  total = 0 
...  while elements: 
...   element = elements.pop() 
...   elements.extend(element.children) 
...   total += element.value 
...  return total 
... 
>>> sum_nodes_iteratively(Node(1,[Node(2,[]),Node(3,[Node(4,[Node(5,[]),Node(6,[Node(7,[])])])])])) 
28