[알고리즘] 재귀 알고리즘

[재귀]

• 나 자신을 다시 호출하는걸 재귀라고 한다.

바로 실습으로 가보자.

---

[실습 1] 유클리드 호제법

# 유클리드 호제
def gcd(a,b):
    c = a % b
    if c == 0 :
        return b
    return gcd(b,c)               # return을 빠트려서는 안된다.

a, b = map(int,input('최대 공약수를 구하고픈 두 수 ? : ').split())
print(f'{a}, {b}의 최대공약수는 {gcd(a,b)}')

return gcd(b,c)에서 return을 빼먹을 경우, b의 값과 관련 없이 함수 gcd(a,b)는 None을 return하게 된다.

왜냐면 자기 자신을 불러오기 전 함수 gcd(a,b)는 무엇을 return할껀지가 안정해지기 때문.

 

 

백준 문제 풀이를 통해 재귀 알고리즘의 대표적 예시인 하노이의 탑을 다뤄보도록 하려고 한다.

=> url : https://callmescone.tistory.com/92

[백준 9단계] 11729 하노이의 탑 이동 순서