[Resolved] Recursion: Reverse an Integer

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:

Code:

---

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.

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.

Code:

---

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;
               
               
        }
  }
}

---

Code:

---

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));       
        }
}

---

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

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

Code:

---

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

---

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.

Code:

---

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;
}

---

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

Code:

---

    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.

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