[ Algorithm ] 재귀

 

 

도입

이 글은 재귀 알고리즘에 대한 설명을 담고 있습니다. 프로그래밍 언어를 공부하다보면, 함수 혹은 메소드에 대해 배우면서 접할 수 있는 알고리즘이 바로 재귀입니다. 사실 재귀는 반복문을 실행하는 것보다 메모리 측면에서 비효율적이라는 의견도 존재하지만 (함수를 종료시키지 않은 채로 계속 실행하기에) 잘 사용하면 문제를 다른 시선으로 바라볼 수 있으며, 복잡한 문제 상황을 간결한 코드로 해결할 수도 있는 알고리즘입니다. 재귀 알고리즘을 학습하고 여러 문제 상황에 대응할 수 있는 능력을 기르는 것이 이 글의 목적입니다.

본 글은 C를 기반으로 작성되었습니다.

 

접근

https://www.acmicpc.net/problem/4779

4779번: 칸토어 집합

다음과 같은 문제를 예시로 들어보자.

 

순차적인 모양이 아니다

기본적인 반복문으로 출력하기엔 어려워 보이고, 큰 틀을 잡아야 출력할 수 있는 모양처럼 보인다. 

가운데 문자열을 공백으로 바꾸는 작업을 선마다 계속 진행하면서, 두 선으로 나누고 그 선을 두 선으로 나누고... 큰 선 하나를 작은 선으로 깊게 나누는 원리이다. 이 문제를 재귀 원리를 학습하고 풀이해보자.

 

재귀란?

재귀 (Recursion) 는 자기 자신을 다시 호출하는 함수 알고리즘을 말한다. 함수 정의부에서 자기 자신을 호출하는 문장이 포함되어 있다. 함수를 호출하면 그 함수를 실행하면서 그 함수를 호출하고 그 함수를 실행하면서 그 함수를 호출하고.. 의 실행이 반복되게 된다.

 

void func1() {
	// ...
    func1(); // 자기 자신 호출
}

그런데, 이렇게 단순히 자기 자신을 호출하기만 하면 문제가 발생한다. 

무한 호출

한 함수를 실행하던 도중 다른 함수를 실행하면, 실행한 함수가 종료되기 전까지 기존에 실행하던 함수는 종료되지 않는다. 자기 자신을 호출하는 함수이기 때문에 무한루프가 걸릴 수 있다는 문제점이 있다.

결국 빠져나갈 수 없다.

재귀 함수를 올바르게 사용하기 위해선, base condition 을 확실히 구성해야 한다.

 

base condition 이란 자기 자신을 호출하지 않고 종료되는 조건을 말한다. 재귀 함수가 계속 실행되다가 base condition 을 충족하는 조건으로 수렴해야 올바르게 종료될 수 있다.

 

base condition을 충족하는 조건으로 다가가려면 값이 변경된다던가 등의 변경점이 있어야 하는데, ( 5, 4, 3, 2, 1, 0 (종료) ) 주로 함수의 매개변수를 사용한다.

 

다음은 base condition이 n > 5 일 때의 재귀 함수 예시이다.

void increase(int n) {
   printf("현재 %d 상태입니다.\n", n); // DEBUG
   if (n > 5) {
      printf("n이 5를 넘어서 종료합니다.\n"); // DEBUG
      return; // n이 5를 넘으면 종료
   }

   increase(n + 1); // n을 1 증가시키면서 재귀적 실행

   printf("%d 상태인 함수를 종료합니다.\n", n); // DEBUG
}

현재 1 상태입니다.
현재 2 상태입니다.
현재 3 상태입니다.
현재 4 상태입니다.
현재 5 상태입니다.
현재 6 상태입니다.
n이 5를 넘어서 종료합니다.
5 상태인 함수를 종료합니다.
4 상태인 함수를 종료합니다.
3 상태인 함수를 종료합니다.
2 상태인 함수를 종료합니다.
1 상태인 함수를 종료합니다.

increase 함수가 n 이 1인 상태에서 시작해서, n을 1 증가시킨 값으로 자기 자신을 호출하며 계속 함수를 호출한다.

그러다 base condition 을 만족하면, 더이상 자기 자신을 호출하지 않고 함수를 종료한다.

함수가 base condition에 의해 종료되면 기존에 실행했던 함수가 호출한 함수가 종료되기 때문에, 순차적으로 재귀 함수가 종료된다.

이러한 원리를 사용해 다양한 문제를 재귀적으로 해결할 수 있다.

다음과 같은 관점으로도 볼 수 있다.

함수 안에서 자기 자신을 계속 호출하다가, base condition 충족 후 차례로 종료되는 순서

이런 시점으로 함수를 바라보면, 절차지향적으로 재귀를 바라볼 수 있다. 그러나 사실 재귀를 다룰 때는 절차지향적 사고보다는 귀납적 사고로 바라본다면 더욱 재귀를 능숙하게 다룰 수 있다.

 

재귀 - 귀납적 사고

명제 p(n)이 모든 자연수에 대해 성립한다는 것을 보이기 위해 p(1) 이 성립한다는 것과 p(n)이 성립할 때 p(n+1) 도 성립한다는 것을 보이면 귀납적으로 증명이 가능하다.

void func1(int n) {
    printf("%d ", n);
    if(n > 1) func1(n - 1);
}

생각해보자. func1(1) 가 1을 출력한다. ( n 이 1일 때는 재귀 호출을 하지 않는다. )

 

func1(2) 가 2와 1을 출력하고, func1(3) 가 3과 2와 1을 출력하고, ..... , func1($n$) 가 $n, n-1, n-2, ..., 3, 2, 1$ 을 출력한다고 가정해보자.  여기서 func1($n$) 은 $n$ 을 출력하고 func1($n - 1$) 을 호출한다. ( base condition은 $n$이 1일때 1을 출력하고 종료한다. )

 

func1($n+1$) 은 $n + 1$ 을 출력하고 func1($n$) 을 호출하며, func1($n$) 은 $n, n-1, n-2, ..., 3, 2, 1$을 출력한다고 가정했기 때문에 func1($n+1$) 이 $n + 1, n, n - 1, ..., 3, 2, 1$ 이 출력됨을 보일 수 있다.

이로써, func1($n$)이 $n, n-1, n-2, ..., 3, 2, 1$을 출력한다는 것을 증명할 수 있다.

 

재귀를 귀납적으로 바라보면, 재귀를 복잡하게 응용해야 할 때 귀납적 증명을 이용해 쉽게 원리를 생각해낼 수 있다.

이후에 다룰 예시 문제에서 재귀를 귀납적으로 사용해볼 것이다.

 

다음은 재귀를 이용한 간단한 응용 문제이다.

재귀 - 1부터 N까지의 합

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

함수 반환형을 이용해 1부터 N까지의 합을 구할 수 있다.

 

재귀 - 유클리드 호제법

최대공약수를 구하는 알고리즘인 유클리드 호제법을 재귀로 구현할 수 있다.

int gcd(int a, int b) {
   if (a % b == 0) return b;
   else return gcd(b, a % b);
}

재귀 - 팩토리얼

n! 을 구하는 알고리즘을 재귀로 구현할 수 있다.

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

재귀 - 피보나치 수

n 번째 피보나치 수를 구하는 알고리즘을 재귀로 구현할 수 있다.

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

 

이제 재귀를 문제에 적용해보자.

4779 : 칸토어 집합

문자열을 3등분한 뒤, 가운데 문자열을 공백으로 바꾸는 과정을 선의 길이가 1일때 까지 반복해야 한다.

즉, base condition은 선의 길이가 1일때 까지이다.

 

- -

func(1)의 출력은 - - 임이 성립된다. ( -가 $3^1$개 있는 문자열에서 문자열을 3등분 한 뒤 가운데를 공백으로 바꾼다. )

 

func(2)가 -가 $3^2$개 있는 문자열에서 문자열을 3등분 한 뒤 ( $3^1$ 길이의 문자열이 3개 만들어짐 ) 가운데를 공백으로 바꾼다. 선의 길이가 1이 될 때까지 남은 선을 3등분하고 가운데를 공백으로 바꿔야 하는데, 즉 $3^1$ 길이의 문자열을 나누어야 한다는 것이기 때문에 func(1)을 실행해야 한다는 것이다!

 

func($n$)이 -가 $3^n$개 있는 문자열에서 문자열을 3등분 한 뒤 가운데를 공백으로 바꾸며 선의 길이가 1이 될 때까지 반복한다고 (func($n-1$) 실행, func($n-2$) 실행, ..., func($2$) 실행, func($1$) 실행) 가정할 때, func($n+1$)이 -가 $3^(n+1)$개 있는 문자열에서 문자열을 3등분 한 뒤 가운데를 공백으로 바꾸고, 남은 두 선에서 func($n$)을 실행한다.

이로써, func($n$)이 -가 $3^n$개 있는 문자열에서 문자열을 3등분 한 뒤 가운데를 공백으로 바꾸며 선의 길이가 1이 될 때까지 반복한다는 것을 증명할 수 있다.

 

이를 코드로 구현해보자. 

void blank(int k) {
    while(k--) printf(" ");
}

void line(int k) {
    if(k == 1) {
        printf("-");
        return;
    }

    line(k/3);
    blank(k/3);
    line(k/3);
}

공백으로 바꾸는 것은 결국 공백을 그만큼 출력해야 한다는 것이기에 다음과 같이 구현했다.

k가 1이 될 때 선을 하나 출력하고, base condition을 출력하지 않을 때는 선 / 공백 / 선 함수를 계속 실행하도록 한다.

 

- 전체 코드

#include <stdio.h>

void blank(int k) {
    while(k--) printf(" ");
}

void line(int k) {
    if(k == 1) {
        printf("-");
        return;
    }

    line(k/3);
    blank(k/3);
    line(k/3);
}

int power(int n, int k) {
    if(k == 0) return 1;
    else return n * power(n, k - 1);
}

int main(void) {
    while(1) {
        int n;
        int r = scanf("%d", &n);
        if(r != 1) break;
        
        line(power(3, n));
        printf("\n");
    }
    return 0;
}

 

재귀는 귀납적으로 생각해야 능숙하게 다룰 수 있기 때문에 어려운 감이 있을 수도 있다. 여러 문제를 풀어보며 재귀에 대한 감을 잡으면 문제를 쉽게 풀이할 수 있을 것이다.