재귀 함수란, 하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 방식으로 주어진 문제를 푸는 방법이다.
재귀함수는 매 호출시마다 입력값이 변한다. 입력값의 변화가 없는 호출은 무한히 반복된다.
입력값의 변화가 없거나 입력값의 변화가 특정 패턴을 반복하게 되면 그 재귀함수는 영원히 반복되다가 콜스택 초과로 종료된다.
따라서 재귀함수 설계 시에는 입력값이 종료 조건으로 수렴하는지를 꼭 검증해야 한다.
재귀 함수의 구조는 크게 2가지로 나눌 수 있다.
종료 조건 (base case)
재귀 함수가 무한 호출에 빠지지 않게 해주는 조건을 명시하는 것이다.
이는 곧 이미 문제가 충분히 작아서, 더 작은 부분 문제로 나누지 않고도 바로 답을 알 수 있는 경우를 뜻한다.
재귀 조건 (recursive case)
종료 조건을 만족하지 못한 나머지 경우를 뜻한다.
즉, 현 문제가 너무 커서, 같은 형태의 더 작은 부분 문제를 재귀적으로 푸는 경우이다.
1부터 N까지의 합 계산
1. 반복문 활용
def sum(n):
s = 0
for i in range(1, n + 1):
s += i
return s- 수행 시간
2. 재귀적 방법 1
- 논리
def sum(n):
if n <= 1: return n
return n + sum(n-1)- 수행 시간
3. 재귀적 방법 2
- 논리
def sum(a, b): # return a + (a+1) + ... + b
if a > b: return 0
if a == b: return a
m = (a+b)//2
return sum(a, m) + sum(m+1, b)- 수행 시간
- 재귀적 방법 1과의 차이점
리스트 거꾸로 배치하기
재귀적 방법1
- 논리
def reverse(A):
if len(A) == 1:
return A
return reverse(A[1:]) + A[0]- 수행시간
재귀적 방법2
- 논리
def reverse(A, start, stop):
if start <= stop:
A[start], A[stop] = A[stop], A[start] # 양 쪽 값 바꾸기
reverse(A, start + 1, stop - 1) # 나머지 가운데 부분 재귀- 수행시간
Tail Recursion
기본적인 팩토리얼 재귀함수를 생각해보자.
def factorial(n):
if n == 1:
return n
return n * factorial(n - 1)base case(factorial(1))까지 계산이 된 후에 return 이 되어 다시 계산되어 올라오면서 전체 값이 완성이 된다.
base case에 도달했을 때, 결과를 내놓을 순 없을까? 라는 아이디어에서 출발.
def factorial(n, value = 1):
if n == 1:
return value
return factorial(n - 1, value * n)factorial(n - 1, **value * n**)과 같이 중간에 계산된 값을 직접 전달 ⇒ base case에서 이미 최종 값을 전달 받음 ⇒ return
이는 recursion stack의 내용을 overwrite하는 방식으로 메모리 사용을 크게 줄일 수 있음.
⇒ TRO(Tail Recursion optimization)이라고 한다.
