재귀 알고리즘 분석 방법

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

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

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

recur(x)

하향식 top-down 분석

가장 상위 함수 호출부터 시작하여 계단식으로 자세히 조사해 나가는 분석 방법

recur(4) 실행 과정
1. recur(3) 실행
2. 4 출력
3. recur(2) 실행

상향식 bottom-up 분석

하향식 분석과는 반대로 아래쪽부터 쌓아 올리며 분석하는 방법

recur(1)의 실행 과정
1. recur(0) 실행
2. 1 출력
3. recur(-1) 실행

recur(2)의 실행 과정
1. recur(1) 실행
2. 2 출력
3. recur(0) 실행

꼬리 재귀 제거하기

• recur() 함수의 맨 끝에서 재귀 호출하는 꼬리 재귀 recur(n-2) 함수의 의미는 '인수로 n-2의 값을 전달하고 recur() 함수를 호출하는 것'
• 다음 동작으로 변경 가능
  n 의 값을 n-2로 업데이트하고 함수의 시작 지점으로 돌아감

재귀 제거하기

n값을 출력하기 전에 recur(n-1)을 실행해야 하기 때문에, 맨 앞에서 재귀호출하는 recur(n-1) 함수 제거는 까다로움
현재의 n값을 임시로 저장해야 함
stack으로 해결하기

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)