정의
자신을 서브루틴으로 호출하는 함수를 사용하여 문제를 해결하는 방법
자신을 호출할 때마다 주어진 문제를 여러 개의 하위 문제로 축소하는 것이 핵심이다. 재귀 호출은 더 이상 재귀를 사용하지 않고 하위 문제를 해결할 수 있는 지점에 도달할 때까지 계속된다.
재귀 함수 구현 전 두 가지를 먼저 파악해야 한다.
1. 단순 기본 케이스 - 재귀를 사용하지 않고 답을 생성하는 종료 시나리오
2. 재귀 관계 - 문제의 결과와 하위 문제의 결과 사이의 관계 (규칙 집합)
위의 두 가지 파악 후, 기저 조건에 도달할 때까지 재귀 관계에 따라 함수 자체를 호출하기만 하면 된다.
문제에 재귀적 해법이 가능하다면 다음 지침에 따라 구현 가능하다.
1. 문제를 작은 범위로 쪼개나가기
2. 원래 문제의 하위문제들을 풀기 위해 함수 재귀적으로 호출하기
3. 2의 결과로 원래 문제 풀기
Memoization
재귀는 알고리즘을 구현하는 직관적이고 강력한 방법인 경우가 많다. 하지만 현명하게 사용하지 않으면 중복 계산과 같은 원치 않는 성능 저하를 초래할 수 있다. 메모이제이션은 주로 비용이 많이 드는 함수 호출의 결과를 저장하고 동일한 입력이 다시 발생할 때 캐시된 결과를 반환하여 컴퓨터 프로그램 속도를 높이는 데 사용되는 최적화 기법이다.
시간복잡도
재귀 알고리즘이 주어졌을 때, 일반적인 시간복잡도는 다음과 같다.
시간 복잡도 = 재귀 호출 횟수 * 각 재귀 호출에 따라 발생하는 계산 시간 복잡도재귀 함수의 실행 흐름을 나타내는 트리인 실행 트리를 사용하면 시간복잡도를 쉽게 구할 수 있다. 트리의 각 노드는 재귀 함수의 호출을 나타냅니다. 따라서 트리의 총 노드 수는 실행 중 재귀 호출 횟수에 해당한다. 재귀 함수의 실행 트리는 n진 트리를 형성하며, n은 재귀 관계에서 재귀가 나타나는 횟수입니다.
예를 들어 피보나치 함수의 경우 2진 트리를 형성하고, 2진 트리의 최대 노드 수는 2^n - 1 이므로 시간 복잡도는 O(2^n)과 같다. 하지만 메모이제이션을 이용한다면 재귀 함수는 (n-1)번 호출된다. 따라서 맨 위 공식에 따라 시간복잡도는 O(n)이 된다.
공간복잡도
재귀 관련 공간과 비재귀 관련 공간을 고려해야 한다.
재귀 관련 공간
재귀 관련 공간은 재귀로 인해 직접적으로 발생하는 메모리 비용, 즉 재귀 함수 호출을 추적하는 Stack을 의미한다. 일반적인 함수 호출을 완료하기 위해 시스템은 Stack에 세 가지 중요한 정보를 저장할 공간을 할당한다.
- 함수 호출의 반환 주소. (함수 호출 다음 코드 줄)
- 함수 호출에 전달되는 매개변수.
- 함수 호출 내의 지역 변수.
스택의 이 공간은 함수 호출 중에 발생하는 최소 비용이다. 함수 호출 횟수만큼 stack에 공간이 할당되는 것이다. 함수 호출이 완료되면 이 공간은 해제된다.
재귀 관련 공간 소비로 인해 스택 오버플로라는 상황이 발생할 수 있다. 스택 오버플로는 프로그램에 할당된 스택이 최대 공간 제한에 도달하여 프로그램이 종료되는 현상이다. 재귀 알고리즘을 설계할 때는 입력이 증가할 때 스택 오버플로가 발생할 가능성이 있는지 신중하게 확인해야 한다.
비재귀 관련 공간
일반적으로 전역 변수에 할당되는 공간(일반적으로 힙 공간)을 포함한다.
재귀 여부와 관계없이, 후속 함수 호출 전에 문제의 입력을 전역 변수로 저장해야 할 수 있다. 또한 재귀 호출의 중간 결과(=메모이제이션)도 저장해야 할 수 있다. 메모이제이션으로 인해 발생하는 공간 비용을 고려해야 한다.
팁
- When in doubt, write down the recurrence relationship.
- Whenever possible, apply memoization.
- When stack overflows, tail recursion might come to help.
재귀와 함께 자주 적용되는 패러다임들
Divide and Conquer
Divide and Conquer 알고리즘은 문제를 동일하거나 관련된 두 개 이상의 하위 문제로 재귀적으로 분할하여 이러한 하위 문제가 직접 해결할 수 있을 만큼 간단해질 때까지 진행한 다음, 하위 문제의 결과를 결합하여 최종 해결책을 만든다. 다른 재귀 알고리즘과 달리, Divide and Conquer 알고리즘에서는 문제를 하나의 작은 하위 문제가 아닌 두 개 이상의 하위 문제로 분할한다.
일반적으로 다음 세 가지 단계를 거쳐 해결한다.
1. Divide: 문제를 하위 문제 집합으로 나눈다.
2. Conquer: 각 하위 문제를 재귀적으로 푼다.
3. Combine: 각 하위 문제의 결과를 합친다.
def divide_and_conquer( S ):
# (1). Divide the problem into a set of subproblems.
[S1, S2, ... Sn] = divide(S)
# (2). Solve the subproblem recursively,
# obtain the results of subproblems as [R1, R2... Rn].
rets = [divide_and_conquer(Si) for Si in [S1, S2, ... Sn]]
[R1, R2,... Rn] = rets
# (3). combine the results from the subproblems.
# and return the combined result.
return combine([R1, R2,... Rn])Backtracking
Backtracking 알고리즘은 일부 계산 문제에 대한 모든(또는 일부) 솔루션을 찾기 위한 일반 알고리즘으로, 솔루션에 대한 후보를 점진적으로 구축하고 후보가 유효한 솔루션으로 이어질 수 없다고 판단되면 즉시 후보를 포기한다. 따라서 불필요한 탐색을 많이 제거되기 때문에 Brute-force 알고리즘보다 훨씬 빠른 경우가 많다.
def backtrack(candidate):
if find_solution(candidate):
output(candidate)
return
# iterate all possible candidates.
for next_candidate in list_of_candidates:
if is_valid(next_candidate):
# try this partial candidate solution
place(next_candidate)
# given the candidate, explore further.
backtrack(next_candidate)
# backtrack
remove(next_candidate)반복 함수로의 변환
재귀는 적절하게 적용하면 우아하고 직관적이지만, stackoverflow 의 위험, 효율성, 복잡성의 문제로 반복 함수로 변환해야 할 수도 있다.
재귀 방식을 반복 방식으로 바꾸려면 다음 두 단계를 수행해야 한다.
1. 함수 내에서 시스템 호출 스택의 역할을 대체하기 위해, stack 또는 queue 자료 구조를 사용한다. 재귀가 발생할 때마다 재귀를 호출하는 대신, 매개변수를 생성한 데이터 구조에 새 요소로 삽입한다.
2. 이전에 생성한 데이터 구조에 루프를 생성합니다. 그러면 재귀의 연쇄 호출은 루프 내의 반복으로 대체된다.
