알고리즘 - 재귀 알고리즘(1)

재귀는 어떠한 작업을 할 때, 자기 자신을 포함 및 사용하는 경우를 말합니다.

 

재귀를 사용하는 대표적인 예인 팩토리얼 문제를 보겠습니다.

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

if __name__ == '__main__':
    n = int(input('출력할 팩토리얼 값을 입력: '))
    print(f'{n}의 팩토리얼은 {factorial(n)}입니다.')

 

만약 3의 팩토리얼 값을 구한다고 했을 때 factorial(3)을 호출하면

3 * factorial(2)을 반환하고 factorial(2)는 다시 factorial(1)을, factorial(0)일 때는 1을 반환하게 됩니다.

그럼 factorial(1) -> 1 * 1(factorial0)이고 factorial(2) -> 2 * 1, factorial(3) -> 3 * 2

이렇게 해서 6이라는 결과가 나옵니다.

 

 

다음으로는 최대 공약수를 재귀적으로 구하는 방법입니다.

def gcd(x: int, y: int) -> int:
    if y > x:
        x, y = y, x
    if y == 0:
        return x
    else:
        return gcd(y, x % y)


if __name__ == '__main__':
    x = int(input('첫 번째 정수값을 입력하세요.: '))
    y = int(input('두 번째 정수값을 입력하세요.: '))

    print(f'두 정숫값의 최대 공약수는 {gcd(x, y)}입니다.')

 

함수 gcd를 보면 y가 x보다 클때 서로 스왑해주는데

그건 큰 값을 작은 값으로 나눈 나머지를 사용하기 때문입니다.

 

x가 18이고 y가 12일 때, gcd 함수를 그대로 적용하면 gcd(18, 12) -> gcd(12, 6) -> gcd(6, 0)

이렇게 되고 x 자리에 있는 6이 최대 공약수가 됩니다.