Recursion...Its hard to grasp. Help.

[first2drown]

So I have my Algorithms class tonight and I want to get the lab done before or during the class. I have write a recursive method that takes an int as a parameter and also returns an int. It has to REVERSE the int. What the heck. I'm not allowed to convert it to a string or anything, it says that I will not get credit if I do. So could someone give me some hints? The only thing I've gotten so far is the main method that accepts an int from the user and the call to the reverse() method which hasn't even been written yet. K thx.

[JosAH]

Are two (recursive) methods allowed? If so, think of a number as HD where H is the number without the last digit D and D is the last digit. You want to reverse H and prepend the single digit D to it. This means that you have to multiply D by a power of ten depending on the magnitude of H.

Here's part of the spoiler:

    private static int pow(int i) {
 
        return (i < 10)?1:10*pow(i/10);
    }
 

kind regards,

Jos

[first2drown]

Thanks Joe! It will take a while for me to fully comprehend what you just wrote, but I'm going to print it out and refer to it whilst I write the method. I have a good deal of freedom as far as writing the method goes so I dont see why I couldn't use two. As long as I'm not converting it to a string ha! Thanks again Joe. If anyone else has any more suggestions please post!

[first2drown]

Okay so I'm feeling really good about myself right now. I got the program to work fairly well. HOWEVER...dot dot dot...the reverse1() method is supposed to eliminate any zero's. For example, 1024 should become 421. But I cant think of a way to do this. Anyone have any ideas? I have until next Tuesday to figure it out.

import java.util.*;
import java.lang.*;
 
public class Reverser
{
    public static void main(String args[])
    {
        Scanner kbd=new Scanner(System.in);
        int num;
 
        System.out.print("Enter a value to be reversed: ");
        num=kbd.nextInt();
 
        System.out.println(reverse1(num));
        System.out.println(reverse2(num));
    }
 
    public static int reverse1(int a)
    {
        if (a%10==0)
            return reverse1(a/10);
        if (a<10)
            return a;
        else
            return (int)Math.pow(10,(int)Math.log10(a))*(a%10)+reverse1((int)a/10);
    }
 
 
    public static int reverse2(int a)
    {
        if (a<10)
            return a;
        else
            return (int)Math.pow(10,(int)Math.log10(a))*(a%10)+reverse2((int)a/10);
    }
}

[JosAH]

There's no need to use those logarithms and power methods; Think of a number as a sequence of digits. When you remove the digit on the right side you add it to the right off another number; when there are no more digits left the new number represents the reverse of the original number; an example:

num: 345 rev: 0 -> num: 34 rev: 5 -> num: 3 rev: 54 -> num: 0 rev: 543

Your additional constraint forbids a zero to be shifted in at the reverse of the number; the code will be three lines: one for the sentinel case, one for the zero check and one for the normal case.

kind regards,

Jos

[first2drown]

Thanks again Jos! When I get back from work I will try to do that. It seems simple enough :).

[BSCode266]

I think you are doing it wrong. From what i understand what is important in this excercise is the recursion. As it is the reversing of digits i think the goal is to have one method do it all.

Take a look at this simple example with a global counter. In this counter you would have to put the length of the int.

void method( int counter){
     if(counter == 0){
         //Spot where you return the reversed int
         return reversed;
     }
     else {
        //This if should be for the handling of any zeros.
        if(something == 0){
           method(--counter);
        }
        else{
           //Reverse 1 digit here
           method(--counter);
           return;
        }
     }
} 

This is what i understood from your exercise, correct me if i am wrong.

Good luck,

BSCode266

[first2drown]

Thanks BSCode, I was still having problems getting reverse1() to work, and I think you just helped a lot.

[JosAH]

@first2drown
Show us your attempt(s) so we can comment on it.

kind regards,

Jos

[first2drown]

Jos, I would show you what I wrote if I had saved any changes to the code that I made Thursday night in Lab. I'm VERY new to this programming thing. I love it, but some concepts are still hard for me to grasp. Let me show you the actual assignment: http://www.midlandstech.edu/edu/ed/i...n/283/hw3.html

He extended the deadline, so I can work on it on Tuesday and Thursday during lab. The thing is...even my teacher can't figure it out and its incredibly discouraging. I'm actually the one who figured out how to get reverse2() working before anyone else...I had to show the teacher.

And when I was trying to implement what you told me to do Jos, I was having problems, not sure why exactly, I just couldn't get any of the output that I wanted. I spent most of my day Thursday trying to come up with some sort of algorithm to get it done. Definitely not saying that what you said is wrong, just that I lack the experience to implement it :( . So my code is nearly exactly the same as it was in my previous post except now it has NOTHING coded for reverse1().

[first2drown]

And after reading your post again I got an idea, so I'm gonna try that right now.

[first2drown]

Yeah still couldn't figure it out.

[JosAH]

Here goes: we want to reverse a bunch of digits; reread my previous reply: for a number num we remove the rightmost digits and shift it in another number that builds up the reverse; e.g. num: 3456, rev: 0; after one step we have num: 345 and rev: 6; after another step we have num: 34, rev: 65; a third step: num: 3, rev: 654 and a last step: num: 0, rev: 6543.

An additional constraint (so you told us) is that we don't want to shift in zeros in our (partially completed) reversed number.

In code: let the number num and the reversed number rev be the parameters to the (recursive) method:

int reverese(int num, int rev) { ... }
 

If num < 10 we're ready, i.e. we either shift it in the rev number from the right if it isn't zero or we simply return the reversed number:

int reverse(int num, int rev) {
   if (num < 10) return (num == 0)?rev:10*rev+num;
   ...
}
 

otherwise we either shift the rightmost digit to the reversed number if it isn't zero, else we simply forget about it:

int reverse(int num, int rev) {
   if (num < 10) return (num == 0)?rev:10*rev+num;
   if (num%10 == 0) return reverse(num/10, rev);
   return reverse(num/10, 10*rev+num%10);
}
 

The above code does what the story is all about: shift in any non-zero digit; keep on going when there are more digits (num >= 10) or we're done. The story to explain this all is much larger then the method itself (as often happens with recursive methods).

Try to chop down this little method so that it does shift in zeros and try to understand what it does in those three lines.

kind regards,

Jos

[first2drown]

Okay wow. I actually get it now. I added your code to my program, modified it so it could compile, then ran it in debug mode so I could see exactly how it worked. The problem I was having understanding it was the 2nd int parameter in the method. I feel like I tried everything except that. Also, it helped me learn how to use those ?:; statements, for some reason we didn't go over those in class. My final code:

import java.util.*;
import java.lang.*;
 
public class Reverser
{
    public static void main(String args[])
    {
        Scanner kbd=new Scanner(System.in);
        int num;
          int shortenedNum;
          int counter=0;
          boolean shortened = false;
 
        System.out.print("Enter a value to be reversed: ");
        num=kbd.nextInt();
 
 
        System.out.println(reverse1(num,0));
        System.out.println(reverse2(num));
    }
 
public static int reverse1(int a, int rev) {
    if (a < 10){
        if (a == 0)
            return rev;
        else
            return 10*rev+a;
        }
 
      if (a%10 == 0)
        return reverse1(a/10, rev);
 
    return reverse1(a/10, 10*rev+a%10);
 
   }
 
    public static int reverse2(int a)
    {
        if (a<10)
            return a;
        else
            return (int)Math.pow(10,(int)Math.log10(a))*(a%10)+reverse2((int)a/10);
    }
}
 

[first2drown]

Also, let me know if you see something wrong with this? Instead of the original reverse2 method.

public static int reverse3(int a, int rev)
      {
         if (a < 10)
            return 10*rev+a;
         return reverse1(a/10, 10*rev+a%10);
      }
   }

[BSCode266]

Well reverse3 isn't recursive. It is making a call to reverse1. For it to be recursive it should call itself.

return reverse1(a/10, 10*rev+a%10);

A little sidenote, you really should try to avoid using variables with names like "a", "b", "c". Name them to the thing they represent just like Jos did, call it "num". Now your code is small but if you develop this as a habbit you are going to be in a world of hurt later.

Greets,

BSCode266

[Nepomuk]

When looking at Jos' last answer, it can be reduced - I have a running solution that has only 2 lines. Just let the recursive method take 2 inputs and think about the various things, that could happen: Is it done? If so, what should the output be? If not, what should be done with the inputs? You should be using % and / operators of course.

Oh, and no pow method is needed - I just use a simple *10 here and then.

Greetings,
Nepomuk

[JosAH]

Why don't you simply show your code; this thread has been a give away after all.

kind regards,

Jos

[Nepomuk]

Guess you're right. OK, here's my reverse function:

private static int reverse(int given, int done) {
    if(given < 10) return (done*10+given);
    else return reverse(given/10,((given%10==0) ? done : (done*10+given%10)));
}

I've added a few extra brackets, just to make the way it works more clear. Of course, you can always remove them, if you like. Oh, and if you want to give only one argument, you can always overload the method with

private static int reverse(int num) {return reverse(num,0);}

Greetings,
Nepomuk

[JosAH]

@Nepomuk
You rewrote the if-then-else of lines #2 and #3 as a ternary expression. Not so intuitive is that the test for (given == 0) in line #1 is superfluous. It took me a bit of thinking (<-- that hurts! ;-) to understand it.

We could rewrite the entire thing as one big ugly line by using the ternary ?: expression again ...

kind regards,

Jos

[Nepomuk]

@JosAH
Jup, looks much nicer that way, doesn't it? ^^ @JosAH
Well, I thought I'd just reduce the amount of recursions. :D
@JosAH
Sure:

private static int r(int g,int d){return(g<10?d*10+g:r(g/10,g%10==0?d:d*10+g%10));}

will do the job just fine! ^^

Mind you, all of the solutions are tail recursive - isn't that beautiful? :-D Oh, and I just realised, that my solution isn't quite perfect - it doesn't work for negative numbers. So make that

private static int r(int g,int d){return((g>=0?g<10:g>-10)?d*10+g:r(g/10,g%10==0?d:d*10+g%10));}

(Math.abs() is SO overrated! ;-) )

Greetings,
Nepomuk

[JosAH]

@Nepomuk
There was no recursion involved in line #1, just a superfluous test. Your version doesn't reduce the amount of recursive steps; both versions take n steps where n is the number of digits in the number to be reversed.

@Nepomuk
Sure, all it does is chew off the rightmost digit and process it. It'd be more difficult not to implement tail recursion here. btw. Java version 7 has much better tail recursion removal; I like that, together with memoization those things can really speed up execution of it all and allows you to write functions in a more intuitive way.

kind regards,

Jos

[BSCode266]

I am not even close to you guys skill level, but isn't one important thing of writing code keeping it readable?

Greets,

~BSCode266

[JosAH]

@BSCode266
No, and readability is in the eye of the author anyways, so :-P
Remember: if it were hard to write it is supposed to be hard to read.

kind regards,

Jos ;-)

[first2drown]

Thank all of you so much for the help. In my last post about reverse3() i meant to edit it to be recursive.

public static int reverse3(int a, int rev) 
      { 
         if (a < 10) 
            return 10*rev+a; 
         return reverse3(a/10, 10*rev+a%10); 
      } 
   }

I tested it and this code does work. I went ahead and submitted the final version to the teacher along with comments on how it works! That was certainly a learning experience.

[JosAH]

@first2drown
That version does copy the zero digits into the reverse of the number; you wrote that you didn't want that.

kind regards,

Jos

[first2drown]

Well in reverse2() you do want to keep the 0s, but we used the Math.pow() method to do it, I was just testing reverse3() as a replacement to reverse2(). =D There were supposed to be 2 methods in my program, one that takes out the 0s and reverses, and one that reverses and keeps the 0s.

[JosAH]

@first2drown
Ok, I must've missed that part; problem solved then.

kind regards,

Jos