Series 1+11+111+… by recursion

Idea. Each term is made from the previous one: term(1) = 1 and term(i) = term(i−1) × 10 + 1 (1 → 11 → 111 → …). The sum is also recursive: sum(N) = sum(N−1) + term(N), with sum(0) = 0.

Two recursive functions are used:

• term(i) gives the i-th term (base case i = 1).
• sumSeries(n) adds term(n) to the sum of the first n−1 terms (base case n = 0).

#include <stdio.h>

/* term(i) = i-th term: 1, 11, 111, ... */
long term(int i)
{
    if (i == 1)
        return 1;
    return term(i - 1) * 10 + 1;
}

/* sum of first n terms */
long sumSeries(int n)
{
    if (n == 0)
        return 0;
    return sumSeries(n - 1) + term(n);
}

int main(void)
{
    int n;
    printf("Enter N: ");
    scanf("%d", &n);
    printf("Sum of first %d terms = %ld\n", n, sumSeries(n));
    return 0;
}

Sample run

Input: 5

Enter N: Sum of first 5 terms = 12345

The sum 1 + 11 + 111 + 1111 + 11111 = 12345 is correct. long is used because the terms grow quickly; with a 32-bit long, N = 11 or more overflows (the 11th term 11111111111 is larger than 2147483647), so use long long for larger N.