[알고리즘] 재귀 알고리즘 분석

순수한 재귀란?

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

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

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

실행 결과 정숫값을 입력하세요.: 4 1 2 3 1 4 1 2

- 순수한 재귀는 위와 같이 실행 과정이 복잡. 매개변수를 4가 아닌 3이나 5라면 어떤 결과를 출력할 지 간단히는 알 수 없음.

 

하향식 분석과 상향식 분석

위 코드를 하향식 분석(Top-down)방법과 상향식 분석(Bottom-up)방법으로 분석해보자.

recur( ) 함수의 하향식 분석 순서도

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

1. recur(3)을 실행한다.

2. 4를 출력한다.

3. recur(2)를 실행한다.

위 사진에서 보면 4를 기준으로 왼쪽에 3, 오른쪽에 2가 있는데 순서대로 보자면 왼쪽 먼저 실행, 4 출력, 오른쪽 실행 순서로 진행되는 것.

이처럼 가장 위쪽에 위치한 상자의 함수 호출부터 시작해 계단식으로 내려가며 자세히 조사해 나가는 분석 방법을 하향식 분석이라고 한다.

* 꼭대기부터 분석하면 같은 함수를 여러번 호출하므로 하향식 방식이 반드시 효율적이라고 말할 수는 없음.

 

상향식 분석 방법은 하향식 분석과는 반대로 아래쪽부터 쌓아올리며 분석하는 방법. 분석하는 방식에 따라 모습은 다르지만 상향식 분석이나 하향식 분석 모두 실행 결과는 같다.

 

꼬리 재귀를 제거하는 방법

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

def recur(n: int) -> int:
    while n > 0:
        recur(n - 1)
        print(n)
        n = n - 2
        
x = int(input("정숫값을 입력하세요.: "))
recur(x)

실행 결과 정숫값을 입력하세요.: 4 1 2 3 4

이렇게 하면 recur( ) 함수의 맨 끝에서 실행되는 꼬리 재귀(tail recursion)를 제거할 수 있다.

꼬리 재귀가 제거된 재귀 함수

재귀를 제거하기(스택을 사용한 비재귀적 구현)

재귀를 실행할 때 재귀 호출하는 recur(n - 1) 함수는 제거가 쉽지 않음. 이유는 n값을 출력하기 전에 recur(n - 1)을 먼저 실행하기 때문.

ex) n값이 4인 경우 재귀 호출 recur(3)의 처리가 완료될 때까지 4를 어딘가에 저장해야 가능.

현재의 n값을 임시로 저장하고, recur(n - 1)의 처리를 완료한 후 n값을 출력할 때 임시로 저장했던 n을 꺼내 값을 출력하는 형식으로 가능한데, 이 과정을 스택이 가능하게 해준다.

from stack import Stack # 미리 만들어 둔 스택 코드 활용

def recur(n: int) -> int:
    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

위 코드에서 실행 결과로 나온 recur(4)가 호출될 때의 동작은 다음과 같다.

1. n값 4를 스택에 푸시

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

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

이 과정을 지나면 n 값은 3이 되었고 이는 0보다 크므로 다시 첫번째 if문이 실행되고 위 1,2,3의 과정이 반복됨.

위 과정을 완료하면 사진과 같이 스택에 1,2,3,4 데이터가 푸시 되어있다.

 

두번째 if문에서는 다음 과정이 실행된다.

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

5. n값 1을 출력

6. n값을 2 감소시켜 -1을 대입

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

4~7의 과정을 순차적으로 실행하면 다음 그림과 같이 스택에서 입출력되는 데이터가 실행 결과로 출력되어 나타나게 됨.

이 그림을 통해 스택이 변화하는 과정과 그에 따라 n값이 어떻게 출력되는지 자세히 살펴보고 이해하는 것이 중요.