12. 재귀 알고리즘

---

 

 

1. 재귀 (Recursion)

재귀란, 어떤 이벤트에서 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의되는 경우를 말한다.

어떤 문제를 해결하는 과정에서 자신과 같지만, 크기가 다른 문제를 발견하고 이들 간의 관계를 파악하여 간명하게 문제를 해결하는 방식이다.

재귀를 사용하면 프로그램을 간결하고 효율적으로 작성할 수 있다.

병합 정렬, 퀵 정렬, 이진 검색 트리 알고리즘에 활용된다.

 

1.1) 자연수의 재귀적 정의 (Recursive Definition)

1은 자연수다.

1 다음의 자연수는 자연수다.

1 다음의 자연수의 다음의 자연수는 자연수다.

즉, 어떤 자연수의 바로 다음 수도 자연수다.

 

1.2) 재귀적 구조 (Recursive Structure)

어떤 문제 안에 크기만 다를 뿐, 성격이 다른 똑같은 문제가 포함된 구조.

수열의 점화식 또는 n의 팩토리얼이 이에 해당한다.

 

---

 

2. 팩토리얼 (Factorial)

팩토리얼은 순차 곱셈, 자승을 의미한다.

즉, 양의 정수를 순서대로 곱하는 것이 팩토리얼이다.

 

2.1) 팩토리얼 구현하기

factorial() 함수 내부에서 자신과 똑같은 factorial() 함수를 호출하는 재귀 구조로 구현한다.

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)}")

 

---

 

3. 재귀 호출 (Recursive Call)

3.1) 직접 재귀 호출 (Direct Recursive Call)

자신과 동일한 함수를 호출한다.

함수 자신을 호출한 것이 아닌, 새로운 함수 객체를 호출한다.

 

3.2) 간접 재귀 호출 (Indirect Recursive Call)

다른 함수를 통해 자신과 동일한 함수를 호출한다.

a( ) 함수가 b( ) 함수를 호출하고, 다시 b( ) 함수가 a( ) 함수를 호출한다.

 

---

 

4. 가장 작은 정사각형의 한 변의 길이를 구하라.

두 변의 길이가 주어졌을 때, 큰 변의 길이를 작은 변의 길이로 나누어 떨어질 때까지 재귀적으로 반복한다.

 

4.1) 변의 길이 x, y인 직사각형의 해 (x >= y)

변의 길이 x, y인 직사각형의 해를 gcd(x, y)라고 하면, gcd(22, 8) == gcd(8, 6) == gcd(6, 2) == gcd(2, 0) == 2

 

4.2) 유클리드 호제법 (Euclidean Algorithm)

 

4.3) 최대 공약수 (GCD: Greatest Common Divisor)

두 정수 x와 y에 대해서, x = az와 y = bz를 만족하는 정수 a, b와 최대 정수 z가 존재할 때, 두 정수의 최대 공약수를 z라고 한다.

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("1번째 정수값을 입력하세요: "))
    y = int(input("2번째 정수값을 입력하세요: "))
    
    print(f"두 정수값의 최대 공약수: {gcd(x, y)}")

 

---

 

5. 순수한 재귀 (Genuinely Recursion)

순수한 재귀란, 재귀 호출을 여러 번 실행하는 함수 호출이다.

실행 순서가 복잡하여 분석이 어렵다.

def recur(n: int) -> int :
    if (n > 0) :
        recur(n-1)
        print(n)
        recur(n-2)
        
x = int(input('정수값: ')
recur(x)

 

---

 

6. 재귀 알고리즘 분석

6.1) 하향식 분석

가장 상위 함수 호출에서 시작하여 계단식으로 자세히 조사해 나가는 분석 방법.

recur(4) 실행 과정은 다음과 같다.

• recur(3) 실행
• 4 출력
• recur(2) 실행

같은 함수를 여러 번 호출하는 중복 호출이 발생한다.

 

6.2) 상향식 분석

아래부터 위로 쌓아 올리며 분석하는 방법

recur(1) 실행 과정은 다음과 같다.

• recur(0) 실행
• 1 출력
• recur(-1) 실행

 

---

 

7. 재귀 알고리즘의 비재귀적 구현

• 꼬리 재귀: 함수의 맨 끝에서의 재귀 호출를 말한다.
• 꼬리 재귀 제거하기: recur(n-2) 호출의 의미는 n-2를 인수로 전달하고 recur( ) 함수를 호출하는 것이다. (n 값을 n-2로 업데이트하고 함수 시작 지점으로 복귀)

## 순수한 재귀 함수

def recur(n: int) -> int :
    if (n > 0) :
        recur(n-1)
        print(n)
        recur(n-2)
        
x = int(input("정수값: "))
recur(x)

## 비재귀적으로 재귀 함수 구현 (꼬리 재귀 제거)

def recur(n: int) -> int :
    while (n > 0) :
        recur(n-1)
        print(n)
        n = n - 2

## 스택을 사용한 재귀 함수 구현 (꼬리 재귀 제거)

from stack import Stack

def recur(n: int) -> int :
    s = Stack(n)
    
    while (True) :
        if (n > 0) :
            s.push(n)
            n = n-1
            continue
        if not (s.is_empty()) :
            n = s.pop()
            print(n)
            n = n-2
            continue
        break
        
x = int(input("정수값: "))
recur(x)

 

---

 

---

수고하셨습니다!

---