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

📌 Intro.

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

✅1️⃣ 재귀의 예시.

• 1. 팩토리얼(Factorial)
  • ↘︎ n! = n x (n-1)!이다.
  • ↘︎ 크기가 n인 팩토리얼은 크기가 n-1인 팩토리얼을 포함하고 있다.
  • ↘︎ 1부터 n까지 곱하는 n!(n 팩토리얼)은 n! = 1 x 2 x 3 x ... x (n-1) x n이다.
    • ↘︎ 여기서 맨 끝에 있는 n만 제외하면 1 x 2 x 3 x ... x (n-1)인데 이것은 (n-1)!이다.
    • ↘︎ n!은 여기에 n만 더 곱하면 된다.
      • 즉, n! = n x (n-1)!이다.

✅2️⃣ 재귀적 구조.

• ↘︎ 어떤 문제나 함수 등이 자신과 성격이 똑같지만 크기가 더 작은 문제를 하나 이상 포함하고 있을 때 재귀적 구조를 갖고 있다고 말한다.
• ↘︎ 자기 자신을 정의하거나 참조하는 구조를 의미한다.
  • ↘︎ 즉, 어떤 개념, 함수, 데이터 구조, 알고리즘 등이 자신을 반복적으로 호출하거나 포함하는 방식을 말한다.

✅3️⃣ 재귀적 구조의 개념.

• ↘︎ 정의 : 자기 자신을 참조하거나 포함하는 구조.
• ↘︎ 주요 특징 : 문제를 더 작은 부분 문제로 나누고, 이 부분 문제를 해결한 뒤 결과를 결합하여 전체 문제를 해결함.
• ↘︎ 종료 조건(Base Case) : 무한히 반복되지 않도록 멈추는 조건이 반드시 필요함.

✅4️⃣ 재귀적 구조의 장단점.

✅5️⃣ 재귀적 구조의 핵심 요소.

• ↘︎ Base Case (종료 조건) : 더 이상 재귀가 진행되지 않는 조건임.
• ↘︎ Recursive Case(재귀 조건) : 문제를 더 작은 단위로 나누고 자기 자신을 호출함.
• ↘︎ Stack 메모리 사용 : 재귀 호출마다 새로운 스택 프레임이 생성됨.

✅6️⃣ 프로그래밍과 재귀(Recursion)

• ↘︎ 대부분의 프로그래밍 언어는 함수 내부에서 자신을 호출하는 자기호출 기능을 제공한다.
• ↘︎ 영어로는 recursion이라고 하고 우리말로 보통 재귀라고 한다.
  • ↘︎ 이런 의미에서, 자료구조와 알고리즘은 관계 중심의 사고방식을 훈련하는 도구이기도 하다.

✅7️⃣ 재귀와 자료구조 그리고 알고리즘.

• ↘︎ 재귀를 모르고는 자료구조와 알고리즘을 공부할 수 없다.
• ↘︎ 재귀는 컴퓨터 과학 이론의 근간을 이루는 중요 개념.
  • ↘︎ 어렵거나 특별한 주제가 아님.
  • ↘︎ 컴퓨터 과학을 공부하다 보면 재귀는 끊임없이 다양한 얼굴로 출현함.