재귀 호출 BASH 버전 :


#!/bin/bash

hanoi(){
if [ $1 -eq 1 ]; then
echo "move $1 from $2 to $3"
return
fi
hanoi $(( $1 - 1 )) $2 $4 $3
echo "move $1 from $2 to $3"
hanoi $(( $1 - 1 )) $4 $3 $2
}


hanoi 4 A B C 호출 결과 :


move 1 from A to C
move 2 from A to B
move 1 from C to B
move 3 from A to C
move 1 from B to A
move 2 from B to C
move 1 from A to C
move 4 from A to B
move 1 from C to B
move 2 from C to A
move 1 from B to A
move 3 from C to B
move 1 from A to C
move 2 from A to B
move 1 from C to B


Comment :

4개의 원판을 A에서 B로 옮기기 위해서는


1단계 - 3개의 원판을 A에서 C로 옮겨놓고

2단계 - 가장 아래에 있던 4번째 원판을 A에서 B로 옮긴 후

3단계 - 다시 C에 있던 3개의 원판을 B로 옮기면 된다.


1단계와 3단계는 출발지와 목적지 위치만 다를 뿐 완전히 동일하다.


참조 영상 :


  1. 구경꾼
    2019.11.24 02:54

    하이노이의탑은 재귀하면 빠지지 않고 등장하는데,
    기초책에서 하노이탑예제는 오히려 독이 되는듯 합니다..

    이렇게 대단한걸 할수 있다고 책의 저자가 자랑? 하는건데... 초보 독자 입장에서는 응용을 전혀 못하죠..

    하노이의 탑은 이해 했다가도 잊어먹는, 반복을 여러번 했었습니다...

    재귀는 수학의 수열개념으로 이해하는게 제일 쉽다고 생각합니다..먼저 이런것부터 ...

    S=1+2+......n

    f(1)=1
    f(n)=f(n-1)+n