01. Recursion 재귀

재귀 함수란, 하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 방식으로 주어진 문제를 푸는 방법이다.

재귀함수는 매 호출시마다 입력값이 변한다. 입력값의 변화가 없는 호출은 무한히 반복된다.

입력값의 변화가 없거나 입력값의 변화가 특정 패턴을 반복하게 되면 그 재귀함수는 영원히 반복되다가 콜스택 초과로 종료된다.

따라서 재귀함수 설계 시에는 입력값이 종료 조건으로 수렴하는지를 꼭 검증해야 한다.

재귀 함수의 구조는 크게 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)이라고 한다.