🧩 [Data Structure] 재귀 구조의 예(1) - 수열

✅1️⃣ 수열.

• 1. 초항(First Term)
  • ↘︎ 정의 : 수열에서 첫 번째 항을 의미함.
  • ↘︎ 기호 : 일반적으로 초항은 $a_1$ 또는 $a$로 나타냄.
  • ↘︎ 예시 :
    • 수열: 2, 4, 6, 8, …
    • 초항: $a_1 = 2$
• 2. 공차(Common Difference)
  • ↘︎ 정의 : 등차수열에서 연속된 두 항의 차이를 의미함.
  • ↘︎ 기호 : 일반적으로 공차는 $d$로 나타냄.
  • ↘︎ 공식 :
    • ↘︎ $d = a_{n+1} - a_n$
  • ↘︎ 예시 :
    • ↘︎ 수열 : 2, 4, 6, 8, …
    • ↘︎ 공차 : $d = 4 - 2 = 2$
• 3. 점화식 (Recurrence Relation)
  • ↘︎ 정의 : 수열의 각 항을 이전 항(또는 몇 개의 항)을 이용해 표현한 식임.
  • ↘︎ 기호 : 보통 $a_{n+1} = a_n + d$ 형태로 나타남.
  • ↘︎ 예시 :
    • ↘︎ 수열 : 2, 4, 6, 8, …
    • ↘︎ 점화식 : $a_{n+1} = a_n + 2$
• 4. 등차수열 (Arithmetic Sequence)
  • ↘︎ 정의 : 연속된 항들의 차이가 일정한 수열.
  • ↘︎ 일반항 공식 :
    • ↘︎ $a_n = a + (n-1)d$
      • ↘︎ $a$ : 초항
      • ↘︎ $d$ : 공차
      • ↘︎ $n$ : 항의 번호
  • ↘︎ 예시 :
    • ↘︎ 수열 : $2, 4, 6, 8, …$
    • ↘︎ 초항 : $a = 2$
    • ↘︎ 공차 : $d = 2$
    • ↘︎ 5번 째 항 : $a_5 = 2 + (5-1) \cdot 2 = 10$

✅2️⃣ 재귀적 구조 알고리즘 예시.

📌 등차수열

• ↘︎ $a_n = a_{n-1}+3, a_1 = 1$
  • ↘︎ 초항이 1, 공차가 3인 등차수열의 점화식.
    • ↘︎ 수열의 n번째 원소는 자신과 성격이 똑같지만 순서가 하나 작은 $(n-1)$번째 원소에 3을 더한 것임.
    • ↘︎ 첫 번째 원소는 1.
      • ↘︎ 이것을 재귀 알고리즘으로 구현하면 아래와 같다.

          seq(n):
          if (n = 1)
              return 1
          else
              return seq(n-1) + 3
        

      • ↘︎ 알고리즘 seq(n)은 seq(n-1)을 호출, seq(n-1)은 seq(n-2)를 호출.
      • ↘︎ seq(n-2)는 seq(n-3)을 호출… seq(2)는 seq(1)을 호출하고, seq(1)은 1을 리턴하고 끝남.
      • ↘︎ seq(1)이 끝나면 역순으로 진행됨.
      • ↘︎ seq(2)는 seq(1)의 리턴 값을 받아 3을 더해 리턴
      • ↘︎ seq(3)은 seq(2)의 리턴 값을 받아 3을 더해 리턴
      • ↘︎ seq(4)는 seq(3)의 리턴 값을 받아 3을 더해 리턴
      • ↘︎ seq(n)은 seq(n-1)의 리턴 값을 받아 3을 더해 리턴하면서 전체가 끝남.
        • ↘︎ 등차수열은 결과를 바로 계산할 수 있는 식이 있어 굳이 이렇게 구할 필요가 없지만 그 속에 재귀적 구조가 있음을 말하려는 것이다.
• ↘︎ 재귀 알고리즘은 반복해서 호출하다가 언젠가 끝나야 하는데 이를 위한 경계 조건을 항상 갖고 있어야 한다.
  • ↘︎ 위 알고리즘에서는 if(n=1)이 경계 조건이다
    • ↘︎ 수열의 초항에 해당한다.

      📌 피보나치 수열

• ↘︎ 피보나치 수열은 다음과 같다.
  • ↘︎ 첫 두 항은 1이고, 나머지 항은 각각 직전 두 항을 더한 값이다.
  • ↘︎ $f_n = f_{n-1} + f_{n-2}, f_1 = f_2 = 1$
    • ↘︎ 이것을 재귀 알고리즘으로 구현하면 다음과 같다.

        fib(n):
        if (n = 1 or n = 2)
            return 1
        else
            return fib(n-1) + fib(n-2)
      

• ↘︎ 이는 재귀 알고리즘으로 구현한 치명적인 예다.
  • ↘︎ 시간이 너무 많이 걸리기 때문이다.
  • ↘︎ 지수함수적으로 증가한다는 느낌이다.
    • ↘︎ 이렇게 엄청난 시간이 걸리는 이유는 한 번 계산해놓은 결과를 계속 호출하여 지수함수적인 중복을 일으키기 때문이다.
    • ↘︎ 이 문제를 아래와 같이 계산하면 fib_fase(100)은 천만 분의 1초도 걸리지 않는다.

        fib_fast(n):
        f[1] ← f[2] ← 1 ◀︎ "f[2] ← 1"과 "f[1] ← 1"을 한꺼번에 적어놓은 것
        for i ← 3 to n
            f[i] ← f[i-1] + f[i-2]
            return f[n]
      

• ↘︎ 재귀는 문제를 해결하는 유용한 도구이지만 잘못 쓰면 치명적이다.
• ↘︎ 자료구조와 알고리즘에서는 주로 재귀가 유용할 경우에 사용한다.