재귀 알고리즘의 기본..

 

오늘으 재귀를 알아보자.. 오늘은 진지하게... 도와줘요 스피드웨건..!

 

가보자고.. !

 

 

재귀 알아보기

어떠한 이벤트를 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의되는 경우를 재귀(recursion)이라고 한다

어려운말인데 쉽게 말해서 자기 자신을 계속 호출한다고 보면 된다 

 

가장 대표적인 예가 피보나치의 수열 또다른건 화면 가운데에 계속해서 자기 화면서 반복해서 나타나는거라고 보면 된다 . 

이렇게 자원이 된다면 무한하게 이어지는 자연수(1, 2, 3, 4,5, ---- etc) 처럼 이것을 다음과 같이 정의할 수 있다.. 

 

자연수의 정의 
1. 1은 자연수이다 
2. 어떤 자연수의 바로 다음 수도 자연수 이다.

 

무안히 존재하는 자연수를 재귀적 정의(recusive definition)를 사용하여 위의 두 문장으로 정의했다.

 

 

재귀를 남발하면 메모리 사용률이 기하급수적으로 늘어나
오히려 프로그램이 터지는 현상이 나지만 

재귀를 잘 쓰면 프로그렘을 간결하고 효율성 있게 작성할 수 있다는 장점도 있다. 

 

팩토리얼 

재귀를 사용하는 대표적인 예로 양의 정수 곱을 구하는 팩토리얼이 있다  (양의 정수를 순서대로 곱한다고 해서 순차 곱셈이라고 함)

팩토리얼 n! 정의 (n은 양의 정수)
1. 0! = 1
2. n > 0 이면 n! = n * (n-1)!

 

간단하게 작성해봣다

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)}입니다")

이 factorial 함수는 매개변수 n에 전달받은 값이 0보다 크면 자기 자신을 곱하고 그렇지 않으면 1을 반환

 

저 코드를 보면 factorial이 n-1의 factorial 값을 구하기 위해 계속 호출하는걸 볼 수 있는데 이 과정을 재귀호출이라고한다

** 정확하기 말하면 재귀 호출은 '함수 자신'이 아니라 '자기 자신'과 똑같은 함수를 호출한다고 이해하는것이 자연스럽다.

만약 함수 자신을 호출하면 끝없이 자신을 호출하는 행위를 계속하기 때문이다.

 

직접 재귀와 간접 재귀

작성한 factorial 함수는 내부에서 자신과 똑같은 factorial함수를 호출하는데 이와 같이 자신과 똑같은 함수를 호출하는 방식을 직접 재귀라고 한다 

 

a() -> b() -> a() 처럼 함수를 호출하는 과정을 간접 재귀라고 한다 

 

재귀 알고리즘은 풀어야 할 문제나 계산할 함수 또는 처리할 자료구조가 재귀적으로 정의되는 경우에 적용됨 

팩토리얼값을 구하는 문제는 재귀의 원리를 돕기 위해서 사용된거지 현실적으로는 적합하진 않음 

 

유클리드 호제법 알아보기 

2개의 정숫값을 직시각형 두 변의 길이라고 생각하면 두 정숫값의 최대 공약수를 구하는 문제는 다음과 같이 바꿀 수 있음 

직사각형 안을 정사각형 어려 개를 가득채워나간다
이렇게 만들 수  있는 정사각형 가운데 가장 작은 정사각형의 변의 길이를 구하세요 

 

이렇게 풀 수 있다 

1. 22 x 8 크기의 직사가격형에서 짧은 변의 길이 8을 한 변으로 하는 정사각형을 나눔 

   그러면 8x8 형태 정사각형 2개 8x6 형태 직사각형 1개가 만들어짐 

2. 이 8x6 형태 직사각형에서 6x6 형태의 정사각형을 하나 만들고 6x2 형태의 직사각형이 만들어짐 

3. 이 6x2 형태의 직사각형을 2x2 형태의 정사각형 3개가 만들어짐  

 

그러면 이렇게 얻은 정사각형 변의 길이 2가 22x8의 최대 공약수라고 할 수 있음 

정리하면 3의 과정처럼 두 정숫값이 주어질 때 큰 값을 작은 값으로 나누어 떨어지면 작은 값이 최대 공약수가 됨 

나머지에 대해 같은 과정을 나누어 떨어질떄까지 재귀적으로 반복하는것이 특징 

 

그럼 이걸 수학적으로 풀어보면 

두 정수 x와 y의 최대 공약수를 gcd(x, y)라고 표현하고 

ex) x = az y = bz 를 만족하는 정수 a, b와 최대의 정수z 가 존재할때  z=gcd(x, y)라고 할 수 있음 

 

이걸 정의하면 다음과 같이 쓸 수 있음 

1. y=0 이면 --- x 
2. y가 0이 아니라면 --- gcd(y x%y)

이걸 유클리드 호제법이라고 함 

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("첫번째 정수 : "))
    y = int(input("두번째 정수 : "))
    
    print(f"두 정숫값의 최대 공약수는 {gcd(x, y)}")