1

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()?

Jonathan Leffler
  • 730,956
  • 141
  • 904
  • 1,278
Worice
  • 3,847
  • 3
  • 28
  • 49

4 Answers4

3

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.

flaviodesousa
  • 7,255
  • 4
  • 28
  • 34
  • 1
    There's random and there's random. It's perhaps 'quasi-random' or 'unpredictable' or … well, 'indeterminate' is also good, but perhaps you need to use something else in the second and third paragraphs (sentences). – Jonathan Leffler Jun 11 '17 at 06:32
  • 1
    Considering the value you get as "random" i.e. unpredictable and practically never the single correct value seems a suitably paranoid way of thinking about this. Even if many definitions of "random" say something else. The question was not "How can I make a good random number generator?" to that, this would be a horribly wrong answer. – Yunnosch Jun 11 '17 at 06:37
  • 1
    Thanks for your explanation. I had no I idea of such behavior. – Worice Jun 11 '17 at 06:45
  • 1
    OP seems to appreciate the recommendation of using strict warnings, which would commented on exactly the right part of the code. Would you like to edit that into your good answer? – Yunnosch Jun 11 '17 at 06:46
3

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.

Jonathan Leffler
  • 730,956
  • 141
  • 904
  • 1,278
Charles
  • 1,008
  • 10
  • 21
  • Thanks for your suggestion, both to @JonathanLeffler and to Charles. – Worice Jun 11 '17 at 06:47
  • Charles, I recommend to study the edit by @JonathanLeffler. It fundamentally changed the core part of your answer. – Yunnosch Jun 11 '17 at 06:51
  • @Yunnosch: you've made that point before (and deleted it). I've stated before (but deleted my response since it was responding to a now non-existent comment) that I disagree. If it had said `return NULL`, I'd be with you. It didn't. I stand by my edit. – Jonathan Leffler Jun 11 '17 at 06:53
  • @JonathanLeffler Only mentioning the `null`, which implies the value `0` (or is too misleadingly phrased), does not explain the misbehaviour observed by OP. It also does not mention the questionable quality of that kind of code. Both those imprecisions made the original answer not worth any upvotes. With your edits these are fixed and the resulting answer does deserve upvotes. I recommend to study the change, for the purpose of improving answerers understanding of either C or how to make good answers at StackOverflow. My previous comment was in a very different tone I did not like anymore. – Yunnosch Jun 11 '17 at 07:03
2

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;
Saurav Sahu
  • 13,038
  • 6
  • 64
  • 79
  • Thanks for your suggestion! – Worice Jun 11 '17 at 06:47
  • Strictly, it's using a putatively returned value when no value is returned that's undefined behaviour, isn't it? If you don't attempt to use the value and no value is returned, you're on thin ice (things go haywire if someone changes the code to use the value), but not actually invoking undefined behaviour. This is the nittiest of nit-picking. It's a horrid idea to say "I'll return a value" and then not do so (so I intensely dislike the special case for `main()` in C99 and later). And I 100% agree that the code should return a value from every path — because it is used. – Jonathan Leffler Jun 11 '17 at 06:50
0

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
John Forkosh
  • 502
  • 4
  • 14