재귀(Recursive)

  • 적절한 데이터를 저장하는 방법 및 구조를 공부하는 자료구조(Data Structure), 효율적인 방법으로 문제를 푸는 알고리즘(Algorithm)을 공부하기 위해서는 재귀에 대한 이해가 필요합니다.
  • 프로그래밍에서 재귀는 ‘주어진 문제를 해결하기 위하여 하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 방식’이라 정의합니다. 볼드체로 표기한 ‘하나의 함수’와 ‘자신을 다시 호출’하는 독특한 구조 덕분에 재귀는 재밌는 표현이 많습니다.
어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.
  "재귀함수가 뭔가요?"
  "잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.
  마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.
  그의 답은 대부분 옳았다고 하네.
  그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어.
    "재귀함수가 뭔가요?"
    "잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을...
  • 이처럼 재귀는 자신을 무한히 호출하는 독특한 방식이 있다고 이해하면 됩니다. (위에서 큰 따옴표가 끝나지 않았다는 것을 눈치챘다면 관찰력이 뛰어나신 겁니다.)

재귀의 구현

  • 자료구조를 공부할 때 주로 C 언어를 많이 사용합니다.

  • C 언어는 다른 언어에 비해 비교적 저수준 언어이며, 동일한 기능을 구현할 때 비교적 불편한 단점이 있습니다.

  • 하지만 다른 언어에서 제공하는 기본적인 자료구조(C++의 vector, deque, map, Python의 list, set, dict, 등…)가 없기 때문에 모든것을 새로 만들어야 하는 장점(?)이 있습니다. (물론 실제 업무/프로젝트를 진행할 때는 주어진 환경이 허락하는 한 최대한 생산성이 높은 언어를 선택하는 것이 맞습니다.)

  • 따라서 자료구조를 공부하고 내용을 정리하는 목적에 따라 C 언어로 자료구조 내용을 정리하겠습니다.

  • 먼저 C 언어에서 재귀의 기본적인 구현은 다음과 같이 작성합니다.

void Recursive(int num)
{
    // 재귀의 종료 조건
    if (num <= 0)
    {
        return;
    }

    printf("Recursive Call! %d\n", num);
    Recursive(num - 1);
}
  • 재귀에서 가장 중요한 것은 **종료 조건(탈출 조건)**을 잘 설계하는 것입니다. 재귀는 기본적으로 자기 자신을 다시 호출하는 구조이기 때문에 재귀의 탈출 조건이 없다면 무한히 실행하게 됩니다. 위 예제에서는 if (num <= 0)이 탈출 조건입니다.

    • Recursive(int num) 함수를 자세히 보면 Recursive(num - 1)와 같은 방식으로 자신을 다시 호출하는 것을 볼 수 있습니다. 따라서 어떤 임의의 양수 n이 입력되면, n회 반복적으로 호출되고 n0보다 작거나 같은 경우를 만족하면 재귀 함수가 종료됩니다.
  • 만약 아래와 같이 실행한다면…

int main()
{
    Recursive(10);

    return 0;
}
  • 실행 결과
Recursive Call! 10
Recursive Call! 9
Recursive Call! 8
Recursive Call! 7
Recursive Call! 6
Recursive Call! 5
Recursive Call! 4
Recursive Call! 3
Recursive Call! 2
Recursive Call! 1
  • 이처럼 10회 호출되고 종료됩니다.

재귀의 실제 사례

  • 보통 재귀를 처음 공부할 때 첫 번째로 접하는 예제가 팩토리얼(Factorial)피보나치 수열(Fibonacci Sequence) 입니다.
  • 그렇다면 왜 재귀를 사용할까요? 재귀는 수학적인 표현을 프로그램으로 그대로 옮길 수 있다는 장점이 있습니다. 어떤 사례가 있는지 살펴볼까요?

팩토리얼(Factorial)

  • 팩토리얼은 어떤 임의의 자연수 n1보다 크거나 같을 때 아래와 같이 정의합니다.

$$ n! = \prod_{i=0}^{n}(n-i) = n(n-1)(n-2) … 3 \cdot 2 \cdot 1 $$

  • 위 수식을 글로 표현하면 1부터 n까지의 자연수를 모두 곱한 값을 의미합니다.
  • 여기서 한 가지 특이한 점을 발견할 수 있습니다. \(n! = n(n-1)(n-2) … 3 \cdot 2 \cdot 1\) 이라면 \((n-1)! = (n-1)(n-2)(n-3) … 3 \cdot 2 \cdot 1\) 이기 때문에, 이를 다시 \(n! = n \cdot (n-1)!\)로 변환할 수 있기 때문입니다.
  • 재귀의 형태가 보이나요? 재귀의 탈출 조건은 n == 1 인 경우입니다. \(1! = 1\) 이기 때문입니다. C 언어로 구현한 팩토리얼 함수는 다음과 같습니다. (참고로 \(0!\)도 \(1\) 입니다.)
int Factorial(int n)
{
    if (n == 1)
    {
        return 1;
    }
    else
    {
        return n * Factorial(n - 1);
    }
}
  • 팩토리얼 수식과 프로그래밍으로 구현한 로직이 동일함을 이해하는 것이 중요합니다.

피보나치 수열

  • 피보나치 수열은 피보나치 수을 나열한 수열입니다. 피보나치 수열은 다음과 같습니다.

$$ 0, 1, 1, 2, 3, 5, 8, 13, 21, … $$

  • 아무런 관계 없는 숫자들의 나열 같지만, 피보나치 수열은 다음과 같은 특별한 관계가 존재합니다.

$$ F_{0} = 0, F_{1} = 1 $$

$$ F_{n} = F_{n-1} + F_{n-2} $$

  • 즉 임의의 n 번째 피보나치 수를 계산하기 위해서는 n-1 번째의 피보나치 수와 n-2 번째의 피보나치 수를 계산하고 이를 더하면 됩니다.
  • 피보나치 수열을 재귀적으로 구현하기 위해서 필요한 종료 조건은 n == 0 일 때와 n == 1 인 경우입니다. 각각 01을 반환하면 됩니다. 이를 C 언어로 구현하면 다음과 같습니다.
int Fibonacci(int n)
{
    if (n == 1)
    {
        return 0;
    }
    else if (n == 2)
    {
        return 1;
    }
    else
    {
        return Fibonacci(n - 1) + Fibonacci(n - 2);
    }
}
  • 정말 간단하죠? 팩토리얼과 피보나치 수열 모두 수학적으로 정의한 수식을 거의 그대로 코드로 옮겼을 뿐입니다. 만약 피보나치 수열을 반복문 형태로 계산한다면 재귀적인 형태보다 복잡한 구조를 갖는 것을 예상할 수 있습니다.

재귀적 구현의 단점

  • 재귀는 어떤 함수가 자기 자신을 다시 호출하는 구조를 갖는다고 정리하였습니다. 그렇다면 프로그래밍에서 재귀의 단점은 어떤 것일까요?
    • 재귀는 재귀의 탈출 조건을 만나기 전 까지, 반복적으로 실행되는 함수와 관련된 데이터가 메모리 영역에 존재합니다. 함수의 호출이 종료되지 않았기 때문에 호출된 함수 마다 메모리에 새롭게 올라가는 구조인 셈이죠. 따라서 시스템 메모리가 허용하는 범위 이상의 재귀를 호출하게 되면, 시스템이 메모리 부족으로 이상동작을 하는 경우가 발생합니다.
    • 또한, 피보나치 수열에서 재귀의 비효율적인 계산을 확인할 수 있습니다. 피보나치 수열 프로그램은 다음과 같은 형태로 함수를 반환합니다. return Fibonacci(n - 1) + Fibonacci(n - 2); 으로 작성된 코드는 Fibonacci(n - 1) 함수가 먼저 호출되고, 이는 종료 조건을 만족할 때 까지 Fibonacci(n - 1)Fibonacci(n - 2) 두 가지 경우로 분기됩니다.
    • 따라서 분기된 재귀적 함수가 종료 조건을 만족할 때 까지 동일한 함수를 반복하는 문제가 있습니다. 만약 19번째 피보나치 수를 계산하기 위해 3번째, 4번째, 5번째 피보나치 수를 계산하는 함수는 몇 번 호출되었을 까요? 바로 4180, 2583, 1596번 호출됩니다. 이처럼 재귀는 계산적인 비효율성을 갖고 있습니다.
  • 재귀의 단점을 정리해보면 비효율적인 메모리 구조, 비효율적인 계산 방식이 있습니다. 하지만 수학적 모델을 코드로 그대로 옮기는 것이 가능하기 때문에 복잡한 문제를 쉬운 방법으로 해결할 수 있는 장점이 있습니다.