재귀 호출
factorial() 함수는 n - 1의 팩토리얼 값을 구하기 위해 다시 자신과 똑같은 factorial() 함수를 호출하는데 이를 함수의 재귀 호출이라 합니다.
▶ 파이썬에서는 math 모듈에서 정수 x의 팩토리얼 값을 구하는 factorial() 함수를 제공합니다.
math.factorial(x)
직접 재귀 vs 간접 재귀
① 직접 재귀: factorial() 함수처럼 자신과 똑같은 함수를 호출하는 방식
② 간접 재귀: a() 함수가 b() 함수를 호출하고 다시 b() 함수가 a() 함수를 호출하는 구조
유클리드 호제법
두 정수 x와 y의 최대 공약수를 구하는 문제로, 큰 값을 작은 값으로 나누어 떨어지면 작은 값이 되지만, 나누어 떨어지지 않으면 작은 값과 나머지에 대해 같은 과정을 나누어 떨어질 때까지 재귀적으로 반복합니다.
def gcd(a: int, b: int) -> int:
if b == 0:
return a
else:
return gcd(b, a%b)
▶ 파이썬에서는 math 모듈에서 gcd() 함수를 제공합니다.
math.gcd(a, b)
재귀 알고리즘의 두 가지 분석 방법: 하향식 분석, 상향식 분석
다음과 같이 재귀 호출을 2번하는 함수가 있다고 가정합니다. 이 함수를 상향식, 하향식 분석해 보겠습니다.
def recur(n: int) -> int:
if n > 0:
recur(n - 1)
print(n)
recur(n - 2)
1. 하향식 분석
하향식 분석이란 가장 위쪽에 위치한 상자의 함수 호출부터 시작하여 계단식으로 자세히 조사해 나가는 분석 방법입니다. recur(3)이 종료된 후에 print(4)와 recur(2)가 실행됩니다.
그렇지만 recur(1), recur(2)를 여러번 호출하고 있습니다. 같은 함수를 여러 번 호출할 수 있으므로 하향식 방식이 반드시 효율적이지는 않습니다.
2. 상향식 분석
상향식 분석이란 아래쪽부터 쌓아 올리며 분석하는 방법입니다. 즉, recur(-1) 부터 하나씩 올라가며 최종적으로 recur(4)를 출력합니다.
재귀 알고리즘의 비재귀적 표현
1. 꼬리 재귀 제거
recur() 함수의 맨 끝에서 재귀 호출하는 꼬리 재귀 recur(n-2)는 '인자로 n-2를 전달한 recur() 함수의 실행'과 동일한 의미입니다. 그러므로 다음과 같이 함수를 구현할 수 있습니다.
def recur(n: int) -> int:
while n > 0:
recur(n - 1)
print(n)
n = n - 2
2. 재귀 제거
꼬리 재귀와 다르게 맨 앞에서 재귀 호출하는 recur(n-1) 함수는 제거하기 쉽지 않습니다. 왜냐하면 n 값을 출력하기 전 recur(n-1)을 실행해야하기 때문이죠. 즉, 이를 해결하기 위해 n 값을 임시로 저장할 필요가 있습니다. 이때 스택을 활용합니다.
from stack import Stack # stack.py의 Stack 클래스 import
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
