CODEWITHSUNDEEP
crecursioncountingfunction-definition
Jason
Jason

Reputation: 95

using recursion to calculate total digits

I wrote this code that counts how many 1's there are in an integer using recursion. N has to be less than 9 digits. I can't seem to find what's wrong with my code and why it won't work. If anyone can give me a hint of where I went wrong I'd appreciate it.

#include <stdio.h>
#include <assert.h>

int count_ones(int n);

int main()
{
    assert(count_ones(1001)==2);
}

int count_ones(int n)
{   
    int sum = 0;
    int x;
    if(n == 0)
    {
        return sum;
    }
    else if(n > 999999999)
    {
        return sum;
    }
    else if(n <= 999999999)
    {
        x == n%10;
        if (x == 1)
        {
        sum = sum + 1;
        count_ones(n/10);
        }
        else
        {
        count_ones(n/10);  
        }
    }
    return sum;
}

Upvotes: 0

Views: 205

Answers (4)

Vlad from Moscow
Vlad from Moscow

Reputation: 310950

For starters there is a typo

x == n%10;

You mean assignment instead of the comparison

x = n%10;

In these calls of the function

    if (x == 1)
    {
    sum = sum + 1;
    count_ones(n/10);
    }
    else
    {
    count_ones(n/10);  
    }

you are not using the returned values of the recursive calls

count_ones(n/10);

Moreover as the function parameter has the signed type int then the user can pass to the function a negative number. In this case the function will return a wrong result.

Pay attention to that such restriction

else if(n > 999999999)

does not make a sense. The user can enter any number of the acceptable range of values for objects of the type int.

The function can look the following way as it is shown in the demonstrative program below.

#include <stdio.h>

size_t count_ones( int n )
{
    const int Base = 10;
    
    return n == 0 ? 0 : ( n % Base == ( n < 0 ? -1 : 1 ) ) + count_ones( n / Base ); 
}

int main(void) 
{
    printf( "%zu\n", count_ones( -11 ) );
    printf( "%zu\n", count_ones( 11 ) );
    
    return 0;
}

The program output is

2
2

Upvotes: -1

abelenky
abelenky

Reputation: 64682

Way too complicated.

Here's how to do it right:

int count_ones(int n)
{
    return n? (n%10 == 1) + count_ones(n/10) : 0;
}

For completeness, here's an iterative (non-recursive) solution.

int count_ones(int n)
{
    int total=0;
    for(;n; n/=10, total += (n%10==1));
    return total;
}

Upvotes: 0

Eugene Sh.
Eugene Sh.

Reputation: 18299

@Barmar's answer is giving you the idea of how to fix your approach. Here is an alternative one, which make the advantage of tail recursion which can be unrolled into a loop by the compiler. This approach is using accumulator (acc) to count the ones, and will only return it once.

int count_ones_rec(int n, int acc)
{
    if (n == 0)
        return acc;
    return count_ones_rec(n / 10, acc + (n % 10 == 1));
}

This can be wrapped in a function like:

int count_ones(int n)
{
    /* additional checks on `n` if needed */
    return count_ones_rec(n, 0);
}

Upvotes: 0

Barmar
Barmar

Reputation: 780842

You're not combining the current sum with the result from the recursive call. So you're just counting the last digit, all the other counts are being discarded.

int count_ones(int n) {
    if (n == 0 || n > 999999999) {
        return 0;
    } else if (n % 10 == 1) {
        return 1 + count_ones(n / 10);
    } else {
        return count_ones(n / 10);
    }
}

Upvotes: 4

Related Questions