Recursive Decomposition of Triangular Numbers

A triangular number is the sum of the natural numbers from 1 through n.

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

This formula provides a direct way to calculate a triangular number. However, the same value can also be calculated recursively by decomposing a triangular arrangement of dots into smaller triangles and a rectangular region.

This article derives a recursive formula from the geometric decomposition of triangular numbers and implements it in C. It also counts the two types of base cases that appear at the leaves of the recursion and compares the execution times of the recursive and direct approaches.

For a visual introduction to triangular numbers, see Youtube.

1. Geometric Representation of Triangular Numbers

A triangular number S_n can be represented as a triangle with n dots along each side. The number of dots in each row, from top to bottom, is 1,2,\ldots,n.

For example, when n=5, the total number of dots is S_5=15. Consider dividing this triangle into a smaller upper triangle, a rectangular region, and a smaller lower triangle.

The blue region represents S_2=3. The orange and yellow regions are each small triangles containing three dots; together, they form a rectangular region containing 2\times3=6 dots. The green region represents S_3=6.

The total number of dots is therefore

S_5=S_2+2\cdot3+S_3

S_5=3+6+6=15

The rectangular region can itself be divided into two smaller triangles, each of size S_2. Grouping the same dots differently gives the equivalent expression

S_5=3S_2+S_3

These two expressions group the same dots in different ways. The first shows the decomposition into smaller triangles and a rectangle. The second groups three smaller triangular contributions under a single coefficient, giving a form suitable for the recursive function.

2. Deriving the Recurrence

Write n in the form

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

where q=\lfloor n/2\rfloor and r=n\bmod 2.

Generalizing the geometric decomposition from the previous section gives

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

We can now simplify the rectangular contribution according to whether n is odd or even.

When n=2q+1, the rectangular region contains q(q+1) dots. Since

q(q+1)=2S_q

we obtain the recurrence

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

When n=2q, the rectangular region contains q^2 dots. Using the identity

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

we obtain

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

Combining the two cases into a single conditional expression gives

S_n= \begin{cases} 3S_{\lfloor n/2\rfloor} +S_{\lfloor n/2\rfloor+1}, & n\text{ is odd}\\ 3S_{n/2}+S_{n/2-1}, & n\text{ is even} \end{cases}

This recurrence matches the two branches in the C implementation. An important detail is that the term multiplied by 3 does not cause three recursive calls. The recursive function is called once, and its return value is multiplied by 3.

For example, when n=5,

S_5=3S_2+S_3

=3\cdot3+6=15

When n=6,

S_6=3S_3+S_2

=3\cdot6+3=21

Thus, odd and even inputs select different subproblems, but both cases can be implemented using the same recursive function.

3. C Implementation

The following code preserves the recurrence and the counters for the two base cases while correcting the integer-overflow and output-format issues.

#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;
}

In the original code, sigma_norec() evaluates n*(n+1) as an int multiplication before returning the result. For n=65535, this product exceeds the maximum value of a 32-bit signed integer. Changing only the return type to long long is not enough: at least one operand must be converted to long long before the multiplication.

The original printf("%\n", ...) also uses an invalid format specifier. The %s specifier is appropriate for printing a string. Both issues are corrected above.

4. Recursive Call Structure

The recursive call structure starting at n=5 is shown below.

Here, S_5 is evaluated as 3S_2+S_3. The call to S_2 on the left contributes a return value multiplied by 3, but the function itself is called only once. The call to S_3 on the right is decomposed further as 3S_1+S_2.

When recursion reaches a base case, the function returns 3 at n=2 and increments n_3, or returns 1 at n=1 and increments n_1.

These two base cases have the following forms:

n_3:          n_1:

  *             *
 * *

n_3 and n_1 count how many times each type of base case is reached. However, the final result cannot be calculated simply as 3n_3+n_1. Each recursive return value may be multiplied by 3 at higher levels, so the contribution of a leaf depends on the multipliers along its path through the recursion tree.

The counters can still be used to examine the structure of the recursion tree. By changing the input and comparing how often each base case occurs, we can experimentally investigate how the recurrence decomposes into its elementary forms.

5. Time and Space Complexity

Each recursive call creates two subproblems. Their sizes are approximately half the original input, and each call performs a constant amount of arithmetic and conditional checking.

The time complexity can therefore be expressed by the recurrence

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

Solving this recurrence gives a total of O(n) recursive calls. The recursion depth is O(\log n) because the problem size decreases by approximately half at each level.

By contrast, the direct formula performs a fixed number of arithmetic operations, giving O(1) arithmetic-operation complexity. If arbitrary-precision arithmetic or the bit complexity of large integers is considered, the actual cost also depends on the size of the integers.

There is therefore no reason to expect the recursive method to be faster than the direct formula. The purpose of the experiment is to verify that the recurrence returns the correct result, measure how many recursive calls occur, and observe its execution time relative to direct calculation.

6. Execution Time and Leaf Counts

The original experiment uses n=65535 and measures the execution times of the recursive and direct implementations with CLOCK_MONOTONIC. This clock is not affected by changes to the system's wall-clock time, making it suitable for measuring elapsed time.

However, a single measurement of each function is not a rigorous performance comparison. Measurement noise and operating-system scheduling can have a relatively large effect when execution times are short. A more reliable comparison would repeat each measurement and compare the medians or distributions.

The counters n_3 and n_1 accumulate the number of base-case calls during a recursive run. If the function is called repeatedly inside a benchmarking loop, these counters will continue to accumulate. The statistical run should therefore be separated from the timing runs, or the counters should be reset before each repetition.

The triangular number for n=65535 is

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

This result is below the maximum value of a 32-bit signed integer. However, the intermediate product 65535\cdot65536 exceeds that range. Therefore, the fact that the final result fits in the data type does not guarantee that the intermediate calculation is safe.

7. Relation to Toeta-sul

Toeta-sul (堆垛術) is a traditional mathematical approach associated with arranging or stacking quantities into geometric forms. Triangular numbers are a representative example of a sequence that arises by arranging objects in a triangular pattern.

The problem considered here goes beyond restating the formula for triangular numbers. It decomposes a triangular arrangement into smaller triangles and a rectangular region, translates the relationship into a recursive function, and counts the base-case forms that appear during execution.

This recurrence was devised through personal experimentation and by combining ideas from different methods of calculation. The central idea is not to memorize a particular formula, but to decompose an arrangement into smaller subproblems and express that decomposition as an executable program. The geometric partition, recursive call structure, leaf counts, and execution times each provide a different perspective on the process.