점화식: 재귀를 수학으로

재귀 함수의 동작을 수식으로 표현:
T(n) = (자기 호출 시간) + (자기 호출 외 시간)

선형: T(n) = T(n-1) + O(1)        → O(n)
분할 정복: T(n) = 2T(n/2) + O(n)   → O(n log n)
지수: T(n) = T(n-1) + T(n-2) + 1   → O(2^n)

# T(n) = T(n-1) + 1, T(1) = 1
# = T(n-2) + 1 + 1
# = T(n-3) + 1 + 1 + 1
# = ...
# = T(1) + (n-1) = n
# → O(n)

def linear_recursion(n):
    if n == 1:
        return 1
    return linear_recursion(n - 1) + 1

# 호출 횟수 검증
count = 0
def linear_counted(n):
    global count
    count += 1
    if n == 1:
        return 1
    return linear_counted(n - 1) + 1

count = 0
linear_counted(100)
print(count)  # 100 → O(n) 검증

# T(n) = 2T(n/2) + n  (머지 정렬)
# 풀이:
# T(n) = 2T(n/2) + n
#      = 2[2T(n/4) + n/2] + n = 4T(n/4) + 2n
#      = 4[2T(n/8) + n/4] + 2n = 8T(n/8) + 3n
#      = ...
#      = 2^k T(n/2^k) + kn
# n/2^k = 1 일 때 종료 → k = log₂ n
# T(n) = n × T(1) + n log n = O(n log n)


# T(n) = T(n/2) + 1  (이진 검색)
# = T(n/4) + 2
# = T(n/8) + 3
# = ...
# = T(1) + log₂ n
# → O(log n)


# T(n) = 2T(n/2) + 1  (이진 트리 순회)
# 풀이: T(n) = 2T(n/2) + 1
#         = 4T(n/4) + 3
#         = ...
#         = 2^k T(n/2^k) + (2^k - 1)
# k = log n → T(n) = n + n - 1 = O(n)

T(n) = a·T(n/b) + f(n) 형태
  · a: 자기 호출 횟수
  · n/b: 부분 문제 크기
  · f(n): 호출 외 작업

세 케이스:
1. f(n) = O(n^c), c < log_b(a) → T(n) = O(n^log_b(a))
2. f(n) = O(n^c), c = log_b(a) → T(n) = O(n^c × log n)
3. f(n) = O(n^c), c > log_b(a) → T(n) = O(f(n))


예시:
머지 정렬: a=2, b=2, f(n)=n (c=1)
  log_2(2) = 1 = c → 케이스 2
  T(n) = O(n × log n) = O(n log n) ✅

이진 검색: a=1, b=2, f(n)=1 (c=0)
  log_2(1) = 0 = c → 케이스 2
  T(n) = O(n^0 × log n) = O(log n) ✅

행렬 곱셈: a=8, b=2, f(n)=n² (c=2)
  log_2(8) = 3 > c → 케이스 1
  T(n) = O(n^3) ✅ (스트라센 알고리즘은 a=7로 줄임)

# T(n) = T(n-1) + T(n-2) + 1
# 풀이는 복잡 — 황금비 관련
# T(n) ≈ φ^n  여기서 φ = (1+√5)/2 ≈ 1.618
# → O(φ^n) ≈ O(2^n)


def fib_naive(n):
    if n <= 2:
        return 1
    return fib_naive(n - 1) + fib_naive(n - 2)


# 호출 횟수 — 폭발
import sys
sys.setrecursionlimit(10000)

count = 0
def fib_counted(n):
    global count
    count += 1
    if n <= 2:
        return 1
    return fib_counted(n - 1) + fib_counted(n - 2)


count = 0; fib_counted(20); print(f"n=20: {count}회")  # 13529회
count = 0; fib_counted(30); print(f"n=30: {count}회")  # 1664079회
count = 0; fib_counted(35); print(f"n=35: {count}회")  # 약 1800만회
# n=40+에서는 분 단위 시간

def fib_memo(n, cache={}):
    if n in cache:
        return cache[n]
    if n <= 2:
        return 1
    cache[n] = fib_memo(n - 1) + fib_memo(n - 2)
    return cache[n]


# 호출 횟수 — 각 n마다 1번만
count = 0
def fib_memo_counted(n, cache={}):
    global count
    count += 1
    if n in cache:
        return cache[n]
    if n <= 2:
        return 1
    cache[n] = fib_memo_counted(n - 1, cache) + fib_memo_counted(n - 2, cache)
    return cache[n]


count = 0; fib_memo_counted(100); print(f"n=100: {count}회")  # 199회
count = 0; fib_memo_counted(1000); print(f"n=1000: {count}회")  # 1999회
# → O(n)


# functools.lru_cache로 자동 메모이제이션
from functools import lru_cache

@lru_cache(maxsize=None)
def fib_lru(n):
    if n <= 2:
        return 1
    return fib_lru(n - 1) + fib_lru(n - 2)


print(fib_lru(100))

# 피보나치 폐쇄형 (비넷 공식)
# F(n) = (φ^n - ψ^n) / √5
# φ = (1+√5)/2, ψ = (1-√5)/2

import math

def fib_binet(n):
    sqrt5 = math.sqrt(5)
    phi = (1 + sqrt5) / 2
    psi = (1 - sqrt5) / 2
    return round((phi**n - psi**n) / sqrt5)


print(fib_binet(10))  # 55
print(fib_binet(50))  # 12586269025
# O(1) 시간 — 단, 부동소수점 오차로 큰 n에서 부정확