HW07

문제) 하노이탑 풀이 과정을 진행하며 원판이 옮겨지는 매순간, '사진', '코드 실행 라인 표시', '메모리 스택 그림'을 매칭하여 서술하세요.

풀이)

①
사진)

코드 실행 라인 표시)

메모리 스택 그림)

현재 n은 4이므로 else문에 들어가서 다시 함수안으로 들어간다.
함수 안으로 들어간 n은 3이 되고 tmp = B, to = C 가 된다.
다시 함수 안으로 들어간 뒤 n은 2가 되고 tmp = C, to = B가 된다.
마지막으로 함수에 들어간 n은 1이 되고 tmp = B, to = C인 상태이다.
이는 base case이므로 from에서 to로 옮긴다.
즉 A에서 제일 위에 있는 원판 1을 to인 C로 옮긴다.

②

n이 1로 들어갔던 함수가 끝났으므로 다음줄의 코드를 실행한다.
이때, n =2, tmp = C, to = B인 상태이므로
원판 2가 A에서 B로 옮겨진다.

③
이제 그 다음 줄의 함수로 들어가게되면 n =1, from = C, tmp = A, to = B가 된다. n이 1이므로 if문 내의 출력문을 출력한다.
즉, 원판 1을 C에서 B로 옮긴다.

④
함수에서 벗어나게 되었으므로 else문의 두번째 코드를 출력한다.
이때 파라미터들은 n = 3, from = A, tmp = B, to = C이다.
즉, 원판3을 A에서 C로 옮긴다.

⑤
다음 줄의 코드를 출력한다. 이때 n은 3이므로 else문으로 들어간다. 이때의 파라미터 값들은 (2,B,A,C)이다.
다시 함수의 else문 안으로 들어가게 되고 이때의 파라미터값들은 (1,B,C,A)가 된다.
n==1이므로 if문 내의 코드를 출력한다.
즉, 원판 1을 B에서 A로 옮긴다.

⑥
이제 함수를 빠져나왔으므로 다음줄을 출력한다. 이때의 파라미터 값들은 (2,B,A,C)이므로 원판 2를 B에서 C로 옮긴다.

⑦

else문의 마지막줄을 출력한다. 이때 n은 2이므로 파라미터 값들은 (1,A,B,C)가 되고 n==1이므로 if문 내의 코드를 출력한다.
즉, 원판 1을 A에서 C로 옮긴다.

⑧
함수에서 빠져나왔으므로 그 다음줄을 출력한다.
이때의 파라미터 값들은 (4,A,C,B)가 되므로 원판 4를 A에서 B로 옮긴다.

⑨
다음줄의 함수를 출력한다. n=4이므로 n=3이 되어 else문 안으로 들어가게 되고 다시 n =2가 되어서 else 문 안으로 들어가게 된다. 그리고 n=1이 되었을 때의 파라미터 값들은 (1,C,A,B) 이므로 원판 1을 C에서 B로 옮긴다.

⑩
함수를 빠져나왔으므로 else문의 두번째 문장을 출력한다. 이때의 파라미터값은 (2,C,B,A)이므로 원판2를 C에서 A로 옮긴다.

⑪
다음줄의 함수로 들어간다. 이때 n=2이므로 함수안에 들어가게되는 파라미터 값들은 (1,B,C,A)가 된다. 즉, 원판 1을 B에서 A로 옮긴다.

⑫
함수를 빠져나왔으므로 else문의 두번째줄을 출력한다. 이때의 파라미터 값들은 (3, C, A, B)이므로 원판 3을 C에서 B로 옮긴다.

⑬
이제 n = 2이므로 함수안에 들어갔을 때 파라미터 값들은 (1,A,B,C)가 된다. if문을 충족하므로 원판 1을 A에서 C로 옮긴다.

⑭
이제 함수에서 빠져나왔으므로 else문의 두번째줄을 출력한다. 이때의 파라미터 값들은 (2,A,C,B)이므로 원판2를 A에서 B로 옮긴다.

⑮
이제 마지막으로 else문의 마지막 함수로 들어가는데 들어가기 전 파라미터 값은 (2, A, C,B)이므로 들어가게 된다면 (1,C,A,B)로 바뀐다. if문의 조건을 충족하므로 원판1을 C에서 B로 옮긴다.

완성!