1. 재귀 알고리즘

재귀 알고리즘
나 자신을 다시 호출하는 것을 재귀하고 한다.

def recusion(num)
	if num >0:
    	print('*'*num)
        return recusion(num -1) #자신을 다시 호출
    else:
    	return 1

---

실습

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

• 유클리드 호제법
  • 두 자연수 n1, n2에 대하여 (n1>n2) n1를 n2로 나눈 나머지를 r이라고 할 때, n1과 n2의 최대공약수는 n2와 r의 최대공약수와 같다.

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

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

---

2. 하노이의 탑

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

• 한 번에 한개의 원판만 옮길 수 있다.
• 큰 원판이 작은 원판 위에 있어서는 안 된다.

---

실습

파이썬을 이용해서 하노이의 탑 게임 진행 과정을 출력하자.

def moveDisc(discCnt, fromBar, toBar, viaBar): # 원판개수, 시작, 도착, 경유
    if discCnt == 1: # 맨 밑만 남았을 경우
        print(f'{discCnt}disc를 {fromBar}에서 {toBar}(으)로 이동')

    else :
    	# (discCnt-1)개들을 경유 기둥으로 이동
        moveDisc(discCnt-1, fromBar, viaBar, toBar)

		# discCnt개를 목적 기둥으로 이동
        print(f'{discCnt}disc를 {fromBar}에서 {toBar}(으)로 이동')

		# (discCnt-1)개들을 목적 기둥으로 이동
        moveDisc(discCnt-1, viaBar, toBar, fromBar)

moveDisc(3, 1, 3, 2)

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

굉장히 어렵다...