재귀 알고리즘의 기본, 재귀 알고리즘 분석

Preface

 

이번 장에선 재귀 알고리즘에 대해 공부했다.

 

재귀 알고리즘을 사용하면 코드를 보다 짧게 작성할 수 있다고 하는데, 나는 아직 재귀 알고리즘이 어떻게 작동하는 것인지 정확히 이해하지 못했다.

 

책에 수록되어 있는 그림을 보며 코드를 이해하려 해봐도 출력값을 예상할 수 없었다.

 

다음 장을 공부하기 전 모든 코드를 다시 한 번 살펴보며 완벽히 이해한 후 넘어갈 계획이다.

---

 

1. 재귀 알고리즘의 기본

 

 

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

→ 프로그램을 간결하고 효율성 좋게 작성할 수 있음

 

 

- 팩토리얼 코드

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( ) 함수를 제공

 

 

- 직접 재귀 : 자신과 똑같은 함수를 호출하는 방식

 

 

- 간접 재귀 : a( ) 함수가 b( ) 함수를 호출하고 다시 b( ) 함수가 a( ) 함수를 호출하는 구조

→ 다른 함수를 통해 자신과 똑같은 함수를 호출

 

 

- 유클리드 호제법 코드

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

→ math 모듈에서 gcd( ) 함수를 제공

 

---

 

2. 재귀 알고리즘 분석

 

 

- 재귀 함수 코드

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


x = int(input('정숫값을 입력하세요.: '))

recur(x)

 

 

- 순수한 재귀 : 재귀 호출을 여러 번 실행하는 함수

 

 

- 분석 방법

1. 하향식 분석 : 가장 위쪽에 위치한 상자의 함수 호출부터 시작하여 계단식으로 자세히 조사해 나가는 분석 방법

2. 아래쪽부터 쌓아 올리며 분석하는 방법

 

 

- 비재귀적으로 재귀 함수 구현

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


x = int(input('정숫값을 입력하세요.: '))

recur(x)

 

 

- 스택으로 재귀 함수 구현

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)