[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)...