[파이썬 기초] 알고리즘 - 재귀, 하노이의 탑

🔍  재귀 알고리즘이란?

- 나 자신을 다시 호출하는 알고리즘

 

1) 재귀 알고리즘

def recusion(num):

    if num > 0:
        print("*" * num)
        return recusion(num-1)

    else:
        return 0

recusion(10)


-----------------------------
**********
*********
********
*******
******
*****
****
***
**
*

 

2) 팩토리얼

def factorial(num):
    if num > 0:
        return num * factorial(num-1)
    else:
        return 1

print(f'factorial(4) : {factorial(4)}')


-----------------------------------------
factorial(4) : 24

 

3) 최대 공약수 구하기

def gcd_for(n1, n2):

    maxNum = 0
    for i in range(1, n1+1): #n1까지
        if n1 % i == 0 and n2 % i == 0:
            maxNum = i
    return maxNum

print(f'for문 이용 : {gcd_for(96,40)}')


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

print(f'재귀 이용 : {gcd_recusion(96,40)}')


-----------------------------------------
for문 이용 : 8
재귀 이용 : 8

---

 

🗝 하노이의 탑

- 3개의 기둥에 적당한 개수의 원반을 쌓아 놓고 다른 쪽으로 옮기는 게임.

하노이의 탑 이동 과정

def moveDisc(discCnt, fromBar, toBar, viaBar):
    if discCnt == 1:
        print(f'{discCnt}disc를 {fromBar}에서 {toBar}(으)로 이동!')
    else:
        moveDisc(discCnt-1, fromBar, viaBar, toBar)

        print(f'{discCnt}disc를 {fromBar}에서 {toBar}(으)로 이동!')

        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(으)로 이동!