재귀와 팩토리얼: n! = n × (n-1)!

수학 정의: n! = n × (n-1)!
기저: 0! = 1, 1! = 1

재귀 = "큰 문제 → 동일 구조의 작은 문제로 분할"
        + "기저 조건"

def factorial(n):
    # 기저 조건 — 반드시 필요
    if n <= 1:
        return 1
    # 재귀 호출
    return n * factorial(n - 1)


print(factorial(5))   # 120
print(factorial(10))  # 3628800
print(factorial(20))  # 2432902008176640000


# 호출 스택 시각화
def factorial_traced(n, depth=0):
    indent = '  ' * depth
    print(f"{indent}factorial({n}) 호출")
    if n <= 1:
        print(f"{indent}→ 1 반환 (기저)")
        return 1
    result = n * factorial_traced(n - 1, depth + 1)
    print(f"{indent}→ {result} 반환")
    return result


factorial_traced(5)
# factorial(5) 호출
#   factorial(4) 호출
#     factorial(3) 호출
#       factorial(2) 호출
#         factorial(1) 호출
#         → 1 반환 (기저)
#       → 2 반환
#     → 6 반환
#   → 24 반환
# → 120 반환

# ❌ 기저 조건 없음
def bad_factorial(n):
    return n * bad_factorial(n - 1)
    # n=5 → 4 → 3 → ... → -1 → -2 → ...
    # 영원히 멈추지 않음

# 결과: RecursionError: maximum recursion depth exceeded
# Python 기본 한도: 약 1000 깊이


# ✅ 기저 조건 + 진행 보장
def good_factorial(n):
    if n < 0:
        raise ValueError("음수 불가")  # 입력 검증
    if n <= 1:
        return 1
    return n * good_factorial(n - 1)

import sys

print(sys.getrecursionlimit())  # 1000 (기본값)


# 깊은 재귀 시도
def deep(n):
    if n == 0:
        return 0
    return 1 + deep(n - 1)


# print(deep(2000))  # RecursionError

# 한도 늘리기 (위험 — 메모리 폭주 가능)
sys.setrecursionlimit(10000)
print(deep(5000))  # 5000


# 안전한 대안 — 반복문으로 변환
def deep_iter(n):
    result = 0
    while n > 0:
        result += 1
        n -= 1
    return result


print(deep_iter(1_000_000))  # 1000000 (재귀 한도 무관)

# 꼬리 재귀: 마지막 동작이 자기 호출 (다른 연산 X)
def factorial_tail(n, acc=1):
    if n <= 1:
        return acc
    return factorial_tail(n - 1, n * acc)  # 마지막이 함수 호출


print(factorial_tail(10))  # 3628800

# Python·JavaScript는 꼬리 재귀 최적화 안 함 — 여전히 스택 사용
# Scheme·Haskell·Erlang은 꼬리 재귀를 반복문으로 자동 변환

# Python에서 꼬리 재귀를 안전하게 — 데코레이터 트릭
import functools

def trampoline(f):
    @functools.wraps(f)
    def wrapper(*args):
        result = f(*args)
        while callable(result):
            result = result()
        return result
    return wrapper


@trampoline
def factorial_safe(n, acc=1):
    if n <= 1:
        return acc
    return lambda: factorial_safe(n - 1, n * acc)


print(factorial_safe(2000))  # 큰 수도 OK (Python 임의 정밀도)

# 1. 거듭제곱 a^n
def power(a, n):
    if n == 0:
        return 1
    if n == 1:
        return a
    return a * power(a, n - 1)


# 더 빠른 — O(log n) 분할 정복
def power_fast(a, n):
    if n == 0:
        return 1
    if n % 2 == 0:
        half = power_fast(a, n // 2)
        return half * half
    return a * power_fast(a, n - 1)


print(power_fast(2, 20))  # 1048576


# 2. 최대공약수 (유클리드 호제법)
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


print(gcd(48, 36))  # 12
print(gcd(101, 17)) # 1


# 3. 하노이의 탑
def hanoi(n, src, dst, via):
    if n == 1:
        print(f"{src} → {dst}")
        return
    hanoi(n - 1, src, via, dst)
    print(f"{src} → {dst}")
    hanoi(n - 1, via, dst, src)


hanoi(3, 'A', 'C', 'B')
# A → C / A → B / C → B / A → C / B → A / B → C / A → C