데이터 스쿨 4주차 학습내용 정리 - 4

재귀함수

재귀함수란 자신을 다시 호출하여 작업을 수행하는 함수입니다. 재귀 호출이나 되부름이라고도 합니다.

재귀함수는 다음과 같은 특징을 가지고 있습니다.

자기 참조
재귀함수는 자신을 다시 호출하기 때문에 자기 참조를 합니다.

종료 조건
재귀함수는 종료 조건을 가지고 있어야 합니다. 종료 조건은 함수가 더 이상 자신을 호출하지 않고 종료되는 조건을 의미합니다.

재귀 호출
제귀함수는 종료 조건을 만족할 때까지 자신을 호출합니다.

재귀함수는 다양한 문제를 해결하는 데 사용할 수 있습니다. 다음은 재귀함수를 사용하여 해결할 수 있는 몇 가지 문제입니다.

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

재귀함수를 * 쌓기

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

재귀함수를 이용한 펙토리얼 구하기

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(82, 32) : {gcd(96, 40)}')

재귀함수를 이용한 최대공약수 구하기(유클리드 호재법)!!

😂하노이의 탑😂

히노이탑 알고리즘은 다음 그림과 같은 장난감을 파이썬으로 직접 구현하는 알고리즘이다.
갑자기 이걸 왜? 라는 느낌을 받을수있지만 이것을 다른 위치로 이동시키는것은 재귀함수를 응용한 함수임을 눈치챌수있다. (유튜브 보고오세요)

def hanoi(layer, go, to, other):
    if layer == 1:
        print(f'{layer}층 : {go}에서{to}로 이동')
    else:
        hanoi(layer-1, go, other, to)
        print(f'{layer}층 : {go}에서{to}로 이동')
        hanoi(layer-1, other, to, go)

hanoi(3, 1, 3, 2)

https://www.youtube.com/watch?v=aPYE0anPZqI
해당 유튜브 시청을 적극 권장드립니다.

아직 소화가 덜되서 설명드리기가 어려우니 나중에 삽입정렬과 함께 다른 정리글에서 뵙겠습니다.