하노이의 탑

재귀 호출 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단계는 출발지와 목적지 위치만 다를 뿐 완전히 동일하다.

참조 영상 :