0

これは、単純な左再帰または末尾呼び出し再帰よりも少し複雑です。ですから、この種の再帰をどのように排除できるのか疑問に思っています。以下に示すように、私はすでに独自のスタックを保持しているため、関数はパラメーターや戻り値を必要としません。ただし、それはまだ特定のレベルまで自分自身を呼び出しています (または下げています)。私はこれをループに変えたいと思っていますが、これについてしばらくの間頭を悩ませていました。

すべての「実際のロジック」を printf("dostuff at level #n") メッセージに置き換えた単純化されたテスト ケースを次に示します。これは Go にありますが、この問題はほとんどの言語に当てはまります。ループと goto の使用は完全に許容されます (しかし、私はこれで遊んでみましたが、複雑になり、手に負えなくなり、そもそも機能しないように見えます)。ただし、追加のヘルパー関数は避ける必要があります。これをある種の単純なステート マシンに変換する必要があると思いますが、...どれでしょうか? ;)

実用性に関しては、これは毎秒約 2000 万回実行されます (スタックの深さは後で最大 1 から 25 の範囲になります)。これは、自分のスタックを維持することが、関数呼び出しスタックよりも安定して高速になる場合です。(この関数には他の関数呼び出しはなく、計算のみです。) また、ガベージが生成されない = ガベージが収集されません。

だからここに行きます：

func testRecursion () {
    var root *TMyTreeNode = makeSomeDeepTreeStructure()
    // rl: current recursion level
    // ml: max recursion level
    var rl, ml = 0, root.MaxDepth
    // node: "the stack"
    var node = make([]*TMyTreeNode, ml + 1)

    // the recursive and the non-recursive / iterative test functions:
    var walkNodeRec, walkNodeIt func ();

    walkNodeIt = func () {
        log.Panicf("YOUR ITERATIVE / NON-RECURSIVE IDEAS HERE")
    }

    walkNodeRec = func () {
        log.Printf("ENTER LEVEL %v", rl)
        if (node[rl].Level == ml) || (node[rl].ChildNodes == nil) {
            log.Printf("EXIT LEVEL %v", rl)
            return
        }
        log.Printf("PRE-STUFF LEVEL %v", rl)
        for i := 0; i < 3; i++ {
            switch i {
            case 0:
                log.Printf("PRECASE %v.%v", rl, i)
                node[rl + 1] = node[rl].ChildNodes[rl + i]; rl++; walkNodeRec(); rl--
                log.Printf("POSTCASE %v.%v", rl,  i)
            case 1:
                log.Printf("PRECASE %v.%v", rl, i)
                node[rl + 1] = node[rl].ChildNodes[rl + i]; rl++; walkNodeRec(); rl--
                log.Printf("POSTCASE %v.%v", rl,  i)
            case 2:
                log.Printf("PRECASE %v.%v", rl, i)
                node[rl + 1] = node[rl].ChildNodes[rl + i]; rl++; walkNodeRec(); rl--
                log.Printf("POSTCASE %v.%v", rl,  i)
            }
        }
    }

    // test recursion for reference:
    if true {
        rl, node[0] = 0, root
        log.Printf("\n\n=========>RECURSIVE ML=%v:", ml)
        walkNodeRec()
    }

    // test non-recursion, output should be identical
    if true {
        rl, node[0] = 0, root
        log.Printf("\n\n=========>ITERATIVE ML=%v:", ml)
        walkNodeIt()
    }

}

更新-ここでいくつかの議論を行い、さらに考えた後:

理論的には必要なことを行うはずの次の擬似コードを作成しました。

curLevel = 0
for {
    cn = nextsibling(curLevel, coords)
    lastnode[curlevel] = cn
    if cn < 8 {
        if isleaf {
            process()
        } else {
            curLevel++
        }
    } else if curLevel == 0 {
        break
    } else {
        curLevel--
    }
}

もちろん、私のカスタム ユース ケースの nextsibling() に記入するのは難しい部分です。しかし、必要な深さ優先のトラバーサル順序を維持しながら内部再帰を排除するための一般的な解決策と同様に、この大まかなアウトラインは何らかの形でそうする必要があります。

4

1 に答える 1

1

再帰コードが少し奇妙に見えるので、何をしたいのかよくわかりません。ただし、TMyTreeNode の構造を理解している場合、これは非再帰バージョンに対して行うことです。

// root is our root node
q := []*TMyTreeNode{root}
processed := make(map[*TMyTreeNode]bool
for {
  l := len(q)
  if l < 1 {
    break // our queue is empty
  }
  curr := q[l - 1]
  if !processed[curr] && len(curr.childNodes) > 0 {
    // do something with curr
    processed[curr] = true
    q = append(q, curr.childNodes...)
    continue // continue on down the tree.
  } else {
    // do something with curr
    processed[curr] = true
    q := q[:l-2] // pop current off the queue
  }
}

注: これは、構造の奥深くまで任意に進みます。それがあなたが望むものではない場合、いくつかの変更が必要になります。

于 2012-04-05T03:43:16.983 に答える