[Resolved] Recursion: Reverse an Integer

[The Hobo]

I need to write a recursive function to reverse the order of digits in an integer. This is a homework problem, so it has to be done using recursion (not a loop or anything). This is what I've come up with so far:

public int revDigits (int num) {
if (num < 10) {
return num;
} else {
int s = num / 10;
int d = num % 10;

int i = revDigits(s);

return (d * 10) + i; // incorrect

// need to find out how many digits in d:
//return (d * 10^(num digits in d)) + i);
}
}

The problem that I've come across is commetted at the bottom. Any help with solving this would be appreciated. Thanks in advance.

[System_Error]

here is how i reversed a string using substring() once. I don't know if this will help you or not. Maybe you can get an idea though.


public class ReverseString
{
public String reverse(String arg)
{
String tmp = null;
if (arg.length() == 1)
{
return arg;
}

else
{


String lastChar = arg.substring(arg.length()-1,arg.length());

String remainingString = arg.substring(0, arg.length() -1);

tmp = lastChar + reverse(remainingString);
return tmp;


}
}
}




import java.io.*;


public class TestReverse
{
public static void main(String[] args) throws IOException
{
System.out.println("Enter a line to be reversed");
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String inData;
inData = br.readLine();
ReverseString rs = new ReverseString();
System.out.println("Reversed: " + rs.reverse(inData));
}
}

[The Hobo]

Thanks, but I have the logical of how to do it down, I've just run into a specific problem. See the commented out portion of my code. What I need, unless there is a better way to go about this, is a way to count the number of digits in a number (hopefully without writing another method).

[System_Error]

This is the best I could do. I know it's not the same method, but maybe you can use it.


public int reverseDigits(int num)
{
int newInt = 0;
int tmpInt = num;
while(tmpInt != 0)
{
newInt *= 10;
newInt += tmpInt % 10;
tmpInt /= 10;
}
return newInt;
}

[CornedBee]

A problem that is particularly unsuited for recursion...

Anyway.

Since I just wrote a good deal of code and then had to delete it because it wouldn't work, let's try another way. What you need is a depth tracker.
int reverseDigits(int i) {
return revDigsRecur(i, new IntWrap());
}

int revDigsRecur(int i, IntWrap tracker) {
if(i < 10) {
++tracker.i;
return i;
} else {
int rev = revDigsRecur(i / 10, tracker);
rev += (i % 10) * Math.pow(10, tracker.i);
++tracker.i;
return rev;
}
}

class IntWrap {
public int i = 0;
}

[The Hobo]

System_Error, I came up with something similiar to yours, I think:

public int revDigits (int num) {
if (num < 10) {
return num;
} else {
int lastDigit = num % 10;
int revSeq = revDigits(num / 10);

// Following code counts digits in lastDigit
int j = revSeq;
int c = 0;
while (j != 0) {
j = j / 10;
c++;
}

return (lastDigit * (int)Math.pow(10, c)) + revSeq;
}
}

I know it's probably not best, but oh well.

CB, all of the recursion problems he gave us are better to accomplish without recursion.

Thanks for your help, guys.

[CornedBee]

Remember that your solution is O(n²), mine is O(n)...