Recursion to the rescue!

Given only putchar (no sprintf, itoa, etc.) write a routine putlong that prints out an unsigned long in decimal.

Here is one of the questions from Microsoft interview.

It’s obvious that you can use the modulus operator (%10) and loop thru the digits one-by-one. Since n%10 gives you only the last digit, you need to somehow store it in a temporary array. I am sure the interviewer will not be too pleased with this and ask you to rethink again without using temporary storage.

The key is to think recursively. Recursion is very powerful and is able to solve this question easily. In fact, it is often used in conjunction with pointers to weed out candidates. Read this article on how Microsoft conduct interviews to get what I mean. Think of recursion as the allocation of a stack… Push the last digit onto the stack, then continue with the 2nd last, …, up until the first digit. Then when the function pops off the stack, you get the digit in the correct order. Voila!

You will probably attempt something like this at first try:

Guess what’s wrong?

You forgot to consider the special case when n == 0!

The above code can be modified to handle the special case of n == 0:

Great! Now you are able to think recursively 🙂 Here is another similar question that often pops up in a job interview:

Print a string in reverse order.

Reversing linked-list can be done recursively too. Can you figure out how to do it? Find out how in my next post.

VN:F [1.9.22_1171]
Rating: 4.7/5 (16 votes cast)
Recursion to the rescue!, 4.7 out of 5 based on 16 ratings

16 thoughts on “Recursion to the rescue!

  1. johny

    Thanks for the code on recursion. I always have a headacre about it. 🙁

    And thanks for the link provided, which let me have a glimpse on what the interviewer is thinking about.

    VA:F [1.9.22_1171]
    0
  2. johny

    Hi, 1337:

    Today, I am flipping the good old bible – The C Programming Language by K&R, for the implementation of quicksort function. As you know, it is implemented recursively.

    Another glimpse let me catch another recursive example presented in the book before qsort.

    4.10 Recursion

    C functions may be used recursively; that is, a function may call itself either
    directly or indirectly. Consider printing a number as a character string. As we
    mentioned before, the digits are generated in the wrong order: low-order digits
    are available before high-order digits, but they have to be printed the other way
    around.

    There are two solutions to this problem. One is to store the digits in an
    array as they are generated, then print them in the reverse order, as we did with
    i toa in Section 3.6. The alternative is a recursive solution, in which printd
    first calls itself to cope with any leading digits, then prints the trailing digit.
    Again, this version can fail on the largest negative number.

    #include

    /* printd: print n in decimal */
    void printd(int n)
    {
    if (n < 0) {
    putchar (' -' ) ;
    n = -n;
    }
    if (n / 10)
    printd(n / 10);
    putchar(n % 10 + '0');
    }

    When a function calls itself recursively, each invocation gets a fresh set of all
    the automatic variables, independent of the previous set. Thus in
    printd(123) the first printdreceives the argument n = 123. It passes 12
    to a second printd, which in turn passes 1 to a third. The third-level printd
    prints 1, then returns to the second level. That printd prints 2, then returns
    to the first level. That one prints 3 and terminates.

    It is dealing almost the same problem as the M$ interview problem. And it seems the textbook solution has handled the case where n == 0.

    Isn't it?

    VA:F [1.9.22_1171]
    0
    1. 1337c0d3r Post author

      Yup, you are right. It has handled the case where n == 0. This code is also more elegant without the repeated section in my example code. The conditional statement “if (n / 10)” is equivalent to “if (n >= 10)”.

      VN:F [1.9.22_1171]
      +2
      1. EG07

        I checked the book.
        In limits.h they define the magnitude of min and max limits of the signed integral types the same. So, the code is OK within the book’s limits.
        However, in platforms I have came across, the magnitude of the min is 1 more than max.

        VN:F [1.9.22_1171]
        0
  3. johny

    In flipping the K&R bible, I happened to find another solution to the string-reverse problem.

    Using the code in Section 3.5:

    #include

    /* reverse: reverse string s in place */
    void reverse(char s[])
    {
    int c, i, j;

    for (i = 0, j = strlen(s)-1; i 1) {
    /* Reverse the rest of the string. */
    reverse(s + 1);
    /* Put the first character at the end. */
    c = s[0];
    for (i = 1; i < l; i++)
    s[i – 1] = s[i];
    s[l – 1] = c;
    }
    }
    This is extracted from http://www.bamsoftware.com/computers/tcpl-answers.html.

    VA:F [1.9.22_1171]
    0
  4. Anonymous

    Above code wont produce the reverse of the digits…

    I think the code should be like this…

    void putlong(unsigned long n) {
    if (n < 10) {
    putchar(n + '0');
    return;
    }

    putchar(n % 10 + '0');
    putlong(n / 10);
    }
    please correct me if I am wrong…

    VA:F [1.9.22_1171]
    +2
  5. Pingback: putlong | 口├人人│의 Blog

  6. Pingback: Printing a Binary Tree in Level Order | 口├人人│의 Blog

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use the <code> tag to embed your code.

*