Recursion to the rescue- Stack as temporary storage

Source

Here is one of the questions from Microsoft interview.

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

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:

?

1 2 3 4 5 6

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

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:

?

1 2 3 4 5 6 7 8

void putlong(unsigned long n) { if (n < 10) { putchar(n + '0'); return; } putlong(n / 10); putchar(n % 10 + '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.

?

1 2 3 4 5 6

void printReverse(const char *str) { if (!*str) return; printReverse(str + 1); putchar(*str); }

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