재귀(Recursion)

이 포스트는 국민대학교 소프트웨어학부 '알고리즘' 강의를 듣고 요약하는 포스트입니다. 원하시는 정보가 없을 수도 있습니다. 이 점 유의 바랍니다. 오류 지적은 매우 환영합니다!

---

수학에서 얘기하는 재귀

어떤 함수를 정의하는데 자기 자신의 함수를 이용하는 것을 재귀라고 합니다. 재귀를 흔히 점화식의 형태로 나타낼 수 있습니다. 예를 들어 자연수 n에 대한 함수 f(n) = n! 가 있다고 합시다. 이를 아래와 같이 정의할 수 있습니다.

f(n) = n! in recursive description

이 정의를 보면 n! 를 정의하는데 다시 (n - 1)!로 정의합니다. n > 0일 때 식을 풀어써봅시다.

n * (n - 1)! = n * (n - 1) * (n - 2)! = n * (n - 1) * (n - 2) * (n - 3)! =...

= n * (n - 1) * (n -2) * (n - 3) *... * 3 * 2 * 1 * (1 - 1)!

= n * (n - 1) * (n -2) * (n - 3) *... * 3 * 2 * 1 * 1

n - 1 = 0 일 때까지 식은 계속 풀어쓸 수 있고 0! 은 1로 정의했기 때문에 1로 바꿔 쓸 수 있었습니다. 이처럼 계속 식이 풀어지는 과정이 recursive step, n = 0이 제일 단순하게 계산할 수 있는 경우인 base case라고 부릅니다.

프로그래밍에서 얘기하는 재귀

수학에서 얘기하는 재귀와 동일합니다. 재귀를 구현할 때 recursive step과 base case를 생각하며 구현하게 됩니다. 팩토리얼 함수를 c++ 언어로 표현해보면 아래와 같습니다.

int factorial(int n)    // 계산 값이 정수 표현 범위 안에 들어온다는 가정
{
    if (n == 0) { return 1; }
    else
    {
        int result = n * factorial(n - 1);
        return result;
    }
}

이처럼 if (n == 0)으로 base case에 대해 check 하고 base case에 도달하지 않은 경우 계속 recursive 하게 함수를 호출하는 방법으로 구현할 수 있습니다. 이게 팩토리얼을 재귀적으로 구현하는 방법입니다.

지금같이 재귀적으로 함수를 호출하는 곳이 한 군데만 있는 것을 Unary recursion이라고 칭합니다. 만약 두 군데에서 호출하면 Binary recursion이라 부르고 세 군데 이상에서 호출하면 Multiple recursion이라 합니다.

 

재귀는 Divide & Conquer(분할 정복 기법), Dynamic Programming(동적 프로그래밍) 등의 문제에서도 많이 사용됩니다. 그리고 Merge sort(병합 정렬), Quick sort(퀵 정렬)에서도 사용됩니다. 이처럼 다양한 상황에서 재귀가 사용됩니다. 재밌는 점은 재귀는 반복문으로 바꿔서 표현할 수 있다는 것입니다.

재귀와 반복문

위에서 작성한 팩토리얼 코드는 아래처럼 반복문으로 바꿀 수 있습니다.

int factorial(n)    // 계산 결과가 정수 표현 범위 안에 들어온다는 가정
{
    int result = 1;
    for (int i = 1; i <= n; i++) { result *= i; }    // 함수를 호출하는 부분이 사라졌다!
    return result;
}

재귀 사용 시 주의 사항

반복문으로도 해결할 수 있는 문제들도 많지만 재귀로 인해 쉽게 풀리는 문제들도 많이 있습니다. 그렇다고 무턱대고 재귀를 마음껏 사용하기에는 주의해야 할 점이 있습니다. 바로 stack overflow입니다(질문 사이트 아닙니다 ㅡㅡ). 재귀를 호출할 때마다 현재 자신의 activation record를 call stack에 push 하는 과정을 거칩니다. 좀 더 자세히 설명드리겠습니다.

재귀적으로 작성한 팩토리얼 코드를 생각해봅시다. 처음에 n이 3으로 들어왔다고 하면 base case가 아니므로 자기 자신을 호출할 것입니다. 재귀적으로 호출된 함수에서의 n은 2가 됩니다. 3이라는 값은 어딘가에 저장해야 나중에 n = 2일 때의 결과와 곱할 수 있을 것입니다.

변수만 저장해야 하는 것은 아닙니다. n = 2일 때에 함수가 끝나면 n = 3일 때의 팩토리얼 함수로 return 되어야 합니다. 하지만 n = 3일 때의 함수는 자신을 호출한 main 함수로 return 되어야 합니다. 재귀로 들어갈 때마다 돌아가야 할 곳이 달라지기 때문에 어디로 return 해야 하는지도 저장해야 합니다. 따라서 재귀로 함수를 호출하고 넘어가기 전에 현재 함수의 정보를 activation record라는 형태로 만듭니다. 그리고 이를 call stack에 저장해서 현재 자신의 상태를 저장합니다. 그림으로 간단하게 나타내면 아래와 같습니다.(이에 대한 정확한 설명은 '운영체제' 분야를 배우시면 됩니다...)

fibonacci 함수가 호출될 때마다 쌓인 call stack

다른 자료 구조들도 많은데 stack을 사용하는 이유는 stack의 LIFO(Last In First Out) 구조가 재귀 함수가 호출되고 반환되는 과정과 동일하기 때문입니다. 이러한 특징으로 인해 재귀 문제를 풀 때 함수를 재귀적으로 호출하지 않고 스택을 직접 만들어 그 스택에 필요한 값들을 저장해가며 풀어가는 사람들도 있습니다. 피보나치 함수가 호출되는 과정을 그림으로 봅시다.

flow of fibonacci(3)

call stack 그림과 함수가 호출되는 과정의 그림을 같이 보면, 리턴되는 순서가 stack에서 pop 되는 순서와 동일한 것을 알 수 있습니다. 따라서 stack의 구조를 사용합니다. 그러면 stack의 문제점을 재귀가 그대로 가지게 됩니다. stack은 주로 크기가 정해져 있습니다. 그렇기 때문에 activation record의 수, 즉 함수 호출 횟수가 stack의 크기를 넘어서면 overflow가 발생하게 됩니다. 그렇기 때문에 재귀로 풀기 전에 overflow가 날 만큼의 호출을 하게 될지 어떨지 생각해보면 좋습니다. 예를 들어(사용 환경마다 다르겠지만) fibonacci(10000000)을 호출하면 call stack에 10**7개만큼의 activation record를 쌓아야 하는데 이를 다 쌓기 전에 stack overflow가 발생할 것입니다.