[고급-3] 재귀함수의 활용

학습목표

-수학적 접근을 통해 해결되는 문제를 수학적 귀납법 설계를 통해 문제를 해결하는 방법을 다양하게 제시할 수 있다.

-경우의 수에 대한 문제의 계산량을 감소하는 방법의 필요성과 문제해결 전략을 설계할 수 있다.

-비선형적인 구조를 선형적인 구조로 변환하는 방법을 이해하고 이를 실제 문제에 적용할 수 있다.

1. 재귀함수 심화1

<타일 채우기>

2*1, 2*2크기의 타일을 2*n크기의 직사각형 모양 틀에 배치하는 문제. 값이 커서 주어지는 수 m으로 나눈 나머지 출력.

{첫번째 방법. f(n)=1번 칸부터 n번째 칸까지 조건에 맞도록 채운 경우의 수}

f(n) = f(n-1) + f(n-2) + f(n-2)

int f(int k){
    if(k<=1) return 1;
    else return f(k-1)+2*f(k-2);
}

{두번째 방법. 짝수인가 홀수인가}

>짝수일때

(1) 반으로 쪼갠다.

(2) f(n/2)를 알고 있다고 가정하고 한것이기 때문에 성립이 된다.

(3) 가운데가 2*2 혹은 1*2 2개로 이루어져 있다면, f(n/2-1)을 두번 더해줘야하기 때문에 3가지의 경우의 수를 더해준다.

>홀수일때

(1)f(n)=f(n/2)+(f/2+1)

(2)짝수일때와 마찬가지로 두가지의 경우를 더 생각해줘야 한다.

long long int f(int k){
    if(k<=1) return 1%n;
    else if(k%2) return (f(k/2)*f(k/2+1)+2*f(k/2)*f(k/2-1))%n;
    else return (f(k/2)*f(k/2)+2*f(k/2-1)*f(k/2-1))%m;
}

2. 재귀함수 심화 2

<노드의 길이>

labeling된 완전 이진트리에서 두 노드간의 거리를 구하는 프로그램.

**잠깐

labeling된 완전 이진트리에서 

>부모노드 : n/2

>왼쪽 자식노드 : n*2

>오른쪽 자식 노드 : n*2+1

**

두개의 현재 노드 n, k에서 큰 값을 부모노드로 올리면서 만나는 지점을 찾는다.

int f(int a, int b){
    if(a==b) return 0;
    if(b>a) return f(a,b/2)+1;
    if(a>b) return f(a/2,b)+1;
}