[알고리즘] 재귀 함수(Recursive Function)

개념

재귀 함수는 직간접적으로 자기 자신을 호출하는 함수이다. 재귀 함수에는 중요한 세 가지 특징이 있다.

1. 재귀 함수는 종료 조건이 있어야 한다.
2. 재귀 함수는 종료 조건에 도달하게 상태를 변경해야 한다.
3. 재귀 함수는 자기 자신을 호출해야 한다.

계승 함수(Factorial Function)

팩토리얼 함수 factorial(n)은 일반적으로 factorial(n) = n*factorial(n-1)을 만족한다. 따라서 factorial 함수를 재귀적으로 정의하면 다음과 같다.

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

배열의 합

배열 A가 n개의 정수를 갖는 배열일 때, A의 합은 n=1 일 때 A[0]이고 그렇지 않으면 A의 n-1개의 정수와 A의 마지막 원소의 합이 같다. 따라서 재귀적으로 정의하면 다음과 같다.

template <class RandomIt>
auto linear_sum(RandomIt first, RandomIt last)
{
    if (first == last) return 0;
    return *first + linear_sum(first+1,last);
}

배열의 반전

배열 A의 n개의 원소를 반전하려면 첫 번째 원소는 마지막 원소가 되고 두번째 원소는 뒤에서 두 번째 원소가 된다. 즉 첫 번째와 마지막 원소를 교환학 재귀적으로 남은 원소들을 바꾸면 전체를 반전시킬 수 있다.

template <class RandomIt>
void reverse_array(RandomIt first, RandomIt last)
{
	if (first<last)
    {
    	auto temp = *(last-1);
        *(last-1) = *first;
        *first = temp;
        reverse_array(first+1, last-1);
    }
}

이진 재귀(Binary Recursion)

알고리즘이 2개의 재귀 호출을 할 때 이를 이진 재귀(binary recursion)이라고 한다. 배열의 합을 이진 재귀 함수로 구하면 다음과 같다.

template <class RandomIt>
auto binary_sum(RandomIt first, RandomIt last)
{
    if (first+1 == last) return *first;
    return binary_sum(first,first+(last-first)/2) + binary_sum(first+(last-first)/2, last);
}

피보나치 수열(Fibonacci Sequence)

피보나치 수열은 다음의 정의를 만족한다.

$$F_{0} = 0$$

$$F_{1} = 1$$

$$F_{i} = F{i-1}+F_{i-2}$$

이를 이진 재귀를 통해 구현하면 다음과 같다.

int binary_fib(int n)
{
    if (n <= 1) return n;
    return binary_fib(n-1) + binary_fib(n-2);
}

그러나 이진 재귀를 사용하여 n번째 피보나치 수를 구하려면 이진 재귀함수를 그 피보나치 수만큼 호출해야 되므로 큰 n에 대해 비효율적이다.

void fibonacci(int* arr, int n)
{
    if (n <= 1)
    {
        arr[0] = n, arr[1] = 0;
    }
    else
    {
        fibonacci(arr, n-1);
        int temp = arr[0];
        arr[0] += arr[1];
        arr[1] = temp;
    }
}

int linear_fib(int n)
{
    int result[2];
    fibonacci(result, n);
    return result[0];
}

선형 재귀를 이용하면 n번째 피보나치 수를 계산할 때 피보나치 함수를 n번 호출하기 때문에 더욱 효율적이다.