하노이타워

def hanoi(n, _from, _by, _to):
	#base case
	if n==1:
        print(f'{n}번째 쟁반을 {_from}에서 {_to}로 이동 ')
        return
    
    hanoi(n-1, _from, _to, _by)
    print(f'{n}번째 쟁반을 {_from}에서 {_to}로 이동 ')
    hanoi(n-1, _by, _from ,_to)

hanoi(3,a,b,c)를 입력했다고 치자 이 함수는 기저조건 n==1을 못맞춰서 프린트하지 않고 아래로 내려갈것이고

hanoi(2,a,c,b)

print(2번째를 a -> c)

hanoi(2,  b,a,c)를 만들것이다

만들어는 두는데, 재귀 호출에 의해 hanoi(2,a,c,b)를 실행할 것이고 

이는 이프문을 지나

hanoi(1,a,b,c)

print(2번째를 a->b)

hanoi(1,c,a,b)를 만들고 다시 hanoi(1,a,b,c)를 실행,

드디어 이프문 조건에 해당되

print(1번째를 a에서 c로 이동)을 만족시키고 리턴,

그럼 hanoi(1,a,b,c)를 만족시키고

print(2번째를 a에서 b로 이동을 출력,

hanoi(1,c,a,b)를 실행,

print(1번째를 c에서 b로 이동)을 실행시킨다.

그후 첫번째 hanoi(2,a,c,b)를 끝내고

print(3번째를 a에서 c로이동)을 출력하고

hanoi(2,b,a,c)를 실행한다

이때

hanoi(1,b,c,a)

print(2번째를 b에서 c로이동)

hanoi(1,a,b,c)를 작성해두고

 

hanoi(1,b,c,a)로 들어간다.

if문에 걸려서

print(1번째를 b에서 a로 이동)을출력,

그다음 print(2번쨰를 b에서 c로이동)을 출력,

hanoi(1,a,b,c)로 들어간다

그다음 print(1번째를 a에서 c로이동을 완료하면 전체)

hanoi(3,a,b,c)를 끝낸다

 

총7번의 출력코드가 생성된다

 

생긴걸로는

print(3번째 a->c) ⓕ

print(2번째 a->b) ⓑ

print(1번쨰 a->c) ⓐ

print(1번째 c->b) ⓒ

print(2번째 b->c) ⓔ

print(1번쨰 b->a) ⓔ

print(1번쨰 a->c) ⓖ

이지만 순서는 옆에 알파벳순으로 출력된다

 

이는 n=3일때 코드이다