CODEWITHSUNDEEP
crecursion
Worice
Worice

Reputation: 4037

Count number of digits recursively

In order to learn recursion, I want to count the number of decimal digits that compose an integer. For didactic purposes, hence, I would like to not use the functions from math.h, as presented in:

I tried two ways, based on the assumption that the division of an integer by 10 will, at a certain point, result in 0.

The first works correctly. count2(1514, 1) returns 4:

int count2(int n, int i){
        if(n == 0)
                return 0;
        else
                return i + count2(n / 10, i);
}

But I would like to comprehend the behavior of this one:

    int count3(int n, int i){
            if(n / 10 != 0)
                    return i + count3(n / 10, i);
    }

For example, from count3(1514, 1); I expect this:

1514 / 10 = 151;        # i = 1 + 1 
151  / 10 = 15;         # i = 2 + 1
15   / 10 = 1;          # i = 3 + 1
1    / 10 = 0;          # Stop!

Unexpectedly, the function returns 13 instead of 4. Should not the function recurse only 3 times? What is the actual necessity of a base case of the same kind of count2()?

Upvotes: 1

Views: 6605

Answers (4)

John Forkosh
John Forkosh

Reputation: 522

I don't think you need that i+count() in the recursion. Just 1+count() can work fine...

#include <stdio.h>
#include <stdlib.h>
static int count(), BASE=(10);
int main ( int argc, char *argv[] ) {
  int num = (argc>1?atoi(argv[1]):9999);
      BASE= (argc>2?atoi(argv[2]):BASE);
  printf(" #digits in %d(base%d) is %d\n", num,BASE,count(num)); }
int count ( int num ) { return ( num>0? 1+count(num/BASE) : 0 ); }

...seems to work fine for me. For example,

bash-4.3$ ./count 987654
 #digits in 987654(base10) is 6
bash-4.3$ ./count 123454321
 #digits in 123454321(base10) is 9
bash-4.3$ ./count 1024 2   
 #digits in 1024(base2) is 11
bash-4.3$ ./count 512 2
 #digits in 512(base2) is 10

Upvotes: 0

flaviodesousa
flaviodesousa

Reputation: 7815

If you do not provide a return statement the result is indeterminate.

On most architectures that mean your function returns random data that happens to be present on the stack or service registers.

So, your count3() function is returning random data when n / 10 == 0 because there is no corresponding return statement.

Edit: it must be stressed that most modern compilers are able to warn when a typed function does not cover all exit points with a return statement. For example, GCC 4.9.2 will silently accept the missing return. But if you provide it the -Wreturn-type compiler switch you will get a 'warning: control reaches end of non-void function [-Wreturn-type]' warning message. Clang 3.5.0, by comparison, will by default give you a similar warning message: 'warning: control may reach end of non-void function [-Wreturn-type]'. Personally I try to work using -Wall -pedantic unless some required 3rd party forces me to disable some specific switch.

Upvotes: 3

Saurav Sahu
Saurav Sahu

Reputation: 13924

Not returning value in a value-returning function is Undefined behavior. You should be warned on this behavior Your logic is also wrong. You must return 1 when `(n >= 0 && n / 10 == 0) and 

if(n / 10 != 0)
        return i + count3(n / 10, i);
else if (n >= 0) return 1;
else return 0;

Upvotes: 2

Charles
Charles

Reputation: 1108

In recursion there should be base conditions which is the building block of recursive solution. Your recursion base doesn't return any value when n==0 — so the returned value is indeterminate. So your recursion count3 fails.

Upvotes: 3

Related Questions