카테고리 없음

재귀 알고리즘 - 개념과 분석

sungw00 2024. 8. 19. 22:53
728x90

재귀 알아보기

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

이러한 재귀의 개념을 사용하여 1, 2, 3, ... 과 같이 무한하게 이어지는 자연수를 다음과 같이 정의할 수 있다.

 

자연수의 정의

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

 

팩토리얼 알아보기

재귀를 사용하는 대표적인 예로 양의 정수 곱을 구하는 팩토리얼 문제가 있다.

팩토리얼은 양의 정수를 순서대로 곱한다는 의미로 순차 곱셈이라고도 한다. 양의 정수 n의 팩토리얼(n!)은 다음과 같이 재귀적 정의를 할 수 있다.

팩토리얼 n!의 정의(n은 양의 정수)

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

 

예를 들어 10!(10의 팩토리얼)은 10 × 9!로 구할 수 있고, 다시 9!은 9 × 8!로 구할 수 있다.

이러한 정의를 그대로 아래 프로그램에서 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)}입니다.')

 

실행 결과

출력할 팩토리얼값을 입력하세요.: 3
3의 팩토리얼은 6입니다.

Process finished with exit code 0

 

factorial( ) 함수는 매개변수 n에 전달받은 값이 0보다 크면 n * factorial(n - 1)의 값을 반환하고, 그렇지 않으면 1을 반환한다.

 

math.factorial( ) 함수란

파이썬에서는 팩토리얼 값을 구하는 표준 라이브러리로 math 모듈에서 factorial( ) 함수를 제공한다. 

예를 들어 math.factorial(x)는 정수 x의 팩토리얼값을 반환한다.

x가 정수가 아니거나 음수라면 ValueError 예외 처리를 내보낸다.

 

factorial() 함수 실행 순서

 

 

직접 재귀와 간접 재귀

factorial( ) 함수는 내부에서 자신과 똑같은 factorial( ) 함수를 호출한다. 이와 같이 자신과 똑같은 함수를 호출하는 방식을 직접 재귀라고 한다. 이와 다르게 간접 재귀는 a( ) 함수가 b( ) 함수를 호출하고 다시 b( ) 함수가 a( ) 함수를 호출하는 구조이다. 이 2가지 재귀 방식을 그림으로 나타내면 아래와 같다.

 

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

이러한 점에서 재귀 과정으로 팩토리얼값을 구하는 문제는 재귀의 원리를 이해하기 위한 예제일 뿐 현실적으로는 적합하지 않다.

 

유클리드 호제법(GCD; Greatest Common Divisor)

두 정숫값의 최대 공약수(GCD)를 재귀적으로 구하는 방법을 생각해보면, 2개의 정숫값을 직사각형 두 변의 길이라고 생각했을 때 두 정숫값의 최대 공약수를 구하는 문제는 다음과 같이 바꿀 수 있다.

Q. 직사각형 안을 정사각형 여러 개로 가득 채워 나갑니다.
이렇게 만들 수 있는 정사각형 가운데 가장 작은 정사각형의 변의 길이를 구하세요.

 

  1. a처럼 22 × 8 크기의 직사각형에서 짧은 변의 길이인 8을 한 변으로 하는 정사각형으로 나눈다. 그러면 b처럼 8 × 8 크기의 정사각형 2개가 만들어지고 8 × 6 크기의 직사각형이 남는다.
  2. 남은 8 × 6 크기의 직사각형에서도 다시 같은 과정을 수행한 결과가 c이다. 6 × 6 크기의 정사각형 1개가 만들어지고 6 × 2 크기의 직사각형이 남는다.
  3. 남은 6 × 2 크기의 직사각형에서도 다시 같은 과정을 수행한 결과가 d이다. 이번에는 2 × 2 크기의 정사각형 3개가 만들어진다. 이렇게 얻은 정사각형의 변의 길이인 2가 8과 22의 최대 공약수이다.

정리하면 3번 과정처럼 두 정숫값이 주어질 때 큰 값을 작은 값으로 나누어 떨어지면 작은 값이 최대 공약수가 된다. 나누어 떨어지지 않으면 작은 값과 나머지에 대해 같은 과정을 나누어 떨어질 때까지 재귀적으로 반복한다.(1, 2)

 

위 과정을 수학에서는 아래와 같이 표현한다.

두 정수 x와 y의 최대 공약수를 gcd(x, y)로 표기할 때 x = az와 y = bz를 만족하는 정수 a, b와 최대의 정수 z가 존재할 때 z는 gcd(x, y)라고 할 수 있다. 다시 말해 최대 공약수는 다음과 같이 구할 수 있다.

  • y가 0이면 ... x
  • y가 0이 아니면 ... gcd(y, x % y)

이 알고리즘을 유클리드 호제법이라고 하며, 아래 프로그램은 유클리드 호제법으로 두 정숫값의 최대 공약수를 구한다.

# 유클리드 호제법으로 최대 공약수 구하기

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

 

실행 결과

두 정숫값의 최대 공약수를 구합니다.
첫 번째 정숫값을 입력하세요.: 22
두 번째 정숫값을 입력하세요.: 8
두 정숫값의 최대 공약수는 2입니다.

Process finished with exit code 0

 

math.gcd( ) 함수
파이썬에서는 최대 공약수를 구하는 표준 라이브러리로 math 모듈에서 gcd( ) 함수를 제공한다.
예를 들어 math.gcd(a, b)는 정수 a와 b의 최대 공약수를 반환한다. a, b가 0이 아닌 경우 gcd(a, b)의 값은 a와 b 모두를 나누어 떨어지게 하는 가장 큰 정수를 반환한다. 
위 프로그램과 같이 두 인수가 모두 0인 경우 gcd(0, 0)은 0을 반환한다.

 

재귀 알고리즘의 2가지 분석 방법

# 순수한 재귀 함수 구현하기

def recur(n: int) -> int:
    """순수한 재귀 함수 recur의 구현"""
    if n > 0:
        recur(n - 1)
        print(n)
        recur(n - 2)

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

recur(x)

 

실행 결과

정숫값을 입력하세요.: 4
1
2
3
1
4
1
2

Process finished with exit code 0

 

recur( ) 함수는 앞에서 다룬 factorial( ) 함수나 gcd( ) 함수와 달리 함수 안에서 재귀 호출을 2번 실행한다.

이처럼 재귀 호출을 여러 번 실행하는 함수를 순수한 재귀라고 하는데 실제 동작은 복잡하다.

실행 결과처럼 매개변수 n에 4를 전달하면 recur( ) 함수는 1, 2, 3, 1, 4, 1, 2를 한 줄에 하나씩 출력한다.

만약에 n이 3이나 5라면 어떤 결과를 출력할지는 간단히 알 수 없다. 재귀 호출하는 recur( ) 함수를 하향식과 상향식 방법으로 분석해보자.

 

하향식 분석

매개변수 n에 4를 전달하면 recur( ) 함수는 다음과 같은 순서로 실행한다.

recur(4)의 실행 과정

recur(3)을 실행한다.

4를 출력한다.

recur(2)를 실행한다.

 

위의 과정 2에서 4가 출력되려면 recur(3)의 실행을 완료한 뒤이므로 먼저 과정 1에서 recur(3)이 무엇을 하는지 알아보자.

각각의 상자는 recur( ) 함수의 동작을 나타낸다. 전달받은 값이 0 이하이면 recur( ) 함수는 아무 일도 하지 않으므로 비어 있다는 의미로 상자 안에 -를 표시한다.

 

위 그림에서 가장 위쪽에 있는 상자는 recur(4)의 실행을 나타낸다. recur(3)을 실행하면 무엇을 하는지는 왼쪽 아래 화살표를 따라가야 알 수 있고, recur(2)를 실행하면 무엇을 하는지는 오른쪽 아래 화살표를 따라가야 알 수 있다.

 

이 내용을 정리하면 '왼쪽 화살표를 따라 1칸 아래쪽 상자로 이동하고, 다시 원래 호출한 상자로 되돌아오면 상자 안의 값을 출력한다. 이어서 오른쪽 화살표를 따라 1칸 아래쪽 상자로 이동한다'를 하나의 단계로 생각해야 한다. 이 단계를 1번 끝내야 비로소 1칸 위쪽 상자로 올라갈 수 있다. 물론 빈 상자인 경우에는 아무것도 하지 않고 원래 상자로 되돌아간다.

 

recur(3) 함수의 호출을 더 자세히 알아보기

가장 위쪽 상자인 recur(3)을 호출하면 가장 왼쪽 아래 상자인 recur(0)까지 계속 왼쪽 화살표를 따라가야 한다. 

그러므로 바로 4를 출력할 수가 없다. recur(0)에서 왼쪽 화살표를 따라 빈 상자(-)를 만나면 recur(0)을 호출한 원래 상자로 돌아가 1을 출력한다. 이어서 recur(-1)을 호출하고 오른쪽 화살표를 따라 내려가서 빈 상자를 만나면 돌아온다.

이렇게 한 단계를 완료하면 1칸 위 상자인 recur(1)로 올라간다. recur(1)은 이전 단계에서 실행했으므로 2를 출력하고, recur(0을 따라 오른쪽 아래 상자로 내려가지만 빈 상자를 만나면 돌아온다.

이처럼 recur( ) 함수를 호출하는 과정을 하향식 분석으로 차근차근 생각해보면 recur(3)을 호출한 상자로 돌아가려면 많은 단계를 거쳐야 한다는 것을 알 수 있다.

 

가장 위쪽에 위치한 상자의 함수 호출부터 시작하여 계단식으로 자세히 조사해 나가는 분석 방법을 하향식 분석이라고 한다. 그런데 위 그림에서는 recur(1)과 recur(2)를 여러 번 호출하고 있다. 꼭대기부터 분석하면 이렇게 같은 함수를 여러 번 호출할 수 있으므로 하향식 방식이 반드시 효율적이라고 말할 수는 없다.

 

상향식 분석

하향식 분석과는 반대로 아래쪽부터 쌓아 올리면 분석하는 방법을 상향식 분석이라고 한다. recur( ) 함수는 n이 양수일 때만 실행하므로 먼저 recur(1)이 어떻게 처리되는지 알아야 한다. recur(1)은 다음과 같은 순서로 실행한다.

 

recur(1)의 실행 과정

  1. recur(0)을 실행한다.
  2. 1을 출력한다.
  3. recur(-1)을 실행한다.

recur(1)을 실행하면 과정 1의 recur(0)과 과정 3의 recur(-1)은 출력할 내용이 없으므로 결국 과정 2의 1만 출력한다는 것을 알 수 있다. 다음으로 recur(2)를 실행하는 과정을 알아보자.

 

recur(2)의 실행 과정

  1. recur(1)을 실행한다.
  2. 2를 출력한다.
  3. recur(0)을 실행한다.

recur(2)를 실행하면 과정 1에서 recur(1)은 1을 출력하지만 과정 3의 recur(0)은 아무것도 출력하지 않는다. 결국 recur(1)과 recur(2)의 과정을 거쳐서 1과 2를 출력한다. 이 작업을 recur(4)까지 쌓아올린 내용이 이 내용이다.

이 과정을 통하여 recur(4)의 최종 출력을 얻을 수 있다.

 

recur( ) 함수의 재귀 호출을 거꾸로 출력하기

# 순수한 재귀 함수 구현하기

def recur(n: int) -> int:
    """순수한 재귀 함수 recur의 구현(거꾸로 출력)"""
    if n > 0:
        recur(n - 2)
        print(n)
        recur(n - 1)

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

recur(x)

 

실행 결과

정숫값을 입력하세요.: 4
2
1
4
1
3
2
1

Process finished with exit code 0

 

재귀 호출을 출력하려면 recur( ) 함수 내 파라미터로 전달하는 숫자를 변경해준다.

recur(4) 함수의 실행 결과는 위와 같으며, 이 프로그램을 상향식 분석하면 아래와 같이 나타낼 수 있다.

 

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

재귀 알고리즘으로 구현한 recur( ) 함수를 비재귀적으로 나타내는 방법을 알아보자.

 

꼬리 재귀를 제거하기

recur( ) 함수의 맨 끝에서 재귀 호출하는 꼬리 재귀 recur(n - 2) 함수의 의미는 '인수로 n - 2의 값을 전달하고 recur( ) 함수를 호출하는 것'이다. 따라서 이 호출은 다음 동작으로 바꿀 수 있다.

n의 값을 n - 2로 업데이트하고 함수의 시작 지점으로 돌아간다.

 

아래 코드는 이 동작을 반영하여 recur( ) 함수를 구현하였으며, n값을 2 감소시킨 뒤 함수의 시작 지점으로 돌아간다.

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

def recur(n: int) -> int:
    """꼬리 재귀를 제거한 recur() 함수"""
    if n > 0:
        recur(n - 1)
        print(n)
        n = n - 2

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

recur(x)

 

이렇게 하면 recur( ) 함수의 맨 끝에서 실행된 재귀 호출인 꼬리 재귀를 쉽게 제거할 수 있다.

정숫값을 입력하세요.: 4
1
2
3
4

Process finished with exit code 0

 

 

재귀를 제거하기

꼬리 재귀와 달리 맨 앞에서 재귀 호출하는 recur(n - 1) 함수는 제거하기가 쉽지 않다. 

왜냐하면 n값을 출력하기 전에 recur(n - 1)을 실행해야 하기 때문이다. 예를 들어 n값이 4인 경우 재귀 호출 recur(3)의 처리가 완료될 때까지 4를 어딘가에 저장해야 한다.

다시 말해 재귀 호출하는 recur(n - 1)을 제거하려면 다음과 같이 간단하게 바꿀 수는 없다.

n값을 n - 1로 업데이트하고 함수의 시작 지점으로 돌아간다.(X)

왜냐하면 현재의 n값을 임시로 저장할 필요가 있기 때문이다. 또한 recur(n - 1)의 처리를 완료하고 n값을 출력할 때 임시로 저장했던 n을 꺼내 그 값을 출력해야 한다.

이러한 문제는 아래 글에서 다뤘던 스택으로 해결할 수 있다.

https://vibeee.tistory.com/286

 

기본 자료구조 - 스택

스택 알아보기데이터를 임시 저장할 때 사용하는 자료구조로, 데이터의 입력과 출력 순서는 후입선출(LIFO) 방식 스택에 데이터를 넣는 작업을 푸시(push)스택에서 데이터를 꺼내는 작업을 팝(pop)

vibeee.tistory.com

 

아래 코드는 스택을 사용하여 비재귀적으로 구현한 recur( ) 함수이다.(위 포스팅 내 가장 마지막에 있는 Stack 클래스를 사용하므로 같은 경로 내에 있어야 한다.)

# 스택으로 재귀 함수 구현하기(재귀를 제거)

from stack import Stack     # stack.py의 Stack 클래스를 임포트

def recur(n: int) -> int:
    """재귀를 제거한 recur( ) 함수"""
    s = Stack(n)

    while True:
        if n > 0:
            s.push(n)   # n값을 푸시
            n = n - 1
            continue
        if not s.is_empty():    # 스택이 비어 있지 않으면
            n = s.pop()     # 저장한 값을 n에 팝
            print(n)
            n = n - 2
            continue
        break

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

recur(x)

 

실행 결과

정숫값을 입력하세요.: 4
1
2
3
1
4
1
2

Process finished with exit code 0

 

recur(4)가 호출될 때 n에 전달받은 4는 0보다 크므로 첫번째 if문에서 다음과 같은 처리 과정을 수행한다.

1. n값 4를 스택에 푸시한다.

2. n값을 1 감소시켜 3으로 만든다.

3. continue 문이 실행되어 while 문으로 돌아간다.

 

n값은 3이 되었고 이는 0보다 크므로 다시 첫번째 if문이 실행된다. 그 결과 1, 2, 3의 과정이 반복된다.

아래 그림의 b → c → d 순으로 진행되며 스택에는 4, 3, 2, 1이 쌓인다.

스택에 1을 쌓은 뒤에 n값은 0이 되고, while 문으로 돌아가지만 n값은 0이 되므로 다음의 첫번째 if문이 실행되지 않는다.

 

그리고 두번째 if문에서 다음 과정을 실행한다.

4. 스택에서 팝한 값 1을 n으로 꺼낸다.

5. n값 1을 출력한다.

6. n값을 2 감소시켜 -1로 한다.

7. continue 문의 동작으로 while 문의 맨 앞으로 돌아간다.

 

n값이 -1이므로 다시 두번째 if문이 실행되고, 아래 그림의 f처럼 스택에서 2가 팝되어 출력된다.

이후 과정은 아래의 그림과 같이 진행되며, n이 0 이하가 되어 스택이 비면 반복문 마지막의 break문이 실행되어 함수 실행을 종료한다.

 

728x90