非再帰アルゴリズムへの再帰的な再帰の手助けが必要

Question

この実装にはスタック保護がないため、funtion呼び出しをヒープに確実に書き込むため、私は自分のmicropythonプラットフォームで再帰を使用できないことがわかりました。

私はこの再帰的なpythonコードを書き直さなければなりません。まだ解決策が見つかりませんでした。ここで

ランドマークが何であるか、いくつかのexplainations：

層 - 再帰は今、どのように「深いです」。最も深いレイヤーは、self.blobsのリストに依存します。レイヤーがlen（self.blobs）-1の場合、再帰が返される必要があります。そうでない場合は、再度再帰します。

firstIDとlastIDは（self.differenceValidに判明（））の組み合わせが可能であるか否かを見つけ出すためのパラメータ

possibleQueuesある戻り値です。ご質問がございましたら、お気軽に等しい

ある

[[0, 2, 4], [6, 8, 1, 3], [0, 2, 4], [1, 3]] 

LEN（self.blobs）とlen（self.possibleLandmarkIDs）： self.possibleLandmarkIDsは次のように、数字を含むネストされたリストです。あなたが私を助けることを願っています！

def findQueueCombinationsRecursive(self, layer, firstID, lastID): 
    possibleQueues = [] 
    for index in range(len(self.possibleLandmarkIDs[layer])): 
     landmarkID = self.possibleLandmarkIDs[layer][index] 
     if layer == 0: 
      firstID = self.possibleLandmarkIDs[layer][index] 
      lastID = self.possibleLandmarkIDs[layer][index] 
     if self.differenceValid(firstID, lastID, landmarkID): 
      if layer == len(self.blobs) - 1: 
       possibleQueues.append([]) 
       possibleQueues[len(possibleQueues)-1].append(landmarkID) 
      else: 
       deeperList = self.findQueueCombinationsRecursive(layer + 1, firstID, landmarkID) 
       if len(deeperList) == 0: 
        continue 
       for item in deeperList: 
        possibleQueues.append([]) 
        possibleQueues[len(possibleQueues)-1].append(landmarkID) 
        for i in item: 
         possibleQueues[len(possibleQueues)-1].append(i) 
    return possibleQueues 

Answer 1

ほとんどの場合、スタックを使用して再帰アルゴリズムを反復アルゴリズムに変換できます。結果がでている順序が同じであれば、あなたが気にしない場合は

def findQueueCombinationsRecursive(self): 
    results = [] 
    stack = [(0, None, None, [])] # items on the stack are 4-tuples 
    while stack: 
     layer, first_id, second_id, queue = stack.pop() 
     for landmark_id in reversed(self.possibleLandmarkIDs[layer]): 
      if layer == 0: 
       first_id = second_id = landmark_id 
      if self.differenceValid(first_id, second_id, landmark_id): 
       new_queue = queue + [landmark_id] 
       if layer == len(self.blobs) - 1: 
        results.append(new_queue) 
       else: 
        stack.append((layer+1, first_id, landmark_id, new_queue)) 
    return results 

：私は間違っているいくつかの小さなビットを持っているかもしれませんがここで（スタックとしてリストを使用して）あなたのコードを変換で簡単に刺すが、ですあなたの再帰的コードとして、forループのreversedコールを取り除くことができます。スタックはLIFO（ラスト・イン・ファースト・アウト）なので、元の順序でスタックからポップするために、アイテムを逆順にプッシュする必要があります。

あなたの問題を解決するための劇的に異なるアプローチを検討することもできます。たとえば、itertools.product(*self.possibleLandMarkIDs)ですべてのキューを生成できると思います。次に、各候補キューの各ステップに対してself.differenceValidメソッドを呼び出すことによって、無効なキューをフィルタリングする必要があります。