0x00 알고리즘 설명

사고 방식

수학적 귀납법에 의해서 이해를 해야한다. 절차 지향적 사고와 귀납적 사고가 존재한다.

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

• 절차 지향적 사고

  순서대로 흐름대로 확인하는 사고

  

• 귀납적 사고

  func(1)이 1을 출력한다.

  func(k)가 k, k-1, k-2, …, 1을 출력한다.

  func(k+1)가 k+1, k, k-1, …, 1을 출력한다.

재귀 함수의 조건

• 특정 입력에 대해서는 자기 자신을 호출하기 않고 종료가 되어야 함.
• 모든 입력은 base condition으로 수렴해야 한다.
• 아니면 끝이 나지 않는다.

재귀 함수의 특징

• 어디까지 계산하고 넘겨줄지 명확해야 한다.
• 재귀 함수는 반복문으로도 구현할 수 있다. → 사용해야 하는 목적이 정확해야 손해를 보지 않는다. 일반적으로 재귀는 메모리와 시간을 손해보기 때문이다.
• 여러번 호출하게 되면 되게 비효율적일 수 있다. → 이런 경우는 memoization을 하는 것이 좋다. (보통의 경우 같은 함수를 호출하는 경우가 많기 때문이다. 그렇게 되면 스택 영역에 계속 누적이 된다.)
• DP와 잘 비교해서 할 수 있다.

연습 문제

01. 거듭 제곱

• 코드