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