[자료구조 스터디] 4. 재귀와 수학적 귀납법

[자료구조 스터디] 4. 재귀와 수학적 귀납법

1. 재귀 알고리즘과 수학적 귀납법
2. 재귀 알고리즘의 구성요소

---

1. 재귀 알고리즘과 수학적 귀납법

-재귀 알고리즘과 수학적 귀납법은 깊은 관련이 있다.

-수학적 귀납법: 자신보다 작은 문제에 대한 결론이 옳다고 생각하고, 자신과 이 작은 문제 간의 관계를 통해, 자신에 대한 결론도 옳음을 보이는 것.

-재귀 알고리즘이 자신보다 작은 문제를 호출하는 것=수학적 귀납법에서 자신보다 작은 문제에 대해 결론이 옳다고 가정하는 것. 

---

 

2. 재귀 알고리즘의 구성요소

(1) 경계 조건(Base Condition)(혹은 종료 조건): 재귀 호출이 반복되다, 마침내 끝내게 하는 조건

(2) 재귀 호출

(3) 관계: 닮음꼴 작은 문제(들)와 본 문제 간의 관계를 나타내는 부분

 

*하노이 탑 문제에서 경계 조건은 n(원판수)=0이다. 옮겨야 할 원판 수가 0이 되면 더이상 재귀 호출이 일어나지 않는다.