python/Data Structure
chapter 5 - 2. 재귀 알고리즘 분석
seondeok
2022. 1. 20. 20:31
순수한 재귀 = 재귀호출을 여러 번 실행하는 함수
하향식 분석 : 가장 위쪽에 위치한 상자의 함수 호출부터 시작하여 계단식으로 자세히 조사해 나가는 분석방법
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
# 순수한 재귀 함수 구현하기 >> 하향식 분석
def recur(n: int) -> int:
"""순수한 재귀 함수 recur의 구현"""
if n > 0:
recur(n-1)
print(n)
recur(n-2)
x = int(input(f'정숫값을 입력하세요.: '))
recur(x)
|
cs |
recur(4)의 실행과정
1. recur(3)을 실행
2. 4를 출력
3. recur(2)를 출력
상향식 분석 : 아래쪽부터 쌓아 올리며 분석하는 방법
1
2
3
4
5
6
7
8
9
10
11
|
# 상향식 분석
def recur(n :int ) -> int:
"""순수한 재귀 함수 recur의 구현(거꾸로 출력)"""
if n > 0:
recur(n - 2)
print(n)
recur(n - 1)
x = int(input(f'정숫값을 입력하세요.: '))
|
cs |
recur(1)의 실행과정
1. recur(0)을 출력
2. 1을 출력
3.recur(-1)을 출력
재귀 알고리즘의 비재귀적 표현
꼬리 재귀를 제거하기
-n값을 2 감소시킨 뒤 함수의 시작 지점으로 돌아감
1
2
3
4
5
6
7
8
9
|
# 비재귀적으로 재귀 함수 구현하기(꼬리 재귀를 제거)
def recur(n: int) -> int:
"""꼬리 재귀를 제거한 recur()함수"""
while n > 0:
recur(n-1)
print(n)
n = n - 2
|
cs |
재귀를 제거하기 >> 스택을 이용
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
# 스택으로 재귀함수 구현하기
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)
|
cs |
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 문으로 돌아감