반복자로 재귀 알고리즘을 구현할 수 있습니까?

StackOverflow https://stackoverflow.com/questions/1201560

  •  05-07-2019
  •  | 
  •  

문제

나는 다음과 같은 나무를 주었다.

http://www.seqan.de/dddoc/html/streepreorder.png http://www.seqan.de/dddoc/html/streepreorder.png

다음 연산자와 함께 각 노드를 Accs 할 수 있습니다.

// postorder dfs
Iterator< Index<String<char> >, BottomUp<> >::Type myIterator(myIndex);
for (; !atEnd(myIterator); goNext(myIterator)) 
    // do something with myIterator

그러나 나는 트리에 재귀 알고리즘을 사용하고 싶습니다.
재귀 알고리즘을 만들 수있는 방법이 있습니까 (각 노드에서 가장 큰 하위 트리를 배출) 반복적 인 방법이 있습니까?
아니면 어떻게 요소를 비활성으로 비활성화 할 수 있습니까?

편집 : 실제 문제 :
나는 나무에서 작동하는 재귀 알고리즘을 주었다. (재귀)
또한 반복자 (비 표준, 반복적)로 항목 만 액세스 할 수있는 라이브러리를 사용합니다.

재귀 <-> 반복.
이것을 어떻게 해결할 수 있습니까?

도움이 되었습니까?

해결책

반복자가 트리의 링크 나 빠른 임의의 액세스를 따르지 않지만 트리 알고리즘을 적응시키는 데 어려움을 겪게 될 것입니다. 그러나 결국 모든 답변은 귀하가 제공하지 않은 사용자 정의 반복자가 제시 한 인터페이스에 따라 다릅니다.

예를 들어, 트리 검색의 쉬운 알고리즘을 고려하십시오. 반복자가 제공 한 유일한 작업이 "첫 번째 요소에서 시작하여 일대일로 이동"이라면 트리 검색을 효율적으로 구현할 수는 없습니다. 이진 검색도 구현할 수 없습니다. 따라서 정확히 어떤 작업이 지원되는지에 대한 목록을 제공해야하며, 각각의 복잡성 경계를 (중요하게) 제공해야합니다.

다른 팁

당신은 변환 할 수 있습니다 저것 스택의 도움으로 반복적 인 함수에 대한 재귀 기능.

//breadth first traversal pseudo-code
push root to a stack
while( stack isn't empty )
    pop element off stack
    push children
    perform action on current node

노드를 가로 지르는 방식에 따라 구현이 다릅니다. 모든 재귀 함수는 반복적 인 기능으로 변환 될 수 있습니다. 특정 문제에 대한 정보가 필요한 방법에 대한 일반적인 사용. 스택/큐를 사용하고 루프로 변환하는 것은 대부분의 상황을 해결 해야하는 일반적인 방법입니다.

또한 꼬리 재귀와이를 식별하는 방법을 살펴 봐야합니다. 이러한 문제는 루프 용으로 잘 해석되므로 많은 컴파일러가이를 수행하기도합니다.

수학적으로 지향적 인 재귀 호출은 다음과 같이 해결할 수 있습니다. 재발 관계. 아직 해결되지 않은 것들을 만날 가능성은 거의 없지만 관심이있을 수 있습니다.

// 편집, 성능? 실제로 구현과 트리의 크기에 따라 다릅니다. 재귀 호출에 깊이가 많은 경우 스택 오버플로가 발생하고 반복 버전은 잘 작동합니다. 재귀를 더 잘 이해할 수있을 것입니다 (메모리가 사용되는 방법). 상황에 더 나은 것이 더 나은 것을 결정할 수 있어야합니다. 다음은 Fibonacci 번호를 사용한 이러한 유형의 분석의 예입니다..

재귀 함수는 스택으로 구현 될 수 있습니다. 이것이 당신이 묻는 질문이라면.

여기에 있습니다 Phil Haack의 기사 주제에.

성능 이익은 한 방향 또는 다른 방법으로 추론 적이며, 컴파일러는 항상 예측할 수없는 무대 뒤에서 코드를 사용합니다. 둘 다 구현하고 실수를 얻으십시오. 비슷한 사용이라면 더 읽기 쉬운 것을 사용하십시오.

재귀 반복이 있더라도 노드 당 노드 방문으로 끝납니다.

당신이 알아야 할 것은 : 내 반복자가 어떻게 깊이 우선으로 가야한다는 말을 할 수 있습니까? 그런 다음 : 한 레벨이 시작/종료되었음을 알 수 있습니다 (즉, 재귀 단계의 시작/끝).

그 지식은 재귀 알고리즘에 매핑 될 수 있습니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top