02. 수열의 귀납적 정의: 점화식 (Recurrence Relation)

1. 학습 목표 (Learning Objectives)

• 수열의 숫자를 단순히 규칙(일반항 $a_n$)으로 찍어내는 대신, “이전 항이 다음 항을 창조해 낸다” 는 이웃 간의 연결 고리로 수열을 세팅하는 ‘귀납적 정의(점화식)’ 에 대해 학습합니다.
• 파이썬(Python) 프로그래밍의 핵심 개념 중 하나인 재귀 함수(Recursive Function) 를 통해 점화식이 어떻게 스스로를 복제 호출하여 팩토리얼($N!$)을 폭발 연산해 내는지 실습합니다.

2. 점화식, 수열의 도화선에 불을 붙이다

지금까지 우리는 수열을 배울 때 $a_n = 2n - 1$ 같은 ‘일반항 전지전능 봇’ 을 썼습니다. 여기에 $n=100$ 을 넣으면 첫 항, 두 번째 항 따위는 다 무시하고 중간 과정 없이 순식간에 텔레포트하여 100번째 항의 값인 $199$ 를 다이렉트로 쏴 줍니다. 아주 빠르고 편하죠.

하지만 수학자들은 수열을 완전히 철학적으로 다른 시각에서 쳐다보기 시작합니다.

“수열이란 원래 1번 항이 2번 진화하고, 2번 항이 쪼개져 3번이 되는 ‘생태계 릴레이’ 아니었나? 바로 전 항의 모양을 알아야만 다음 내 모습($n+1$)을 유추할 수 있는 릴레이 구조로 수열을 묶어보자!”

이처럼 처음 시작하는 도미노 세팅값(초항 $a_1$) 하나를 던져주고, “이전 항 $a_n$ 과 다음 항 $a_{n+1}$ 사이의 관계 릴레이식” 을 통해 수열을 연쇄 렌더링 시키는 방식을 수열의 귀납적 정의, 가장 유명한 한자어 용어로 점화식(Recurrence Relation) 이라고 부릅니다. (불을 붙이는 도화선 점화처럼 연쇄 폭발을 일으킨다는 뜻입니다!)

[예시] 등차수열의 점화식: $a_{n+1} = a_n + d \quad (a_1 = a)$ “내 다음 모습($a_{n+1}$)은, 방금 전 내 모습($a_n$)에다가 공차 $d$ 스탯을 더 먹은 것이다!”

3. 거울 속의 거울: 파이썬 재귀 함수 (Recursion)

이 점화식의 릴레이 호출 본능은 컴퓨터 프로그래밍 세계로 넘어오면서 가장 아름답게 구현됩니다. 자신의 목적을 달성하기 위해, 함수 내부에서 “스스로 자기 자신(함수)을 다시 부르면서 안으로 안으로 파고들어 가는 구조” 를 프랙탈 재귀 함수(Recursive Function) 라고 합니다.

수학적으로 가장 명확한 재귀 점화식 모델은 1부터 $N$까지의 모든 정수를 곱해버리는 폭파 연산 공장, ‘팩토리얼(Factorial, $N!$)’ 입니다.

• $5! = 5 \times 4 \times 3 \times 2 \times 1$
• 하지만 점화식 머리로 쳐다보면? $\rightarrow \mathbf{5! = 5 \times 4!}$ 입니다!
• 다시 $4!$ 은 뭐죠? $\rightarrow \mathbf{4 \times 3!}$ 입니다!

[팩토리얼 점화식] $F(n) = n \times F(n-1)$ (단, $F(1) = 1$ 에서 재귀 루프를 정지시킨다!)

4. 파이썬 재귀 폭발 스캐너 시뮬레이션

파이썬 코드로 이 자기 자신을 쪼개고 들어가는 재귀의 소용돌이를 렌더링 보겠습니다.

def factorial_recursive(n):
    """
    점화식 구조를 이용해 팩토리얼(n!)을 재귀 방식으로 스스로 무한 호출 분쇄하는 함수
    """
    # 1. 종료 조건 (Base Case): 
    # 재귀는 끝나는 지점이 없으면 메모리(거울)가 무한 증식하여 파이썬 컴파일러가 폭파됩니다!
    if n == 1:
        print(f"   [바닥 도달] factorial_recursive(1) 이 호출됨. 제일 끝단 1을 반환! (거꾸로 튕겨올라감)")
        return 1
        
    # 2. 점화식 릴레이 (Recursive Step):
    print(f"⚡ [재귀 진입] factorial_recursive({n}) 호출 ➔ 일단 대기! 내 하위 점화식인 {n} * factorial_recursive({n-1}) 호출!")
    
    # 자기 자신인 함수를 매개변수만 1 깎아서 다시 실행! 
    # (결과가 나올 때까지 현재 함수는 일시 정지 상태로 스택 메모리에 차곡차곡 쌓임)
    result = n * factorial_recursive(n - 1)
    
    # 하단의 바닥 1부터 다시 계산되어 거꾸로 폭발 렌더링 होकर 올라오는 결괏값들 출력
    print(f"💥 [재귀 복귀] 하위 연산 끝남! n={n} ➔ 팩토리얼 계산 복원 결과 = {result}")
    return result

# 5! 연산 스크립트 실행
target = 5
print(f"🚀 [점화식 재귀 엔진] {target}! 연산 시작\n" + "-"*60)
final_answer = factorial_recursive(target)
print("-"*60 + f"\n✅ 최종 {target}! 타겟 해킹 결과물: {final_answer}")

터미널 실행 콘솔 렌더링 (재귀 스택 궤적):

🚀 [점화식 재귀 엔진] 5! 연산 시작
------------------------------------------------------------
⚡ [재귀 진입] factorial_recursive(5) 호출 ➔ 일단 대기! 내 하위 점화식인 5 * factorial_recursive(4) 호출!
⚡ [재귀 진입] factorial_recursive(4) 호출 ➔ 일단 대기! 내 하위 점화식인 4 * factorial_recursive(3) 호출!
⚡ [재귀 진입] factorial_recursive(3) 호출 ➔ 일단 대기! 내 하위 점화식인 3 * factorial_recursive(2) 호출!
⚡ [재귀 진입] factorial_recursive(2) 호출 ➔ 일단 대기! 내 하위 점화식인 2 * factorial_recursive(1) 호출!
   [바닥 도달] factorial_recursive(1) 이 호출됨. 제일 끝단 1을 반환! (거꾸로 튕겨올라감)
💥 [재귀 복귀] 하위 연산 끝남! n=2 ➔ 팩토리얼 계산 복원 결과 = 2 (2*1)
💥 [재귀 복귀] 하위 연산 끝남! n=3 ➔ 팩토리얼 계산 복원 결과 = 6 (3*2)
💥 [재귀 복귀] 하위 연산 끝남! n=4 ➔ 팩토리얼 계산 복원 결과 = 24 (4*6)
💥 [재귀 복귀] 하위 연산 끝남! n=5 ➔ 팩토리얼 계산 복원 결과 = 120 (5*24)
------------------------------------------------------------
✅ 최종 5! 타겟 해킹 결과물: 120

이 콘솔 로그를 보면 코드가 안에서 끝없이 거울 방으로 파고 들어갔다가, 1이라는 밑바닥을 찍자마자 연쇄적으로 스택을 해체하며 결괏값을 뽑아 올리는 엄청난 점화식 귀납 메커니즘을 볼 수 있습니다.

5. 학습 정리 (Summary)

1. 수열의 귀납적 정의(점화식): 앞뒤 항들 간의 상관관계(릴레이식)를 이용하여 전체 수열의 구조를 코딩하는 방법입니다. 결과만 알기보다는 번식과 파생의 과정을 모델링하는 데 유리합니다.
2. 파이썬 재귀 함수(Recursion): 점화식 로직을 코드 안에서 자기 자신 함수를 계속 불러오는 형태로 반복 구현한 것입니다. 단, 멈추는 밑바닥 제한 브레이크 장치(종료 조건)가 없으면 컴퓨터 램(RAM) 메모리가 터져버리는 멜트다운 오류(Stack Overflow)가 터집니다.