재귀와 메모이제이션을 활용한 수열 계산

 

 

 

def rs(d):
    # 입력 데이터 처리
    n = d["n"]          # 현재 계산할 숫자 n
    memo = d["memo"]    # 이미 계산된 값 저장소 (메모이제이션)

    # 이미 계산된 값이 있으면 반환
    if n in memo:
        return memo[n]

    # n이 1 이하일 때 결과는 1
    if n <= 1:
        return 1

    # 재귀 호출로 n-3과 n-1을 계산
    result = rs({"n": n - 3, "memo": memo}) + rs({"n": n - 1, "memo": memo})

    # 계산 결과를 메모리에 저장
    memo[n] = result

    # 결과 반환
    return result


# 초기 설정
num = 7
memo_dict = {"n": num, "memo": {}}

# 결과 출력
print(f"결과: {rs(memo_dict)}")

---

코드 분석

함수 설명

• rs(d)는 재귀적으로 호출되는 함수로, n값을 기준으로 계산을 수행.
• memo를 활용하여 중복 계산을 피함 (메모이제이션).
• 종료 조건:
  • n <= 1이면 결과는 1.
• 계산식: rs(n)=rs(n−3)+rs(n−1)rs(n) = rs(n-3) + rs(n-1)

실행 과정

• 입력 num = 7을 기준으로 계산.

---

계산 과정

단계별 호출

1. rs(7):rs(7)=rs(4)+rs(6)rs(7) = rs(4) + rs(6)
2. rs(4):rs(4)=rs(1)+rs(3)rs(4) = rs(1) + rs(3)
   • rs(1): 종료 조건 → 1.
   • rs(3): rs(3)=rs(0)+rs(2)rs(3) = rs(0) + rs(2)
     • rs(0): 종료 조건 → 1.
     • rs(2): rs(2)=rs(−1)+rs(1)rs(2) = rs(-1) + rs(1)
       • rs(-1): 종료 조건 → 1.
       • rs(1): 종료 조건 → 1.
     • 결과: rs(2) = 1 + 1 = 2.
   • 결과: rs(3) = 1 + 2 = 3.
   • 결과: rs(4) = 1 + 3 = 4.
3. rs(6):rs(6)=rs(3)+rs(5)rs(6) = rs(3) + rs(5)
   • rs(3): 메모이제이션 활용 → 3.
   • rs(5): rs(5)=rs(2)+rs(4)rs(5) = rs(2) + rs(4)
     • rs(2): 메모이제이션 활용 → 2.
     • rs(4): 메모이제이션 활용 → 4.
     • 결과: rs(5) = 2 + 4 = 6.
   • 결과: rs(6) = 3 + 6 = 9.
4. 최종 결과:rs(7)=rs(4)+rs(6)=4+9=13rs(7) = rs(4) + rs(6) = 4 + 9 = 13

---

출력 결과

결과: 13