재귀 (Recursion)

재귀함수는 함수의 내부에서 자기 자신을 다시 호출하는 함수를 뜻한다.
ex) 피보나치 수열, 팩토리얼 구현 등

일반적인 재귀 함수의 특징

1. 함수의 호출이 트리 구조를 가진다.
(트리란 사이클이 없는 연결 그래프를 의미)

2. 재귀적으로 함수를 호출하는 대신 바로 함수를 종료하는 기저 사례(base case)를 가진다.
(기저 사례는 트리의 리프 노드(= 자식 노드가 없는 노드)에 해당)

분할 정복 (Divide and Conquer)

큰 문제를 작은 문제로 분할(divide)하고 나눠진 작은 문제를 하나하나씩 정복(conquer)하여, 작은 문제의 답으로 큰 문제의 답을 구하는 것을 분할정복이라고 합니다.

이때 기저 사례(base case)를 둬서 더 이상 Divide하지 않고 바로 답을 구하는 기저 사례를 만들면 문제를 쪼갠 뒤 합치는 과정을 통해 원래 문제의 답을 구할 수 있다. 이러한 분할 정복의 구조 때문에 거의 대부분 분할 정복은 재귀로 구현된다.

중복 제거 (Memoization & Tabulation)

재귀함수는 알고리즘을 간단히 축약할 수 있다는 장점이 있지만, 스택 오버 플로어 문제와 런타임이 비교적 오래 걸린다는 단점이 있다. 단점을 극복하기 위해, Memoization과 Tabulation 이 두 개는 메모리를 더 사용하는 대신, 계산 시간을 줄인다.

예를 들어, 다음과 같은 피보나치 수열을 구하는 예제가 있다.

def fibonacci(num):
    if num == 1 or num == 2: return 1
    return fibonacci(num - 1) + fibonacci(num - 2)

Memoization

재귀함수에서 일어나는 중복 계산을 피하기 위한 방법이다. 피보나치를 계산해서 배열에 저장해놓고, 필요할 때 이용한다. 오버헤드는 발생하지 않는다. 런타임 시간은 줄고, 메모리 사용은 증가한다는 특징이 있다.

record = [0 for _ in range(50)]
record[0] = 1
record[1] = 1

def fibonacci(num):
    global record
    index = num - 1
    
    if record[index] == 0:
        record[index] = fibonacci(num - 1) + fibonacci(num - 2)
    return record[index]

값이 리스트에 저장해되어 있기 때문에 중복 계산을 생략할 수 있다.

Tabulation

Memoiation과 동일하게 함수 중복을 줄여주는 방식. 다른 점이라면 미리 피보나치를 필요한 만큼 계산해두고 꺼내쓰는 방식이다.

record = [0 for _ in range(50)]
record[0] = 1
record[1] = 1

def fibonacci_table():
    global record
    for i in range(2, 50):
        record[i] = record[i-1] + record[i-2]

fibonacci_table()