🧩 [Data Structure] 자료구조와 재귀

✅1️⃣ 자료구조와 재귀.

📌 Intro.

• ↘︎ 재귀: ‘내 안의 나를 찾는 것’
  • ↘︎ 즉, 성격은 같고 크기만 작은 나를 찾아 큰 나와 작은 나가 연결된 관계를 드러내는 것.

✅2️⃣ 자료구조와 재귀의 예시.

• ↘︎ 팩토리얼(Factorial)
  • ↘︎ 1부터 n까지 곱하는 n!(n 팩토리얼)은 $n!\ =\ 1\ ×\ 2\ ×\ 3 \ × ﹒﹒﹒\ × \ (n-1)\ ×\ n$ 이다.
  • ↘︎ 여기서 맨 끝에 n만 제외하면 $1\ ×\ 2\ ×\ 3 \ × ﹒﹒﹒\ × \ (n-1)$인데 이것은 (n-1)!이다.
    • ↘︎ n!은 여기에 n만 더 곱하면 된다.
      • ↘︎ “즉, $n!\ =\ n\ ×\ (n-1)!$”
        • ↘︎ 크기가 n인 팩토리얼은 크기가 n-1인 팩토리얼을 포함하고 있다.
        • ↘︎ 즉, 성격은 같고 크기만 작은 나를 찾아 큰 나와 작은 나가 연결된 관계를 드러낸 것이다.
          • ↘︎ 이처럼 어떤 문제나 함수 등이 자신과 성격이 똑같지만 크기가 더 작은 문제를 하나 이상 포함하고 있을 때 “재귀적 구조”를 갖고 있다고 말한다.

✅3️⃣ 자료구조와 알고리즘 그리고 재귀의 관계.

• ↘︎ 대부분의 프로그래밍 언어는 함수 내부에서 자신을 호출하는 자기호출(재귀) 기능을 제공한다.
  • ↘︎ 자료구조와 알고리즘은 관계 중심의 사고방식을 훈련하는 도구이기도 하다.
• ↘︎ 재귀는 학부에서 알고리즘을 다룰 때 명시적으로 40% 정도, 명시적으로 드러나지 않지만 재귀적 성격을 갖고 있는 것 까지 합하면 80% 정도나 차지하는 주제다.
• ↘︎ 자료구조에서도 상당히 높은 비율을 차지한다.
• ↘︎ 재귀를 모르고 자료구조와 알고리즘을 공부할 수 없다.
• ↘︎ 재귀는 컴퓨터 과학 이론의 근간을 이루는 중요 개념으로, 어렵거나 특별한 주제가 아니다.
• ↘︎ 컴퓨터 과학을 공부하다 보면 재귀는 끊임없이 다양한 얼굴로 출현한다.
  • ↘︎ 따라서 이 주제에 대해 숨 쉬듯이 자연스럽게 받아들여야 한다.