패턴은 하노이 타워 문제에 대한이 고전 재귀 의사 솔루션을 고려 재귀 알고리즘과 이벤트 중심의 소비자

Question

사이에 조정하기 :

void move(num,src,dest,spare) { 
     if(num == 1) { 
     moveSingle(src,dest); 
     } else { 
     move(num-1,src,spare,dest); 
     move(1,src,dest,spare); 
     move(num-1,spare,dest,src); 
     } 
    } 

을 ... 그리고 디스플레이 엔진 등의 이벤트 루프를 고려 처리

void draw() { 
     // code to draw a single frame goes here; for example 
     if(! aDiscIsInMotion()) { 
      getNextMove(); 
     } 

     updateCoordinates(); 
     drawMovingDisc(); 
    } 

두 패턴간에 어떤 좌표가 있습니까?

두 가지 옵션이 마음에 와서 :

스레드와 큐

을 자체 스레드에서 재귀 함수를 시작

. moveSingle()는 FIFO 큐로 이동을 기록합니다. 대기열의 용량이 초과되면 차단 될 수 있습니다. getNextMove()는 큐에서 이동을 읽습니다.

나는 이것이 잘 동작 할 것이라고 확신하지만, 스레딩을 피하는 패턴이 있는지 궁금합니다.

대신 오히려 호출 스택보다는 힙에 LIFO 큐를 사용하도록 재귀 알고리즘을 다시 작성

를 재귀의 명시 적 스택을 사용합니다. 예 :

Move getMove() { 
    if(lifo.isEmpty()) { 
     return null; 
    } 
    State state = lifo.pop(); 
    while(state.num != 1) { 
     lifo.push(new State(state.num -1, state.spare, state.dest, state.src)); 
     lifo.push(new State(1, state.src, state.dest, state.spare)); 
     lifo.push(new State(state.num -1, state.src, state.spare, state.dest)); 
     state = lifo.pop(); 
    } 
    return new Move(state); // guaranteed num==1 
} 

... 다시 작동하지만 상태를 보존하기 위해 호출 스택을 사용하여 표현력을 상실합니다.

내가 찾지 못한 또 다른 기술이 있습니까?

하노이 타워와 처리의 예를 선택 했음에도 불구하고 이것은 재귀 알고리즘을 업데이트를 위해 폴링하려는 다른 인터페이스와 통합하는 일반적인 문제로 고안되었습니다. 그래서 저는 "하노이를 해결하기 위해 스택이 필요 없습니다"와 같은 대답에 관심이 없습니다. - 저도 압니다.

Answer 1

코 루틴은 일부 언어 (예 : 자바)에서 빠져 있지만 coroutines가 있습니다. 코 루틴을 사용하면 산출물 루틴이 실제로 완료되기 전에 호출 루틴에 양보 할 수 있습니다. 나는 자바를위한 라이브러리가 있다는 것을 알고있다. coroutines를 지원하기 위해 바이트 코드를 다시 작성한다. 자바를 목표로한다면 당신은 그것을 조사해야 할 것이다.

언급 한 두 가지 변종은 근본적으로 대안입니다. 산출하려는 중간 결과를 멀티 스레드 또는 대기열에 넣습니다. 특정 경우에는 알고리즘에 상호 작용이 없으므로 알고리즘 내부를 확인하는 대신 실제로 전체 대기열을 미리 만들 수 있습니다.

편집 : 수익률이 재귀와 잘 작동하는지 확실하지 않습니다. 내 지식은 더 이론적이다. 제 생각에 직접적으로 또는 재귀 호출에서 추가로 항복함으로써 여러 수준을 산출 할 수 있어야한다고 생각합니다.