chapter 5 - 1. 재귀 알고리즘

 

재귀 : 어떠한 이벤트에서 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의되는 경우

 

 

<팩토리얼>

양의 정수를 순서대로 곱한다 = 순차곱셈 = math.factorial()함수

factorial()함수는 n-1팩토리얼값을 구하기 위해 자신과 똑같은 factorial()함수를 또 호출

재귀 호출 : 자기 자신과 똑같은 함수를 호출

 

# 양의 정수 n의 팩토리얼 구하기
def factorial(n:int) -> int:
    """양의 정수 n의 팩토리얼값을 재귀적으로 구함""" 
    if n > 0:
        return n * factorial(n-1)
    else:
        return 1
 
if __name__ == '__main__':
    n = int(input('출력할  팩토리얼값을 입력하세요.: '))
    print(f'{n}의 팩토리얼은 {factorial(n)}입니다.')
 
 

직접 재귀 : 자기 자신과 똑같은 함수 호출

간접 재귀 : a()가 b()를 호출하고 다시 b()가 a()를 호출

 

<유클리드 호제법>

두 정숫값의 최대 공약수를 구하는 프로그램 = math.gcd()함수

-직사각형에서 짧은 변의 길이를 한 변으로하는 정사각형으로 가득 채움

-남은 직사각형에서도 같은 작업을 반복

-정사각형으로만 구성되었을 때 가장 작은 정사각형의 변의 길이가 최대공약수이다.

# 유클리드 호제법으로 최대 공약수 구하기
 
def gcd(x: int,y: int) ->int:
    """정숫값 x와 y의 최대 공약수를 반환"""
    if y == 0:
        return x
    else:
        return gcd(y, x % y)
 
 
if __name__ == '___main__':
    print('두 정숫값의 최대 공약수를 구합니다.')
    x = int(input('첫 번째 정숫값을 입력하세요: '))
    y = int(input('두 번재 정숫값을 입력하세요: '))
 
    print(f'두 정숫값의 최대 공약수는 {gcd(x,y)}입니다.')