알고리즘 study -10-

<재귀함수>

-> 자기 자신을 호출하는 함수

#include <stdio.h>

int getFactorial(int n){
  if(n == 0){  
    return 1;  // 무한 루프가 돌지 않게 끝나는 조건이 있어야 함
  }
  else{
    return n * getFactorial(n-1);
  }
}


int main() {

  int a = 5;
  
  int factorialA = getFactorial(a);
  
  printf("%d\n", factorialA);

  return 0;
}

---

<값의 계산을 위한 두 가지 방법>

• 순차적 계산법
• 귀납적 계산법 : 구하려고 하는 값을 f(x)라 가정 / f(x)를 구하기 위해 다시 f(x)를 사용한다

ex> n! = n * (n-1)! -->> 팩토리얼 정의!
0! = 1

---

n^m 을 귀납적으로 계산하여라
-> n^m = n * n^(m-1), n^0 = 1

귀납적 계산법이 제대로 된 값을 반환하는 이유
-->> 1) 수많은 가정을 하다가 2) 맨 끝에는 정확한 값이 있기 때문이다

ex> 5^4 = 5^3 5 -->> 5^3이 5를 세 번 곱한 것이라 가정
5^3 = 5^2 5 -->> 이어서 5^2이 5를 두 번 곱한 것이라 가정
5^2 = 5^1 5
5^1 = 5^0 5
5^0 = 1 --> 앞의 가정들 다시 차례대로 계산

---

<수학적 귀납법>

명제 P(n)이 모든 자연수 n에 대해 성립함을 보이는 것

• 증명순서

1. P(1)이 참임을 보인다

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

   ---

<재귀함수 디자인 절차> (꼭 지키자)

1) 함수의 역할을 말로 정확하게 정의한다
2) 기저조건(Base Condition)에서 함수가 제대로 동작함을 보인다
= 제일 단순한 경우
3) 함수가 (작은 input에 대하여)제대로 동작한다고 가정하고 함수를 완성한다

---