[Algorithm] 재귀 알고리즘_2

05-2  재귀 알고리즘 분석

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

실습 5-3 순수한 재귀 함수 구현하기

# 순수한 재귀 함수 구현하기
# 순수한(genuinely) 재쉬 -> 재귀 호출을 여러 번 실행하는 함수

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

recur() 함수는 함수 안에서 재귀 호출을 2번 실행합니다. 이처럼 재귀 호출을 여러 번 실행하는 함수를 순수한(genuinely) 재귀라고 하는데 실제 동작은 복잡합니다. 실행 결과처럼 매개변수 n에 4를 전달하면 recur() 함수는 1, 2, 3, 1, 4, 1, 2를 한 줄에 하나씩 출력합니다. 만약에 n이 3이나 5라면 어떤 결과를 출력할지는 간단히 알 수 없습니다. 재귀 호출하는 recur() 함수를 하향식(top-down)과 상향식(bottom-up) 방법으로 분석해 보겠습니다.

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

recur(4)의 실행 과정

1. recur(3)을 실행합니다.
2. 4를 출력합니다.
3. recur(2)를 실행합니다.

위의 과정 2에서 4가 출력되려면 recur(3)의 실행을 완료한 뒤이므로 먼저 과정 1에서 recur(3)이 무엇을 하는지 아래 그림을 참고할 수 있습니다. 각각의 상자는 recur() 함수의 동작을 나타냅니다. 전달받은 값이 0 이하이면 recur() 함수는 아무 일도 하지 않으므로 비어 있다는 의미로 상자 안에 -를 표시합니다.

recur() 함수의 하향식 분석

상향식 분석

하향식 분석과는 반대로 아래쪽부터 쌓아 올리며 분석하는 방법을 상향식 분석(bottom-up analysis)이라고 합니다. 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() 함수의 상향식 분석

---

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

꼬리 재귀를 제거하기

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

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

실습 5-4 비재귀적으로 재귀 함수 구현하기(꼬리 재귀를 제거)

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

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

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

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

재귀를 제거하기

꼬리 재귀와 달리 맨 앞에서 재귀 호출하는 recur(n - 1) 함수는 제거하기가 쉽지 않습니다. n값을 출력하기 전에 recur(n - 1)을 실행해야 하기 때문입니다. 예를 들어 n값이 4인 경우 재귀 호출 recur(3)의 처리가 완료될 때까지 4를 어딘가에 저장해야 합니다. 현재의 n값을 임시로 저장할 필요가 있기 때문입니다. 또한 recur(n - 1)의 처리를 완료하고 n값을 출력할 때 임시로 저장했던 n을 꺼내 그 값을 출력해야 합니다. 이 문제는 스택(stack)으로 해결할 수 있습니다.

실습 5-5 스택으로 재귀 함수 구현하기(재귀를 제거)

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

from stack import 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

실습 5-5의 recur() 함수 실행에 따른 스택의 변화

1. n값 4를 스택에 푸시합니다.[a]
2. n값을 1 감소시켜 3으로 만듭니다.
3. continue 문이 실행되어 while 문으로 돌아갑니다.
4. 스택에서 팝한 값 1을 n으로 꺼냅니다.[e]
5. n값 1을 출력합니다.
6. n값을 2 감소시켜 -1로 합니다.
7. continue 문의 동작으로 while 문의 맨 앞으로 돌아갑니다.

- 출처: Do it! 자료구조와 함께 배우는 알고리즘 입문 - 파이썬 편
- notebook ipynb file: https://github.com/heejvely/Algorithm/blob/main/Do_it_algorithm/Do_it_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98_%EC%9E%AC%EA%B7%80%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98.ipynb

GitHub - heejvely/Algorithm: 파이썬 알고리즘 인터뷰 책을 참고한 파이썬 알고리즘 연습