완전검색 그리디 - 반복과 재귀

1. 반복(Iteration)과 재귀(Recursion)

• 반복과 재귀는 유사한 작업을 수행할 수 있습니다.
• 반복은 수행하는 작업이 완료될 때까지 계속 반복합니다.
  • 루프(for, while 구조)
• 재귀는 주어진 문제의 해를 구하기 위해 동일하면서 더 작은 분제의 해를 이용하는 방법입니다.
  • 하나의 큰 문제를 해결할 수 있는 (해결하기 쉬운) 더 작은 문제로 쪼개고 결과들을 결합합니다.
  • 재귀 함수로 구현

---

2. 반복구조

• 초기화
  • 반복되는 명령문을 실행하기 전에 (한 번만) 조건 검사에 사용할 변수의 초기값을 설정합니다.
• 조건검사 (check control expression)
• 반복할 명령문 실행 (action)
• 업데이트 (loop update) : 무한 루프(infinite loop)가 되지 않게 조건이 거짓(false)이 되게 합니다.

---

---

3. 재귀적 알고리즘

• 재귀적 정의는 두 부분으로 나뉩니다.
• 하나 또는 그 이상의 기본 경우(basis case or rule)
  • 집합에 포함되어 있는 원소로 induction을 생성하기 위한 시드(seed) 역할
• 하나 또는 그 이상의 유도된 경우 (inductive case or rule)
  • 새로운 집합의 원소를 생성하기 위해 결합되는 방법

---

4. 재귀 함수(recursive function)

• 함수 내부에서 직접 혹은 간접적으로 자기 자신을 호출하는 함수
• 일반적으로 재귀적 정의를 이용해서 재귀 함수를 구현합니다.
• 따라서, 기본 부분(basis part)와 유도 부분(indcutive part)로 구성됩니다.
• 재귀적 프로그램을 작성하는 것은 반복 구조에 비해 간결하고 이해하기 쉽습니다.
  • 그러나, 재귀에 대해 익숙하지 않은 개발자들은 재귀적 프로그램이 어렵다고 느낍니다.
• 함수 호출은 프로그램 메모리 구조에서 스택을 사용합니다. 따라서 재귀 호출은 반복적인 스택의 사용을 의미하며 메모리 및 속도에서 성능저하가 발생합니다.

---

5. 반복 또는 재귀?

• 해결할 문제를 고려해서 반복이나 재귀의 방법을 선택합니다.
• 재귀는 문제 해결을 위한 알고리즘 설계가 간단하고 자연스럽습니다.
  • 추상 자료형(List, tree 등)의 알고리즘은 재귀적 구현이 간단하고 자연스러운 경우가 많습니다.
• 일반적으로, 재귀적 알고리즘은 반복(Iterative) 알고리즘보다 더 많은 메모리와 연산을 필요로 합니다.
• 입력 값 n이 커질수록 재귀 알고리즘은 반복에 비해 비효율적일 수 있습니다.

---

6. 연습문제