ネストされたリストをトラバースし、再帰を伴わない各要素に相互依存する値を代入する（Python）

Question

入力データの中には、再帰深度エラーを超えるものがあるため、次の関数の再帰を解消したい。 Increasing the recursion depthは、長期的には解決策ではありません。

def foo(x): 
    for element in x.elements: 
     element.depth = x.depth + 1 
     self.foo(element) 

は元のリスト構造を保持する必要があるため適用されません。

This solutionは、再帰を含むジェネレータを使用します。それが発電機であるという事実は違いを生みますか？

最後に、stack approachがあります。ここでは、これが割り当てられる値の相互依存性から100％適用可能かどうかはわかりません。

エレガントな（Pythonic）、非再帰的な解決策は何でしょうか？

Answer 1

基本的にデータにDFSを実装しています。あなたのデータは、各要素がノードであり、2つの要素間の接続がエッジであるグラフです。

要素を反復してスタックにプッシュし、スタックがなくなるまで再帰DFSをスタックDFSに簡単に置き換えることができます。

small difference in the ordering of elementsが存在する可能性があることに注意してください。しかし、それは容易に解決することもできます。

DFSのための擬似コードは次のようになります。

def foo(x): 
    s = new stack 
    s.push(x) 
    while not s.empty() 
    e = s.pop() 
    for element in e.elements: # or elements[::-1] for reversed order 
      element.depth = e.depth + 1 
      s.push(element) 
      # if data structure is not a tree, add visited set. 

Answer 2

def foo(x): 
    stack = [(x,0)] 
    while stack: 
     node,depth = stack.pop(0) 
     node.depth = depth 
     stack.extend([(ele,depth+1) for ele in node.elements if ele]) 

が、私は、少なくとも...あなたの説明に基づいて考える