재귀 알고리즘, 하노이의 탑

1. 재귀 알고리즘

나 자신을 다시 호출하는 것을 재귀라고 한다. 반복문을 사용할 수 있지만 재귀함수를 사용하는 방법이 더 간결하다.

*를 사용해 tree를 만드는 코드를 재귀 함수를 통해 만들면 아래와 같다.

def recusion(num):
    
    if num>0:
        print('*'*num)
        return recusion(num-1)
    else:
        return 1
    
recusion(10)

 

2. 재귀 알고리즘을 이용한 최대 공약수 계산

유클리드 호제법을 사용해 계산할 수 있다.

 유클리드 호제법

두 자연수 n1, n2에 대하여 (n1 > n2) n1를 n2로 나눈 나머지를 r이라고 할 때,
n1과 n2의 최대공약수는 n2와 r의 최대공약수와 같다

42와 24의 최대공약수의 경우 n1=42를 n2=24로 나눈 나머지 r=18이라고 할 때,
42와 24의 최대공약수는 24와 18의 최대공약수와 같다

#최대공약수(greatest common devide)

def gcd(n1, n2):
    if n1 % n2 == 0:
        return n2
    else:
        r = n1 % n2
        return gcd(n2, r)

print(f'gcd(82, 32): {gcd(82,32)}')
print(f'gcd(96, 40): {gcd(96,40)}')

3. 하노이의 탑

퍼즐게임의 일종으로 3개의 기둥을 이용해 원판을 다른 기둥으로 옮기면 되고, 제약 조건은 다음과 같다

- 한 번에 한 개의 원판만 옮길 수 있다.

- 큰 원판이 작은 원판 위에 있어서는 안 된다.

#원판 개수, 출발 기둥, 도착 기둥, 경유 기둥
def moveDisc(discCnt, fromBar, toBar, viaBar):
    if discCnt == 1:
        print(f'1:{discCnt}disc를 {fromBar}에서 {toBar}(으)로 이동')
    else:
        #(discNo - 1)개들을 경유 기둥으로 이동
        moveDisc(discCnt-1, fromBar, viaBar, toBar)
        
        #discNo를 목적 기둥으로 이동
        print(f'2:{discCnt}disc를 {fromBar}에서 {toBar}(으)로 이동')
        
        #(discNo-1)개들을 도착기둥으로 이동
        moveDisc(discCnt-1, viaBar, toBar, fromBar)
        
moveDisc(3, 1, 3, 2)

결과 출력

1:1disc를 1에서 3(으)로 이동
2:2disc를 1에서 2(으)로 이동
1:1disc를 3에서 2(으)로 이동
2:3disc를 1에서 3(으)로 이동
1:1disc를 2에서 1(으)로 이동
2:2disc를 2에서 3(으)로 이동
1:1disc를 1에서 3(으)로 이동