이 재귀 유형을 제거하는 방법은 무엇입니까?

Question

이것은 간단한 왼쪽 재귀 또는 꼬리 호출 재귀보다 약간 복잡합니다. 그래서 이런 종류의 재귀를 제거 할 수 있을지 궁금합니다. 아래에서 볼 수 있듯이 이미 스택을 유지하고 있으므로 함수에는 매개 변수 나 반환 값이 필요하지 않습니다. 그러나, 그것은 여전히 ​​자신을 특정 레벨까지 (또는 아래로) 부르고 있으며 이것을 루프로 바꿔 놓고 싶지만, 지금 당분간 내 머리를 긁적 거리고 있습니다.

단순한 테스트 케이스는 모든 "실제 로직"을 printf ("레벨 #n에서"dostuff ") 메시지로 대체합니다. 이것은 Go에 있지만 문제는 대부분의 언어에 적용됩니다. 루프와 고토의 사용은 완벽하게 받아 들여질 수 있습니다 (하지만 이걸 가지고 놀았고, 뒤죽박죽이되어 버렸습니다. 그리고 처음에는 겉으로보기에는 쓸모가 없었습니다). 그러나 추가 도우미 기능은 피해야합니다. 이걸 일종의 단순한 상태 기계로 바꾸어야한다고 생각하지만 ... 어느 쪽? ;)

실용성에 관해서는, 이것은 초당 약 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() 
    } 

}

UPDATE가는 - 어떤 여기 토론, 추가 사고 후 :

난 그냥 다음 의사 코드를 제작하는 이론 은이 필요합니다.

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()을 채울 것입니다. 그러나 필요한 깊이 우선 탐색 순서를 유지하면서 내부 재귀를 제거하는 일반적인 해결책과 마찬가지로이 대략적인 개요는 어떤 형태로든 그렇게해야합니다.

Answer 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 
    } 
} 

참고 : 이는 구조에 임의로 적용됩니다. 그것이 당신이 원하는 것이 아니라면 약간의 수정이 필요할 것입니다.