삼각수의 재귀적 분해

삼각수는 처음부터 n까지의 자연수를 더한 값이다.

S_n=\sum_{k=1}^{n}k=\frac{n(n+1)}{2}

이 공식은 삼각수를 직접 계산하는 방법을 알려준다. 하지만 삼각형으로 배열된 점들을 작은 삼각형과 직사각형으로 분해하면, 같은 값을 재귀적으로 계산할 수도 있다.

이 글에서는 삼각수의 기하학적 분해에서 출발해 재귀식을 유도하고, 이를 C로 구현한다. 또한 재귀 호출의 말단에서 나타나는 두 가지 기본형을 계수하고, 재귀 방식과 직접 계산 방식의 실행 시간을 비교한다.

1. 삼각수의 기하학적 표현

삼각수 S_n은 한 변에 점이 n개 있는 삼각형으로 나타낼 수 있다. 각 행의 점 개수는 위에서부터 1,2,\ldots,n이다.

예를 들어 n=5이면 전체 점의 개수는 S_5=15이다. 이 삼각형을 위쪽의 작은 삼각형, 직사각형 부분, 아래쪽의 작은 삼각형으로 나누어 보자.

파란색 영역은 S_2=3이다. 주황색과 노란색 영역은 각각 점 세 개로 이루어진 작은 삼각형이며, 두 영역을 합치면 2\times3=6개의 점으로 이루어진 직사각형 부분이 된다. 초록색 영역은 S_3=6이다.

따라서 전체 점의 개수는 다음과 같다.

S_5=S_2+2\cdot3+S_3

S_5=3+6+6=15

여기서 직사각형 부분은 다시 두 개의 S_2로 나눌 수 있다. 그러므로 같은 분해를 다른 방식으로 묶으면 다음과 같이 쓸 수 있다.

S_5=3S_2+S_3

이 두 식은 같은 점들을 서로 다른 방식으로 묶은 것이다. 첫 번째 식은 작은 삼각형과 직사각형의 분해를 보여주고, 두 번째 식은 재귀 함수에서 사용할 네 개의 부분 중 세 개의 작은 삼각형을 하나의 계수로 묶어 표현한다.

2. 재귀식 유도

n을 다음과 같이 나타내자.

n=2q+r,\qquad r\in\{0,1\}

여기서 q=\lfloor n/2\rfloor이고, r=n\bmod 2이다.

앞 절의 기하학적 분해를 일반화하면 다음 식을 얻는다.

S_n=S_q+q(q+r)+S_{q+r}

이제 n의 홀짝에 따라 직사각형 부분을 다시 정리하자.

n=2q+1인 경우에는 직사각형 부분의 크기가 q(q+1)이다. 한편,

q(q+1)=2S_q

이므로 다음 재귀식을 얻는다.

S_{2q+1}=3S_q+S_{q+1}

n=2q인 경우에는 직사각형 부분의 크기가 q^2이다. 다음 항등식을 이용하면,

q^2=S_q+S_{q-1}

다음 재귀식을 얻는다.

S_{2q}=3S_q+S_{q-1}

두 경우를 하나의 조건문으로 합치면 다음과 같다.

S_n= \begin{cases} 3S_{\lfloor n/2\rfloor} +S_{\lfloor n/2\rfloor+1}, & n\text{이 홀수}\\ 3S_{n/2}+S_{n/2-1}, & n\text{이 짝수} \end{cases}

이 식은 실제 C 구현의 재귀 분기와 일치한다. 중요한 점은 계수 3이 붙은 항을 세 번 재귀 호출하는 것이 아니라, 한 번 계산한 반환값에 3을 곱한다는 것이다.

예를 들어 n=5이면 다음과 같다.

S_5=3S_2+S_3

=3\cdot3+6=15

n=6이면 다음과 같다.

S_6=3S_3+S_2

=3\cdot6+3=21

따라서 홀수와 짝수에 대해 각각 다른 하위 문제를 선택하되, 같은 재귀 함수로 계산할 수 있다.

3. C 구현

다음은 재귀식과 말단 계수를 그대로 유지하면서 정수 오버플로와 출력 형식 문제를 수정한 코드다.

#include <stdio.h>
#include <time.h>

long long n_3 = 0;
long long n_1 = 0;

long long sigma_norec(int n) {
    return ((long long)n * (n + 1)) / 2;
}

long long sigma_rec(int n) {
    if (n <= 0) {
        return 0;
    }

    if (n == 2) {
        n_3++;
        return 3;
    }

    if (n == 1) {
        n_1++;
        return 1;
    }

    if (n % 2) {
        return 3 * sigma_rec(n / 2)
             + sigma_rec(1 + n / 2);
    }

    return 3 * sigma_rec(n / 2)
         + sigma_rec(n / 2 - 1);
}

int main(void) {
    int n = 65535;
    struct timespec start, end;

    clock_gettime(CLOCK_MONOTONIC, &start);
    long long v = sigma_rec(n);
    clock_gettime(CLOCK_MONOTONIC, &end);

    long long time_v =
        (end.tv_sec - start.tv_sec) * 1000000LL
        + (end.tv_nsec - start.tv_nsec) / 1000LL;

    clock_gettime(CLOCK_MONOTONIC, &start);
    long long w = sigma_norec(n);
    clock_gettime(CLOCK_MONOTONIC, &end);

    long long time_w =
        (end.tv_sec - start.tv_sec) * 1000000LL
        + (end.tv_nsec - start.tv_nsec) / 1000LL;

    printf("time(recursion): %lld us, "
           "time(no recursion): %lld us\n",
           time_v, time_w);

    printf("%s\n",
           w == v ? "recursion succeeded"
                  : "recursion failed");

    printf("n_3 leaf refers to\n"
           "  *\n"
           " * *\n"
           "form\n");

    printf("n_1 leaf refers to\n"
           "*\n"
           "form\n");

    printf("n_3 leaf: %lld, n_1 leaf: %lld\n",
           n_3, n_1);

    return 0;
}

원래 코드에서 sigma_norec()는 n*(n+1)을 int로 먼저 계산한다. n=65535일 때 이 곱은 32비트 부호 있는 정수의 최대값을 넘으므로, 반환형만 long long으로 바꾸는 것으로는 충분하지 않다. 피연산자 중 하나를 long long으로 변환한 뒤 곱해야 한다.

또한 printf("%\n", ...)는 유효한 형식 지정자가 아니다. 문자열을 출력하려면 %s를 사용해야 한다. 위 코드는 이 부분도 수정했다.

4. 재귀 호출 구조

n=5에서 재귀 호출 구조를 나타내면 다음과 같다.

여기서 S_5는 3S_2+S_3으로 계산된다. 따라서 왼쪽의 S_2 호출은 반환값에 3이 곱해지지만, 함수 자체는 한 번만 호출된다. 오른쪽의 S_3은 다시 3S_1+S_2로 분해된다.

말단에 도달하면 함수는 n=2에서 3을 반환하고 n_3를 증가시키며, n=1에서 1을 반환하고 n_1을 증가시킨다.

이 두 말단 형태는 각각 다음과 같다.

n_3:          n_1:

  *             *
 * *

n_3와 n_1은 각 유형의 말단 함수가 실제로 몇 번 호출되었는지를 나타낸다. 다만 이 값만으로 최종 결과를 3n_3+n_1로 계산할 수는 없다. 상위 호출에서 반환값에 3을 곱하는 연산이 중첩되므로, 각 말단의 기여도에는 그 경로에 따른 가중치가 적용되기 때문이다.

이 계수는 재귀 트리의 구조를 관찰하는 데 사용할 수 있다. 입력을 바꾸어 두 말단 유형의 호출 횟수가 어떻게 변하는지 비교하면, 재귀식이 어떤 기본형으로 분해되는지를 실험적으로 살펴볼 수 있다.

5. 시간 및 공간 복잡도

각 재귀 호출은 하위 문제 두 개를 생성한다. 두 하위 문제의 크기는 대략 절반이며, 각 호출에서 수행하는 산술 연산과 조건 검사는 상수 시간이다.

따라서 시간 복잡도는 다음 점화식으로 나타낼 수 있다.

T(n)=T(\lfloor n/2\rfloor) +T(\lceil n/2\rceil)+O(1)

이를 풀면 전체 재귀 호출 수는 O(n)이다. 재귀 깊이는 매 단계 문제 크기가 대략 절반으로 줄어들기 때문에 O(\log n)이다.

반면 직접 계산 방식은 고정된 수의 산술 연산만 수행하므로 산술 연산 횟수 기준으로 O(1)이다. 임의 정밀도 정수 연산이나 큰 정수의 비트 비용을 고려하면 실제 비용은 정수 크기에 따라 달라질 수 있다.

따라서 재귀 방식이 직접 계산 방식보다 빠를 것이라고 예상할 근거는 없다. 이 실험에서 비교할 대상은 재귀식이 실제로 올바른 결과를 반환하는지, 재귀 호출이 얼마나 발생하는지, 그리고 직접 계산과 비교했을 때 실행 시간이 어떻게 나타나는지다.

6. 실행 시간과 말단 계수

원래 실험에서는 n=65535를 사용하고, 재귀 방식과 직접 계산 방식의 실행 시간을 CLOCK_MONOTONIC으로 측정한다. 이 시계는 시스템 시각의 변경에 영향을 받지 않는 단조 시계이므로 경과 시간을 측정하는 데 적합하다.

다만 각 함수를 한 번씩만 실행해 얻은 시간은 엄밀한 성능 비교로 보기 어렵다. 실행 시간이 짧을수록 측정 오차와 스케줄링의 영향이 상대적으로 커진다. 더 신뢰할 만한 비교를 하려면 여러 차례 반복 측정하고, 각 방식의 중앙값이나 분포를 비교하는 편이 낫다.

또한 n_3와 n_1은 한 번의 재귀 실행에서 누적된 말단 호출 횟수다. 반복 측정 루프 안에서 그대로 사용하면 횟수가 계속 누적되므로, 말단 통계를 구하는 실행과 성능을 측정하는 실행을 분리하거나 각 반복 전에 카운터를 초기화해야 한다.

n=65535의 삼각수는 다음과 같다.

S_{65535}=\frac{65535\cdot65536}{2} =2147450880

이 값은 32비트 부호 있는 정수의 최대값보다 작다. 하지만 직접 계산식의 중간 곱인 65535\cdot65536은 그 범위를 넘는다. 따라서 결과값이 자료형에 들어간다는 사실만으로 중간 연산까지 안전하다고 판단해서는 안 된다.

7. 퇴타술과의 관련성

퇴타술(堆垛術)은 수를 배열하거나 쌓아 올린 형태로 다루는 전통적인 수학적 접근과 관련된 명칭이다. 삼각수 역시 수를 삼각형 형태로 배열했을 때 나타나는 대표적인 수열이다.

이 글에서 다룬 문제는 삼각수의 공식을 단순히 재진술하는 데 그치지 않는다. 삼각형의 배열을 작은 삼각형과 직사각형으로 분해하고, 그 관계를 재귀 함수로 옮긴 뒤, 계산 과정에서 나타나는 말단 형태까지 계수한다.

이 재귀식은 개인적인 실험과 여러 산법을 종합하여 고안한 것이다. 핵심은 특정 공식을 외우는 것이 아니라, 하나의 배열을 서로 다른 크기의 부분 문제로 분해하고 그 분해를 실행 가능한 프로그램으로 표현하는 데 있다. 기하학적 분할, 재귀 호출 구조, 말단 계수와 실행 시간은 각각 이 과정을 다른 관점에서 관찰하게 해 준다.