chapter 5 - 2. 재귀 알고리즘 분석

 

순수한 재귀 = 재귀호출을 여러 번 실행하는 함수

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

 

# 순수한 재귀 함수 구현하기 >>   하향식 분석
def recur(n: int) -> int:
 
    """순수한 재귀 함수 recur의 구현"""
 
    if n > 0:
        recur(n-1)
        print(n)
        recur(n-2)
 
x = int(input(f'정숫값을 입력하세요.: '))
 
recur(x)
 

recur(4)의 실행과정

1. recur(3)을 실행

2. 4를 출력

3. recur(2)를 출력

 

상향식 분석 : 아래쪽부터 쌓아 올리며 분석하는 방법

#  상향식 분석
 
def recur(n :int ) -> int:
 
    """순수한 재귀 함수 recur의 구현(거꾸로 출력)"""
 
    if n > 0:
        recur(n - 2)
        print(n)
        recur(n - 1)
x = int(input(f'정숫값을 입력하세요.: '))   

recur(1)의 실행과정

1. recur(0)을 출력

2. 1을 출력

3.recur(-1)을 출력

 

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

꼬리 재귀를 제거하기 

-n값을 2 감소시킨 뒤 함수의 시작 지점으로 돌아감

# 비재귀적으로 재귀 함수 구현하기(꼬리 재귀를 제거)
 
def recur(n: int) -> int:
 
    """꼬리 재귀를 제거한 recur()함수"""
    while n > 0:
        recur(n-1)
        print(n)
        n = n - 2

 

재귀를 제거하기 >> 스택을 이용

# 스택으로 재귀함수 구현하기
from stack import Stack
 
def recur(n:int) ->int:
 
    """재귀를 제거한 recur()함수"""
    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)

recur(4)를 호출

1. n값 4를 스택에 푸시

2. n값을 1감소시킴

3. continue문을 통해 while 문으로 돌아감

4. 스택에 4,3,2,1 순으로 push

 

1. 스택에서 1을 출력

2. 1을 2만큼 감소 시킴

3.continue문을 통해 while 문으로 돌아감