1장. 재귀호출

실습_1. 재귀호출

목표

• 알고리즘이란?
• 재귀호출
• 퀵정렬

알고리즘이란

• 문제를 해결하는 방법
• 계산을 통하여 해결할 수 있는 문제를 해결하는 방법(with 컴퓨터)
• 5가지 성질
  • 유한성
  • 명확성
  • 효과성
  • 입력
  • 출력

재귀호출

• 함수가 자기 자신을 호출
• 재귀적 계산법(값)
• 기저조건(base condition)이 있어야 한다

수학적 귀납법

• 재귀적 증명법(명제)
• 명제 P(n)을 다음과 같이 증명하는 방법
  1. N = 1 일 때 성립함을 보인다
  2. P(k)가 성립한다고 가정할 때, P(k+1)이 성립함을 보인다
  3. 따라서 모든 자연수 n에 대하여 P(n)이 성립한다

퀵정렬(Quick Sort)

• 재귀함수을 이용한 대표적인 정렬

재귀함수 디자인

• 재귀함수를 디자인 하기 위한 세가지 단계
  1. 함수의 정의를 명확히 한다
  2. 기저 조건(Base condition)에서 함수가 제대로 동작하게 작성한다
  3. 함수가 작은 input에 대하여 제대로 동작한다고 가정하고 함수를 완성한다