시벌벌

아직도 손이 부르르 떨리네

하노이 타워 재귀구현이 왜  이해가 안가지

 

아니 하노이에서

기둥이 123있을떄

 

최상위 n-1개의 접시들을 기둥 2로 옮기고

n번째 접시를 기둥 3으로 옮기고

다시 기둥 n-1개의 접시들을 기둥 3으로 옮긴다는데

 

의사코드로 보면

Hanoi(갯수, 시작, 목표, 오픈) //시작이 기둥1, 목표가 기둥3, 오픈이 기둥2

IF(갯수 > 0)

Hanoi(갯수-1, 시작, 오픈, 목표) //여기서 갯수-1개가  기둥1에서 시작해서 기둥2로 가니까 시작에서 오픈을 목표로 두고 재귀함수호출하고        

Move 이동(갯수, 시작, 목표) //n번째 접시를 기둥1에서 기둥3으로 옮겼고

Hanoi(갯수-1, 오픈, 목표, 시작) //갯수-1개가 기둥2인 오픈에 모여있고 최종 목표로 가니까 재귀호출 

 

주석표현대로 이해하면되?

아오 그런데 이해가 안가는게  만약에 접시가 4개 있다 치자

 

그럼 저걸 재귀함수가 스택에 쌓이는대로 쭉 써보면

 

Hanoi(4, 1,3,2) //함수 실행!

Hanoi(3, 1,2,3)

Hanoi(2, 1,3,2)

Hanoi(1, 1,2,3)

Move(1, 1, 2)

Hanoi(1, 3,2,1)

Move(3, 2)

.

.

. 아 못하겠네 어쩄든 왔다갔다 엄청 하는데..아니 이렇게 왔다 갔다 하는걸 어떻게 저 위에 말도 안되는 재귀함수 호출로 이해가 가능한거야?

 

형들 지금은 한강물 많이 춥지?.....불쌍한 동생 머리에 이해좀 시켜줘요..