Optimizing a recursive method call

Question

One of the books I'm currently reading to learn C# asked me to write a method that takes an integer between 1 and 99999 and displays each number in that integer in a sequence, separating each digit by 2 spaces. For example: the int 87564 would be written to the console as 8 7 5 6 4.

This is simple enough to do using the input as a string, converting it to a char array, or looping over the string with a foreach and printing out a formatted string for each character.

For fun though and mostly to challenge myself, I like to work out the problems as they are intended for someone just learning the concepts for the first time. The chapter was about methods and briefly introduced recursion. It's clearly the author's intent that you solve this using division and modulus operations to pick off each digit and then write them out.

So there really were limited options in terms of solving this with the material you have learned to this point in the book. You could pick off each digit and store it as it's own variable, then later write them out in order since you know the range of integers.

I decided to make the method more useful by really allowing any non-negative integer and my approach involved recursion. I'm not really experienced using recursion so I'd like to get some feedback on my implementation to see what I could have done better.

    static void DisplayDigits(int value)
    {
        if (value < 10)
        {
            Console.Write("{0}  ", value);
            return;
        }
        DisplayDigits(value / 10);
        Console.Write("{0}  ", value % 10);
    }

It appears to be working for all non-negative numbers I've tried. I even wrote an overload that takes a ulong and passed it UInt64.MaxValue and it printed everything fine. I can't help but feel like maybe it could be better in some way. Any criticism, suggestions, links to more reading material would be appreciated.

in the `Write` where `value < 10`, you don't need the trailing spaces, since that will be the last digit printed — dub stylee, Feb 07 '14 at 18:07
This question appears to be off-topic because it is asking for a code review. Try codereview.stackexchange.com? — crashmstr, Feb 07 '14 at 18:13
That call to `Console.Write` where `value < 10` is actually the first digit printed. Thanks for the code review site link. I will try that. — Gary Justin, Feb 07 '14 at 18:16

Nicholas Carey · Answer 1 · 2014-02-07T19:30:13.393

Try

static void Digits( uint n )
{
  if ( n == 0 ) return ;
  Digits( n / 10 ) ;
  Console.WriteLine( "{0}  " , n % 10 ) ;
  return ;
}

But since recursion is equivalent to using a stack — the call stack being the stack that you're using — and, since Stack<T> is also IEnumerable<T>, the recursion is easily transormed into the equivalent

static void Digits( uint n )
{
   Stack<char> digits = new Stack<digits>() ;
   for ( uint i = n ; i > 0 ; i/=10 )
   {
      digits.Push( '0'+ i%10 ) ;
   }
   Console.WriteLine( string.Join("  ", digits ) ) ;
   return ;
}

Just for fun, a straight iterative solution that doesn't use anything but the barest set of fundamentals:

static void WriteDigits( uint n )
{
  string s = "" ;
  do
  {
    if ( s.Length > 0 ) s += "  " ;
    s += (n%10).ToString() ;
    n /= 10 ;
  } while ( n > 0 ) ;
  Console.WriteLine( string.Reverse() ) ;
}

Or, even easier, a one-liner, using just the properties and methods of string:

static void WriteDigits( uint n )
{
  Console.WriteLine( string.Join( "  " , n.ToString().ToCharArray() ) ;
}

I tried to do something similar to your iterative approach in my earliest attempts, however I kept running into the problem of having the numbers in reverse order, and since the author hadn't talked about properties and methods of the `string` class in much detail, I added those to my list of restrictions. — Gary Justin, Feb 07 '14 at 19:55

Rick Love · Accepted Answer · 2014-02-07T18:36:39.520

1

Lookup "Tail Recursion"

Basically, you want your recursive call to be the last call so that the compiler can optimize by reusing the stack (without adding another level to the stack).

However, in practice I find it hard to structure.

Here is an example:

static string DisplayDigits(int value, string after)
{
    var t = string.Format("{0}  ", value % 10);

    if (value < 10)
    {
        return t + after;
    }

    return DisplayDigits(value / 10, t + after);
}

I recommend matching your code structure to your data.

With sequential data, use a loop (or better a linq expressions which enables parallellism).

Recursive calls should be reserved for hierarchical data (multiple children).

edited Feb 07 '14 at 18:36

answered Feb 07 '14 at 18:23

Rick Love

12,519
4
28
27

Well now that you've brought it up, how would you recommend solving this without recursion? Obviously a loop is the best way, but at this point in the text the author hasn't covered arrays or `foreach` loops. He assumes you will get a `string` from `Console.ReadLine`, use `Convert.ToInt32` and then break the resulting number down to digits using `/` and `%`. The `integer` input is limited to numbers between 1 and 99999, so it'd be simple to pick off each digit and store it, but that didn't seem elegant to me and I wanted something that could take any non-negative number and work. – Gary Justin Feb 07 '14 at 18:56
Also, he hasn't really talked about any sort of collection that you could iterate over. I'm not entirely sure how you would loop over the digits of an integer without some sort of array at least. At the end of the day it's throwaway code from a textbook exercise. However, I like the idea of trying to optimize this with restrictions for the sake of mastery. I appreciate your help. – Gary Justin Feb 07 '14 at 19:14
One should note that, while the CLR and the JIT compiler **do** implement TRO (tail recursion optimization), the particular language compiler must emit the correct IL. The C# compiler does not, but the F# compiler does (recursion being pretty fundamental for a functional language). See http://stackoverflow.com/questions/491376/why-doesnt-net-c-optimize-for-tail-call-recursion for more. – Nicholas Carey Feb 07 '14 at 19:22

Optimizing a recursive method call

2 Answers2