[알고리즘] 재귀 알고리즘(Recursion) - 1: 팩토리얼, 유클리드 호제법, 재귀 분석, 비재귀적 표현

참고 문헌

https://www.easyspub.co.kr/20_Menu/BookView/381/PUB

https://www.easyspub.co.kr/20_Menu/BookView/381/PUB

 

재귀 알고리즘에 대하여

어떤 이벤트에서 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의하는 것

 

예시) 팩토리얼 n!의 정의

• 0! = 1
• n > 0이면 n! = n × (n - 1)!

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

위 팩토리얼 구현에서 보면, 함수 정의 자체에서 다시 자기 자신을 불러와 함수를 정의하는 것을 확인할 수 있다.

cf) 팩토리얼은 사실 재귀보다 다른 방식으로 구하는 것이 더 효율적이다.

 

재귀 호출

재귀 함수의 수행 과정 안에서 특정 함수가 다시 자기 자신과 똑같은 함수를 불러오는 것

위와 같은 순서로 함수를 호출하고 반환한다.

 

직접 재귀와 간접 재귀

• 직접 재귀: 자기 자신과 똑같은 함수를 호출하는 방식
• 간접 재귀: A함수가 B함수를 호출하고, 다시 B함수가 A함수를 호출하는 것

 

유클리드 호제법

두 정숫값의 최대 공약수(GCD)를 재귀적으로 구하는 방법

두 정수 A, B를 각각 22와 8이라고 하고, 유클리드 호제법의 예시를 볼 때,

• 22를 가로, 8을 세로로 하는 사각형을 설정한다.
• 사각형에서 짧은 변을 길이로 하는 정사각형을 이용하여 사각형을 채운다
• 사각형의 남은 부분에서(하늘색) 위 과정을 반복한다.
• 과정을 반복하다가 사각형이 완전히 채워지고, 정사각형이 생기면 해당 정사각형의 길이가 최대공약수가 된다.

이 과정에서는 2가 최대공약수가 된다.

유클리드 호제법의 구현

def gcd(x: int, y: int) -> int:
    if y == 0:
        return x
    else:
        return gcd(y, x % y)

 

재귀 알고리즘 분석

재귀 알고리즘에는 상향식 분석 방법과 하향식 분석 방법이 있다.

아래의 함수를 2가지 방법으로 분석해보려고 한다.

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

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

recur(4)의 결과는 1, 2, 3, 1, 4, 1, 2를 차례대로 출력한다.

 

1. 하향식 분석

recur(3)의 과정에서 3이 출력되려면 우선 recur(2)이 먼저 실행되어야 한다.

왼쪽 화살표를 따라 아래 칸으로 이동하고, 다시 원래 칸으로 돌아오면 그 때 되어서야 가운데의 값을 출력한다.

이어서 오른쪽 화살표를 따라 아래 칸으로 갈 수 있을 때까지 이동해야 하나의 단계가 끝나는데, 이러한 하나의 단계가 끝나야 위 칸으로 올라갈 수 있다.

 

이처럼 가장 상위의 함수 호출부터 시작하여 내려가며 자세히 조사해 나가는 분석을 하향식 분석이라고 한다.

 

2. 상향식 분석

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

 

recur() 함수는 먼저 n > 0 일 때만 실행하므로 recur(1)이 어떻게 처리되는지 알아야 한다.

recur(0)과 recur(-1)은 실행되지 않으므로, 1만 출력한다.

recur(1)의 결과: 1

 

이후 recur(2)에서는 recur(1)을 실행한 후, 2를 출력하고 recur(0)을 수행한다.

1을 출력하고, 2를 출력한 후 recur(0)은 실행되지 않으므로, 결과는 다음과 같다.

recur(2)의 결과: 1 2

 

recur(3)에서는 recur(2)를 실행한 후, 3을 출력하고 recur(1)을 수행한다.

 1 2를 출력하고, 3을 출력한후 1을 출력하므로 결과는 다음과 같다.

recur(3)의 결과: 1 2 3 1

 

recur(4)에서는 recur(3)을 실행한 후, recur(2)를 수행한다.

1 2 3 1을 출력한 후 4를 출력하고, 1 2를 출력하므로 결과는 다음과 같다.

recur(4)의 결과: 1 2 3 1 4 1 2

 

재귀 알고리즘의 비재귀적 표현

recur 함수를 비재귀적으로 나타내는 방법: 꼬리 재귀(recur(n - 2))를 제거하기

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

 

그러나 여기서 recur(n - 1)은 제거하기 쉽지 않다.

왜냐하면 출력 전에 recur(n - 1)을 실행해야 하기 때문이다.

recur(4)과정에서 recur(3)이 먼저 실행 된 후 4가 출력되어야 하는데 그러려면 4는 어딘가에 저장을 해두어야 한다.

따라서 위 처럼 쉽게 제거하기는 힘들고, 스택을 사용하여 해결해야 한다.

from collections import deque

def recur(n: int) -> int:
    s = deque()

    while(True):
        if n > 0:
            s.append(n)
            n = n - 1
            continue
        if s:
            n = s.pop()
            print(n)
            n = n - 2
            continue
        break