Counting the number of digits with a recursion algorithm in c

Question

I'm learning recursion and I think that I can finally wrap my head around it.

I had to write a program that given an integer would print out its number of digits and I wanted to know if it is correctly implemented and if there's anything I can do to make it better.

Here's my code:

#include<stdio.h>

int countDigits(int n);

int main(void){
  int n,result;
  printf("What is the number?\n");
  scanf("%d", &n);
  result=countDigits(n);
  printf("%d\n", result);
  return 0;
}

int countDigits(int n){
  if(n>=0&&n<10){
    return 1;
  }
  else{
    return 1+countDigits(n/10);
  }
}

Answer 1

I unfortunately cannot comment (not enough reputation), but in terms of performance and generated assembly code both variants are exactly same:

int countDigitsSane (int n){
  int digits=1;
  for(int i=n; i>9; i/=10)
  {
    digits++;
  }
  return digits;
}

int countDigits(int n){
  if(n<10){
    return 1;
  }
  else{
    return 1+countDigits(n/10);
  }
}

Pay attention, I have removed the redundant check in the recursive snippet.With that correction, the code generated by the compiler is almost 100% same, save for different choice of registers.

Having said that, it is indeed, better to avoid recursion in imperative languages (such as C++), however in functional languages (Haskell, OCaml etc.) , recursion is a normal thing, and the compiler guarantees it can optimise tail-recursive calls.

Answer 2

As mentioned in comments, you should be careful about which integer type you use. int is negative and if your function takes int as parameter, it will therefore be assumed that it can handle negative numbers. So unsigned int might have been a better choice.

More importantly, you should be aware that recursion is dangerous, ineffective and often hard to read. The compiler may not always be able to optimize away the recursive call - so-called tail-call optimization - and if it doesn't the function turns very slow and gives a peak in stack memory use.

In this specific case, the compiler should be able to recognize that the else is redundant and the recursive call ends up at the return statement where it should be in order to enable optimization.

Still, gcc gives me less efficient code for your recursive function than for a loop alternative, even though it could optimize away the recursive call. Disassembling your code and comparing it with this one:

int countDigitsSane (int n){
  int digits=1;
  for(int i=n; i>9; i/=10)
  {
    digits++;
  }
  return digits;
}

Then it gives me slightly worse code for the recursive alternative, https://godbolt.org/z/Ddzv9u. The assembler generated is pretty unreadable with lots of compiler tricks, but writing the code as a plain readable loop is what makes such tricks possible. Usually, code that is easily read by humans is code that is easily optimized by the compiler.

So what was gained from recursion? The code turned slower and harder to read. The uncomfortable truth here is that recursion is mostly used for posing, when the programmer writes needlessly complicated code on purpose to show off.

In the real world where professionals write code with the purpose of making it safe, rugged and maintainable, recursion should be avoided in general. There are very few actual uses for it outside artificial academic exercises - it should pretty much only be used in various specialized search/sort algorithms and never in ordinary application logic. High level language programmers may tell you otherwise, but that's because they don't have a clue about how actual machine code is generated.

Answer 3

it is correctly implemented (?)

No. Incorrect result when n <= 10.

Goal: Counting the number of digits with a recursion algorithm in c

Simply change the condition to handle all int.

int countDigits(int n){
  // if(n>=0&&n<10){
  if(n > -10 && n < 10) {
    return 1;
  }
  else {
    return 1 + countDigits(n/10);
  }
}