CODEWITHSUNDEEP
calgorithmfunctionrecursion
Rabin Adhikari
Rabin Adhikari

Reputation: 310

How can we print the sum of series 1+ 11 +111+........ upto N terms using recursion in C

I have tried continuously to print the sum of this series using recursion but ended up returning its nth term only. I know how to print the sum of series using iteration but it has been too hard for me to print its sum using recursion.

After a lot of thinking, I came upto this as the final code.

#include <stdio.h>
int sumseries(int);
int main()
{
    int n;
    printf("Enter the number: ");
    scanf("%d",&n);
    printf("The sum of the series is %d",sumseries(n));
}
int sumseries(int n)
{
    int i,sum=0;
    if(n==1)
        return 1;
    for(i=0;i<n;i++)
        sum=sum*10+1;
    return (sum+sumseries(n-1));
}

Can you help me with this without using the for loop?

Thanks in advance for the answer!

Upvotes: 3

Views: 3910

Answers (2)

Vlad from Moscow
Vlad from Moscow

Reputation: 310960

We beginners should help each other.:)

Here you are.

#include <stdio.h>

unsigned long long int series_sum( unsigned int n )
{
    static unsigned long long int value;
    const unsigned long long int Base = 10;

    unsigned long long int sum = 0;

    if ( n )
    {
        value = Base *value + 1;
        sum += series_sum( n - 1 ) + value;
        value /= Base;
    }

    return sum;
}

int main( void )
{
    const unsigned int N = 10;

    for ( unsigned int i = 0; i < N; i++ )
    {
        printf( "series_sum( %u ) = %llu\n", i, series_sum( i ) );
    }

    return 0;
}

The program output is

series_sum( 0 ) = 0
series_sum( 1 ) = 1
series_sum( 2 ) = 12
series_sum( 3 ) = 123
series_sum( 4 ) = 1234
series_sum( 5 ) = 12345
series_sum( 6 ) = 123456
series_sum( 7 ) = 1234567
series_sum( 8 ) = 12345678
series_sum( 9 ) = 123456789

As you see the function has only one parameter as it is required. Also it is better to use the type unsigned int as the type of the argument (otherwise you have to check whether the argument is negative) and the type unsigned long long int as the return type because the type int (or unsigned int) is too small to keep the sum.

Upvotes: 1

Daniel Martin
Daniel Martin

Reputation: 23548

So, if you were doing this by hand, how would you do it?

Well, by hand you'd probably write each term down:

1 + 11 + 111 + 1111 + 11111 + 111111

And then you'd start taking sums: 1 + 11 = 12, 12 + 111 = 123, 123 + 1111 = 1234, etc.

Of course, you could also take the sums going backwards: 111111 + 11111 = 122222, 122222 + 1111 = 123333, etc.

In order to attack this with recursion, you'll need to carefully plan out what the function is returning and what its arguments are.

You have, in this problem, two things you need to calculate: the actual series terms (1, 11, 111, 1111, etc) and the sum of those terms. As is clear by the name of your function, you intend sumseries to be returning the sums of the series.

Now, you seem to have in hand already a way to make the next term from the current term (multiply by 10 and add 1), but that isn't helping with the recursion yet.

If you had a way to say "current term" added to "sum of the rest of the stuff", though, you'd be on your way towards a recursive solution.

So what if your function took two parameters: an n that says how many terms to write, and a current_term variable that gives the current term?

Then you could do this in part of your function:

next_term = 10 * current_term + 1
return current_term + sumseries(n-1, next_term);

And in fact, that's the core of it:

int sumseries(int n, int current_term)
{
    if(n==1)
        return current_term;
    next_term = 10 * current_term + 1
    return current_term + sumseries(n-1, next_term);
}

And then change the call in main to be sumseries(n, 1) instead of just sumseries(n)

Upvotes: 5

Related Questions