재귀함수

 

수학적 귀납법 : 명제 P(n)이 모든 자연수 n에서 성립하는 것을 보이는 방법이다.

 

증명순서

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

2) P(k)가 성립한다고 가정한 후 P(k+1)이 성립함을 보인다.

3) 2)번까지 보였으면 모든 자연수 n에 대하여 P(n)이 성립한다.

 

어떤 명제 A가

k=1일때 성립하고

k=n일때 성립한다고 가정했을때

k=n+1일때 성립한다면

귀납적 방법에 의해 명제 A는 모든 자연수에서 성립한다.

 

 

 

재귀함수 디자인을 위한 3가지 절차

 

1. 함수의 역할을 말로 정확하게 정의한다.

 

2. 기저조건(Base Condition)에서 함수가 제대로 동작함을 보인다.

 

3. 함수가 작은 input에 대하여 제대로 동작한다고 가정하고 함수를 완성한다.

 

4. 함수를 완성한 후 기저조건으로 수렴함을 보인다.

 

 

 

재귀함수를 이용하여 N중 for을 대체할 수 있다. (이때 시간복잡도는 아마 같다.)

 

기저조건은 수납적 귀납법에서 k=1일때 성립하는 것을 보이는 것과 같다.

 

 

 

재귀호출을 이용한 BF구현 (이 방법은 중요한 테크닉이므로 암기하라고 한다.)

각 자리가 1부터 n자리의 수 중 하나인 n자리 수의 모든 경우의 수를 출력하는 코드이다.

 

void getresult(int current, int n, int result[]){

//current : 현재 인덱스, n : 출력할 횟수, result[] : n개의 결과를 저장할 배열

 

기저조건 ↓

    if(current>=n){ //current와 n이 같아지면 배열이 가득찬 상태이므로 출력한다.

 

       for(int i=0;i<n;i++) printf("%d",result);

 

기저조건이 아닌 조건 ↓       

    }else{ //current가 n보다 작다면 배열이 가득찬 상태가 아니므로 배열을 계속 채운다.

 

       for(int i=1 ; i<=n ; i++){

            

           if(isNotCotaining(result,i){ // result 배열에 i가 없다면 실행한다.

                

               result[current]=i;

               getresult(current+1,n,result); // current+1번 째 for문을 구현하기 위해서 재귀함수를 사용한다.  

               result[current]=0;

//current번 째 인덱스의 결과가 i일 때의 값을 모두 조사하였으므로 다른 인덱스에서 i를 사용할 수 있도록 초기화한다.

 

           }

            

       }

        

    }

 

}

 

재귀함수가 종료될 조건은 current==n이거나 for문이 n까지 모두 탐색했을 때이다.