알고리즘 :: 컴파일러도 "귀찮다" 라고 말하는 하노이 탑 문제

2009/01/13 23:44


사용자 삽입 이미지

난 단지 지쳐서 Ctrl+C 눌렀을 뿐이고.

얘는 단지 귀찮다고 말할 뿐이고.


하노이 탑 문제를 재귀호출을 이용하여 풀다가 지쳐서 중지시켰는데, 컴파일러가 저런 메시지를 보여줬습니다. 어디에 이런 XBox가 숨어있는건지... ㅋ


하노이 탑을 풀면서 생각한 겁니다만, 재귀호출은 현재를 기반으로 하여 과거를 예측하는 문장이라는 생각이 듭니다. 항상 마지막 과정을 시작으로 하여 처음 과정을 유추하고 결과를 재생하죠.


하노이 탑 문제가 궁금하시다면..


재귀 호출을 이용한 소스가 궁금하시다면..

크리에이티브 커먼즈 라이센스
Creative Commons License

6l4ck3y3 0x07 알고리즘 , , , , ,

Trackback Address:이 글에는 트랙백을 보낼 수 없습니다
  1. Blog Icon
    박병언

    안녕하세요^^ C 를 공부하고 있는 학생인데요.

    죄송하지만 복사를 해서 실행시켜 보았습니다.

    다른 하노이 프로그램 보다

    더욱 짧고 간단하고 완벽하다고 생각합니다.

    글을 남기는 이유는 의문점이 생겨서 인데요.

    재귀 함수를 사용하는데.

    while, for 문이 없음에도. 어떻게 무한 반복 하듯이 반복하는지 궁금합니다.

    이제 입문 하는 학생이 염치없게도 가르침 부탁합니다.

    항상 건강하세요^^

  2. Blog Icon
    6l4ck3y3

    재귀 함수란 것이 스스로를 호출하는 것을 말합니다. 위 소스에서 moveHanoi() 함수가 있는데, 이 함수 안에서 다시 moveHanoi() 함수를 호출하지요. 그리고 호출된 moveHanoi() 함수는 또 다른 moveHanoi() 함수를 호출합니다. 이렇게 계속 스스로를 호출하기 때문에 계속 반복을 할 수 있는 것입니다.

    함수는 호출되면서 데이터가 스택에 쌓이게 되고, 함수가 종료되면 스택에서 제거됩니다. 그런데 재귀 함수는 자기 자신이 종료되기도 전에 자기 자신을 부르기 때문에 스택에서 제거되지 않고 계속 쌓이게 되죠. 그리고 마지막에 (n==1) 과 같은 조건을 만나서 더 이상 호출을 할 필요가 없게 되면, 호출된 순서의 역순으로 차례대로 함수가 종료됩니다. 여기서 함수가 종료되면서 문자열을 출력하죠.

    재귀 함수는 처음 접하는 분께는 어려운 개념일 거예요. 제 대답이 도움이 되었으면 좋겠네요. 자세한 내용은 아래 문서를 봐주세요.

    http://www.winapi.co.kr/clec/cpp2/16-2-1.htm
    http://www.winapi.co.kr/clec/cpp2/16-2-2.htm