[알고리즘] 재귀호출

알고리즘이란?

: 계산을 통하여 해결할 수 있는 문제를 해결하는 방법

 

 

알고리즘 특징

1. 유한성
2. 명확성
3. 입력
4. 출력
5. 효과성

 

재귀호출이란?

: 함수가 자기 자신을 호출

 

수학적 귀납법 = 재귀적 증명법

: 명제 P(n)을 다음과 같이 증명하는 방법

1. N = 1일 때 성립함을 보인다.
2. P(k)가 성립한다고 가정할 때, P(k+1)이 성립함을 보인다.
3. 따라서 모든 자연수 n에 대하여 P(n)이 성립한다.

예시)

 

퀵정렬

: 재귀호출을 이용한 대표적인 정렬

예시) 4를 기준으로 작은수는 왼쪽 큰수는 오른쪽

 

 

재귀함수 디자인

재귀함수를디자인 하기 위한 세가지 단계

1. 함수의 정의를 명확히 한다.
2. 기저 조건에서 함수가 제대로 동작하게 작성한다.
3. 함수가 작은 input에 대하여 제대로 동작한다고 가정하고 함수를 완성한다.