재귀 알고리즘

재귀(Recusion) 알고리즘이란?

재귀 함수는 자기 자신을 참조하는 함수입니다. 원래의 문제를 동일한 유형의 하위 문제로 나누고 하위문제를 해결한 다음 결과와 결합합니다. 이러한 알고리즘을 분할 정복법이라합니다. 또 하위 결과를 저장하여 조회하는 알고리즘이 추가되면 동적 프로그래밍이라고 부릅니다. 이러한 재귀함수는 다음과 같은 구조를 가져야 합니다.

 

• Base Case : 재귀함수의 종료 조건으로 더 이상 문제를 쪼갤수 없을 때, 자기자신을 호출하지 않고 답이 나올 때
• Recusion Case : 복잡한 입력을 더 간단한 입력으로 분류하여 자기자신을 호출

 

재귀의 활용 예시

1. 계수(factorial) 구하기

다음은 factorial 함수는 n!을 구합니다.

 

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

}

 

2. 완전 탐색

다음은 주어진 배열에서 찾고자 하는 문자 f의 존재 여부를 반환합니다.

arr은 배열, start는 배열의 시작, len은 배열의 길이입니다.

 

bool search(char* arr, int start, int len, char f)
{
    //base case
    if (start == len )
    {
        return false;
    }
    //base case
    if (f == arr[start])
    {
        return true;
    }

    return search(arr, start + 1, len, f);

}

 

3. 이진수 구하기

printBin함수는 주어진 10진수를 2진수로 변환하여 출력합니다.

 

void printBin(int a)
{
      //base case
    if (a < 2)
    {
        printf("%d", a );;
        return;
    }
    //Recusion case
    printBin(a / 2);
    printf("%d", a % 2);

}

 

4. 1부터 n까지의 합

sumsum 함수는 1부터 n까지의 합을 구합니다.

 

int sumsum(int n)
{
    if (n == 1)
    {
        return 1;
    }
    return n + sumsum(n - 1);
}

 

5. 배열의 합

sumOfArr함수는 주어진 배열의 합을 구합니다. arr은 주어진 배열, start는 시작 index, len은 배열의 길이입니다.

 

int sumOfArr(int* arr, int start, int len)
{
    if (start == len -1)
    {
        return arr[start];
    }

    return arr[start] + sumOfArr(arr, start + 1, len);

}

 

6. 거듭제곱 구하기

powpow함수는 주어진 n의 x승을 구합니다.

 

int powpow(int n, int x)
{
    if (x == 1)
    {
        return n;
    }

    return n * powpow(n, x - 1);
}

 

7. 순열 구하기(permutation)

다음은 순열 nPr을 계산합니다.

 

int permutation(int n,int r)
{
    if (n == 0 || n == 1 || r==0)
    {
        return 1;
    }


    return n * permutation(n - 1, r - 1);
}

 

8. 모든 순열 출력하기

다음은 모든 순열을 구하는 함수입니다.

 

void swap(char* arr1, char* arr2)
{
    char temp = *arr1;
    *arr1 = *arr2;
    *arr2 = temp;

}

void permutation2(char* arr, int start, int end)
{
    if (start == end-1)
    {
        for (int i = 0; i < end; i++)
        {
            printf("%c", arr[i]);

        }
        printf("\n");
        return;
    }

    for (int i = start; i < end; i++)
    {
        swap(&arr[start], &arr[i]);
        permutation2(arr, start+1, end);
        swap(&arr [ i], &arr [ start]);
    }
}

 

재귀 알고리즘에서 주의할 점

재귀를 너무 많이 호출하다보면 Stack Overflow 현상이 발생할 수 있습니다.