재귀의 정의

1. 하나의 함수에서 자기 자신을 다시 호출해 작업을 수행하는 알고리즘
2. 기저사례(종료 조건)이 반드시 존재해야한다.

형태

1. 기저사례(종료 조건)
2. 처리해야 하는 로직
3. 자기자신(재귀)의 호출

수학적 귀납법

• 1번 도미노가 쓰러진다. k번 도미노가 쓰러진면 k+1번 도미노도 쓰러진다.

절차지향적인 사고와 귀납적 사고

• 아래의 코드를 해석할 때 방법에 따라 각각 다음과 같이 사고한다.

void func1(int n) {
	if(n == 0) return;
	cout << n << ' ';
	func1(n-1);
}

• 절차지향적 사고

  1. 3 출력
  2. func1(2) 호출
  3. 2 출력
  4. func1(1) 호출
  5. 1 출력
  6. func1(0) 호출

• 귀납적 사고

  1. func1(1)이 1을 출력한다.
  2. func1(k)가 k k-1 k-2 ... 1을 출력하면
  3. func1(k+1)은 k+1 k k-1 ...1을 출력한다.
  4. func1(k+1)을 호출하면 k+1 다음에 내부적으로 func1(k)를 호출하기 때문에

재귀 함수의 조건

• 특정 입력에 대해서는 자기 자신을 호출하지 않고 종료 되어야 함(Base Condition) 모든 입력은 base condition으로 수렴해야 함.

void func1(int n) {
	if(n == 0) return;
	cout << n << ' ';
	func1(n-1);
}

위의 코드에서 if (n == 0) return; 이 base condition임