[5.15] 05-2 재귀 알고리즘 분석

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

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

x = int(input('정수를 입력하세요 : '))
recur(x)

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

하향식 분석 top down - 가장 위쪽의 함수 호출부터 계단식으로 조사

- recur(3) -> recur(1), recur(2) -> recur(1), recur(0) ->

상향식 분석 bottom up - 아래쪽부터 샇아 올리며 분석

- recur(0), recur(1), recur(2) - - - > 

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

꼬리 재귀를 제거하기

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

print(recur(3))

재귀를 제거하기

스택을 활용한다.

- 왜 안되는거지? 수정할 것  -> 왜 안되는지 모르겠다... ㅜㅜ

from class_making import Stack

def recur(n: int) -> int:
    s = Stack(n)
    
    while n >= 0:
        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)