Integer to String recursive method

Question

I was experimenting with lists, sets, and finally maps when I spotted a pattern in my code to make it recursive. Now I haven't used recursion much in the past or at work and I was very excited to have something that does recursion.

I have this recursive method that takes in an Integer and returns a string representation of the Integer by reading two HashMaps.

For example representation(11) will be Eleven OR representation(89) will be Eighty-Nine, ect.

I have arranged to handle up to 999,999. Are there any improvements I could make to this current implementation to handle things more efficiently/speedily?

public String representation(Integer num) { StringBuffer numRep = new StringBuffer(); StringBuffer hundred = new StringBuffer("Hundred"); StringBuffer thousand = new StringBuffer("Thousand"); //The case for anything less than 20; 0-19 if (num < 20) { numRep.append(genNumMap.get(num)); //The case for any integer less than 100; 20-99 } else if (num < 100) { int temp = num % 10; if (temp == 0) { numRep.append(greaterNumMap.get(num)); } else { numRep.append(greaterNumMap.get(num - temp) + "-" + representation(temp)); } //The case for any integer less than 1000, covers the hundreds; 100-999 } else if (num < 1000) { int temp = num % 100; if (temp == 0) { numRep.append(representation(num / 100) + "-" + hundred); } else { numRep.append(representation((num - temp) / 100) + "-" + hundred + "-" + representation(temp)); } //The case for any integer less that one million, covers the thousands; 1,000 - 999,999 } else if (num < 1000000) { int temp = num % 1000; if (temp == 0) { numRep.append(representation(num / 1000) + "-" + thousand); } else { numRep.append(representation((num - temp) / 1000) + "-" + thousand + "-" + representation(temp)); } } else if (num > 1000000){ numRep.append("Sorry, this number is too large"); JOptionPane.showMessageDialog(null, "Sorry, this number is too large\n"+"Integers 0 through 999,999 are exceptable."); } return numRep.toString(); } 

Answer 1

1. Such an algorithm is very rarely used, so it is extremely unlikely that its performance matters. So, most chances are you do not need to optimize it at all. But if you insist:

2. Do not pre-initialize the 'hundred' and 'thousand' StringBuffers. Only initialize them if they are needed. As a matter of fact, it is good practice (though it does not have anything to do with performance) to not even declare them outside of the narrowest possible scope in which they will be used. By the way, I do not understand why 'hundred' and 'thousand' are StringBuffers instead of Strings.

3. You do not need HashMaps for this job; just use arrays of String. They will be faster.

4. It seems like the kind of recursion you are using is tail recursion, so you can trivially convert your function to work iteratively, which will probably yield better performance. I am not saying it will necessarily perform better, so write both versions and benchmark one against the other if you really care about performance. But if you do not, then keep the recursive version, it is way cooler, and even easier to read.

5. When you append to a StringBuffer, never append multiple strings concatenated with +. Always use a separate call to append() for each string. Otherwise, the compiler will very likely be creating more temporary StringBuffers behind your back in order to optimize your string append operations.

6. Considering that any number minus zero is still the same number, you can optimize this:

   int temp = num % 1000; if (temp == 0) { numRep.append(representation(num / 1000) + "-" + thousand); } else { numRep.append(representation((num - temp) / 1000) + "-" + thousand + "-" + representation(temp)); } 

   into this:

   int temp = num % 1000; numRep.append( representation( (num - temp) / 1000) ); numRep.append( "-" ); numRep.append( thousand ); if( temp != 0 ) { numRep.append( "-" ); numRep.append( representation( temp ) ); } 

Answer 2

By all means, implement your code iteratively -- recursion is probably never the most efficient way to do something, because you do indeed make multiple copies of the local variables. If your method allocates a 256 byte buffer on the stack, that 256 byte buffer is allocated every method call, and eventually, you'll run out of stack space.

What's more significantly expensive with a function call is allocating memory for it's internal procedures. If you have an iterative function -- one which exits before it is called again -- the allocation only needs to happen ONCE, the same region of memory will be reused. With a recursive function, however, allocation has to happen at each level of recursion. So the only good time to use recursion is when, for example, you need to compound data, in which case an iterative function would be allocating and returning data each time, or else there is no clear and easy iterative method. Main reasons to use recursion:

• Because it's cool.
• Because it will be fewer lines of code.

Method calling is slower then looping for several reasons. you have to unroll the stack, return, and remove variables passed into the function from the stack for every function call. Not to mention saving and restoring the stack pointer, it has several instructions associated with it, and difficult branch prediction as well

Loops, on the other hand, don't have to deal with half that stuff. most will fit completely in the icache. they allocate space for needed variables once, and they have no return pointer pushed on the stack with each function call. In short, they are the best option for anything that involves repeating a step.

As most programmers know, the solutions to many problems can be expressed very elegantly using recursion. However, it is also true that any recursive algorithm can be converted into an iterative one, and traditional wisdom suggests that iterative algorithms are preferred from the standpoint of performance and scalability. See.