[5.15] 05 -1 재귀 알고리즘의 기본

05-1 재귀 알고리즘의 기본

재귀 알아보기

recursion - 자기 자신을 모함하고 자기 자신을 사용하여 정의하는 경우

- recursive call

팩토리얼 알아보기

#양의 정수 n의 팩토리얼 구하기

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

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

math.factorial() 함수를 사용할 수도 있음. 

직접 재귀 direct 와 간접 재귀 indirect 

유클리드 호제법 알아보기

두 정수의 최대공약수 GCD를 재귀적으로 구하기

직사각형 안을 정사각형 여러 개로 채운다. 정사각형 가운데 가장 작은 정사각형의 변의 길이는?

#최대공약수 구하기

def gcd(a, b): #a > b라고 본다. 

    if a % b == 0:
        return b
    return gcd(b, a%b)

print(gcd(100, 5))

 예제 코드

#최대공약수 구하기

def gcd(x : int, y : int) -> int:
    if y == 0:
        return x
    else:
        return gcd(y, x % y)
    
if __name__ == '__main__':
    print('최대 공약수는? ')
    x = int(input('x의 값은 : '))
    y = int(input('y의 값은: '))
    print(f'두 정숫값의 최대 공약수는 {gcd(x, y)}입니다.')