2. 재귀 함수

저번 글까지는 맛보기였고 지금부터가 진짜입니다.

 

이번 시간에 진행할 내용은 재귀함수 입니다.

 

재귀함수는 알고리즘에 있어서 매우매우 중요합니다.

여러 알고리즘들이 재귀함수를 베이스로 가지고 있기도 하고, 재귀 함수 대한 이해 없이는 진행할 수 없는 알고리즘도 수없이 많습니다.

 

 

재귀함수는 자기 자신을 호출하는 함수입니다.

반복문을 사용하는 코드는 항상 재귀함수를 통해 구현이 가능합니다.(물론 그 반대도 가능합니다.)

 

우리가 어떤 문제를 재귀함수로 푼다는 것은, 귀납적인 방법으로 문제를 푼다는 뜻입니다.

 

수학적 귀납법을 생각해보면

1. 기본 가정

2. 귀납 가정

3. 귀납 증명

이 세가지 단계를 통해 우리는 귀납적으로 증명할 수 있습니다.

 

예를 들어,

\( 1+3+5+ ... + (2n-1) = n^{2} \) 이 임의의 자연수 \( n \)에 대하여 성립한다는 사실을 귀납적으로 증명할 수 있습니다.

1. 기본 가정

\( n = 1 \) 인 경우, \( 1 = 1^{2} \) 은 참이다.

 

2. 귀납 가정

\( 1+3+5+ ... + (2n-1) = n^{2} \)은 어떤 자연수 \( n \)에 대하여 성립한다고 가정하자.

 

3. 귀납 증명

\( 1+3+5+ ... + (2n-1) = n^{2} \) 양변에 \( 2n+1 \) 을 더하면, 다음과 같다.

\( 1+3+5+ ... + (2n-1)+(2n+1) = n^{2} + 2n + 1  = (n+1)^{2} \)

그러므로 \( n+1 \)에 대하여 명제가 성립한다.

 

임의의 자연수 \( n \)에 대하여, 명제가 성립함을 알 수 있다.

 

 

재귀함수도 마찬가지 입니다.

1. 기본 가정에서 재귀함수는 종료되어야 합니다. -> 기본 가정은 재귀 함수의 정지조건이 됩니다.

2. 모든 입력은 기본 가정으로 수렴해야 합니다.

 

아래 코드는 팩토리얼에 대한 예제입니다.

int factorial(int n)
{
    if(n == 1 || n == 0) return 1;
    return n * factorial(n-1);
}

0 이상의 정수 n이 함수의 파라미터로 들어오게됩니다.

모든 입력은 재귀 함수의 정지조건의 향해 수렴합니다.

 

n = 4 일때, 

factorial(4)를 부르게 되고,

factorial(4)는 factorial(3)을 부르게 되고,

factorial(3)은 factorial(2)를 부르게 되고,

factorial(1)은 factorial(1)을 불러 재귀함수를 정지시킵니다.

www.acmicpc.net/problem/10872

10872번: 팩토리얼

 

 

 

 

www.acmicpc.net/problem/10974

10974번: 모든 순열

이 문제를 보면 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하라고 합니다.

3을 입력받았을 떄

1 2 3

1 3 2

2 1 3

2 3 1

3 1 2

3 2 1

이렇게 사전순으로 출력해야합니다.

 

일단 N = 3 인 상황으로 고정하여 생각해 봅시다.

위 처럼 출력하려면

 

for(int i=1;i<=3;i++)
{
    for(int j=1;j<=3;j++)
    {
        for(int k=1;k<=3;k++)
        {
            if(i != j && j != k && i != k)
                printf("%d %d %d\n", i, j, k);
        }
    }
}

사전순으로 빠짐없이 출력하기 위해 이렇게 3중 for문을 사용해야합니다.

 

이제 N = 4 라고 해봅시다.

어떻게 구현할 수 있을까요?

 

for(int i=1;i<=4;i++)
{
    for(int j=1;j<=4;j++)
    {
        for(int k=1;k<=4;k++)
        {
            for(int l=1;l<=4;l++)
                if(i != j && i != k && i != l && j != k && j != l && k != l)
                    cout << i << ' ' << j << ' ' << k << ' ' << l << endl;
        }
    }
}

N = 3 인 경우와 비슷하게 4중 for문을 이용하면 구현할 수 있습니다.

 

이 방법으로 N = 8 인 경우까지 생각하면 8중 for문까지 만들어야 합니다.

 

 

 

하지만 재귀를 이용하여 N중 for문을 만든다면 위 문제를 쉽게 해결할 수 있습니다.

 

#include <bits/stdc++.h>
using namespace std;
 
int cnt;
void recursive(int pos, int n)
{
    if(pos == n)
    {
        cnt++;
        return;
    }
    for(int i=0;i<n;i++)
        recursive(pos+1, n);
}
 
int main()
{
    int n;
    cin >> n;    
    recursive(0, n);
    cout << cnt;
 
    return 0;
}

위 코드를 실행하면 출력되는 cnt 값이 얼마가 될까요?

\( n^{n} \) 이 출력됩니다.

pos 는 해당 함수를 호출했을 때의 깊이를 의미합니다. 그래서 깊이가 n 이하일 때는 for문 작업을 하고, 깊이가 n이 되었을 때 함수를 멈추면 n중 for문과 같은 작업을 합니다.

 

\( n = 3 \) 이라고 하면, 3중 for문에서 가장 안쪽에 있는 for문에 cnt++ 연산만 있는 것과 같습니다.

 

이제 이걸 이용해서 모든 순열 문제를 해결하면 됩니다...!

 

#include <bits/stdc++.h>
using namespace std;
int ans[9];
bool check[9];
 
void recursive(int pos, int n)
{
    if(pos == n)
    {
        for(int i=0;i<n;i++)
            printf("%d ", ans[i]);
        printf("\n");
        return;
    }
    for(int i=1;i<=n;i++)
    {
        if(check[i] == false)
        {
            check[i] = true;
            ans[pos] = i;
            recursive(pos+1, n);
            check[i] = false;
        }
    }
}
 
int main()
{
    int n;
    scanf("%d", &n);
    recursive(0, n);
    return 0;
}

코드에 대해 설명을 하면, 앞선 코드 처럼 N중 for문을 만들어 놓은 상태에서 현재 재귀 함수 깊이 = 몇번째 자리 수 인가? 와 같습니다.

 

그래서 결과를 저장하는 ans 배열 pos 자리에 숫자를 넣는 작업을 합니다.

하지만 이미 선택된 수는 다시 선택하면 안되므로 check 배열을 통해 해당 수가 선택되었는지를 먼저 판단합니다.

(false -> 선택되지 않음, true -> 선택됨.)

 

선택되지 않았으면 true로 만들어 선택해주고 ans 배열 pos번째 자리에 해당 숫자를 넣습니다.

그리고 재귀 함수를 진행합니다.

 

그러다 pos 값이 n과 같아지면 결과를 저장한 배열을 모두 출력해줍니다.

 

재귀함수가 다시 돌아왔을 때는 다시 선택을 해제해주어 다른 숫자를 pos번째 자리에 넣을 수 있도록 해줍니다.