자료구조
[알고리즘] 재귀호출
홍시_코딩기록
2024. 4. 25. 22:44
알고리즘이란?
: 계산을 통하여 해결할 수 있는 문제를 해결하는 방법
알고리즘 특징
- 유한성
- 명확성
- 입력
- 출력
- 효과성
재귀호출이란?
: 함수가 자기 자신을 호출
수학적 귀납법 = 재귀적 증명법
: 명제 P(n)을 다음과 같이 증명하는 방법
- N = 1일 때 성립함을 보인다.
- P(k)가 성립한다고 가정할 때, P(k+1)이 성립함을 보인다.
- 따라서 모든 자연수 n에 대하여 P(n)이 성립한다.
예시)
퀵정렬
: 재귀호출을 이용한 대표적인 정렬
예시) 4를 기준으로 작은수는 왼쪽 큰수는 오른쪽
재귀함수 디자인
재귀함수를디자인 하기 위한 세가지 단계
- 함수의 정의를 명확히 한다.
- 기저 조건에서 함수가 제대로 동작하게 작성한다.
- 함수가 작은 input에 대하여 제대로 동작한다고 가정하고 함수를 완성한다.