2
\$\begingroup\$

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);
  }
}
\$\endgroup\$
5
  • 1
    \$\begingroup\$ What about negative numbers? \$\endgroup\$
    – Null
    Mar 11 '20 at 22:37
  • \$\begingroup\$ Didn't make it to work for them \$\endgroup\$ Mar 11 '20 at 22:37
  • 1
    \$\begingroup\$ Then you should check for a negative number before you call countDigits() with a negative number. Also, unsigned int may be a more appropriate argument and return type if countDigits() is not intended to count the number of digits of a negative number. It's not difficult to make it work with negative numbers, though... \$\endgroup\$
    – Null
    Mar 11 '20 at 22:43
  • 1
    \$\begingroup\$ I can understand that you decided to implement it recursively as you said to be learning recursion. But if you should take a lesson from this, it should be that recursion is often not the best solution. The way you implemented it can produce up to 10 stack frames (for 32bit integers) where you only realy need one frame, two local variables and a while loop. \$\endgroup\$
    – slepic
    Mar 12 '20 at 7:52
  • \$\begingroup\$ ... and at other times, recursion is the best solution. Use the right tool for the job. Typical iterations are not a good recursion solution but do allow learners to "wrap their heads around it" \$\endgroup\$ Mar 14 '20 at 2:14
3
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ On gcc specifically, yeah nearly identical machine code. On icc -O3... fine machine code for my version, complete trash code for the recursive version, since it fails to tail-call optimize. Sitting in some ivory tower and saying that the compiler should take care of everything does us no good - in the real world that is not often the case. The programmer who made the call to use recursion is to blame for the mess, not the compiler. We shouldn't write needlessly inefficient code when there are faster and more readable alternatives. \$\endgroup\$
    – Lundin
    Mar 13 '20 at 8:45
  • 1
    \$\begingroup\$ Not only GCC but Clang produces exactly same code in both cases. Not only that, I have explicitly mentioned that is not appropriate technique to use in C and C++, as they are imperative languages. One more thing to mention - it is not tail recursive code at all, and clang and g++ do us a favor, when reorganize it to be such. Properly written tail recursive I am sure code will be optimal on Intel C++ too. Speaking of readability - for someone coming from say Haskell background, recursive version could be, in fact more readable, than the one with a loop. \$\endgroup\$
    – ilkhd2
    Mar 13 '20 at 10:09
  • \$\begingroup\$ Both incorrectly report 1 when n <= -10. \$\endgroup\$ Mar 13 '20 at 22:11
2
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ And to recursion-hugging people who will start to whine in comments and down-vote: talk to the disassembly. \$\endgroup\$
    – Lundin
    Mar 12 '20 at 9:42
1
\$\begingroup\$

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);
  }
}
\$\endgroup\$

This site is temporarily in read only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .