Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 13 of 13

Thread: Recursion

  1. #1
    Banned
    Join Date
    May 2010
    Location
    North Central Illinois
    Posts
    1,631
    My Mood
    Sleepy
    Thanks
    390
    Thanked 112 Times in 110 Posts

    Red face Recursion

    I'm supposed to get it to take an int number and print it out one character at a time(one per line) and no, I'm not allowed to turn it into a String and use getCharAt(int x). I have to do it recursively.

    I found a way for a base case that will just print it if it is 0-9.

    It'll work in my other cases by diving by 10 till I reach the base case, then taking that number I get in the base case and multiplying it 10 raised to the number of times I had to divide by 10 to get the base case.

    For example

    225

    225 / 10 = 22;

    22/ 10 = 2;

    225 - 200 = 25;

    25 /10 = 2;

    25 - 20 = 5;

    2
    2
    5

    However, for cases where I something like

    x = n * 10^k + c
    0 <=c <= 9, That won't work and I need help figuring out what to do in those cases.

    For example, I can't use the above way exactly to work with

    30505.

    It'll only print
    3
    5
    5
    and miss the 0s.



  2. #2
    Member Darryl.Burke's Avatar
    Join Date
    Mar 2010
    Location
    Madgaon, Goa, India
    Posts
    491
    Thanks
    8
    Thanked 47 Times in 45 Posts

  3. The Following User Says Thank You to Darryl.Burke For This Useful Post:

    javapenguin (October 16th, 2010)

  4. #3
    Banned
    Join Date
    May 2010
    Location
    North Central Illinois
    Posts
    1,631
    My Mood
    Sleepy
    Thanks
    390
    Thanked 112 Times in 110 Posts

    Smile Re: Recursion

    Quote Originally Posted by Darryl.Burke View Post
    I always wondered what a modulo was. However, yeah, I knew about the % operator.

    2%1 = 0;

    1%2 = 1;

    I did realize that using the % operator would work if I did something like 300.

    However ,what about 505?

    505 / 10 = 50;

    50 /10 = 5;

    Okay, so if I have it so when the number I'm getting divided by 10 can be divided by 10 and not get a remainder, then I can add a 0.

    3505

    3505 /10 = 350

    350/10 = 35;

    35 / 10 = 3;

    print 3;

    3505-3000 = 505;

    505 /10 = 50;

    50 /10 = 5;

    505-500 = 5;

    How do I get the 0 in there exactly?

    I could try something to get it to print the 0, but how do I get it to print it after the 5?

    1050

    1050/10 = 105;

    105 /10 = 10;

    10/10 = 1;

    Ok, if I can show that for the first time, if num%10 = 0, then I get it to print the 0 after the single digit number I get at the end.

    1050-1000 = 50;

    50/10 = 5;

    Well, that's working so far.

    3505

    3505/10 = 350;

    350/10 = 35;

    35 /10 = 3;

    3505-3000 = 505;

    505/10 = 50;
    50/10 = 5;

    505-500 = 5;

    Ok, still lacking a 0. Getting better though.

    3050/10 = 3050

    3050%10 = 0; // print a zero after reaches base case
    305/10 = 30;
    30/10=3; // print a 3, then a 0.
    3050-3000 = 50;
    50&10 = 0; // print a 0 after reaches base case
    50/10=5 ; // print a 5 then a 0

    3
    0
    5
    0



    Now I get what you were trying to tell me.

    This might work. It looks like it is.

    300%10 = 0;
    300/10=30;

    30%10=0;


    30/10 = 3;

    Hey, there's a though, but how do I get it to print the 0s later each on one line?
    Last edited by javapenguin; October 16th, 2010 at 04:08 PM. Reason: Getting closer still

  5. #4
    Banned
    Join Date
    May 2010
    Location
    North Central Illinois
    Posts
    1,631
    My Mood
    Sleepy
    Thanks
    390
    Thanked 112 Times in 110 Posts

    Default Re: Recursion

    Ok, I figured out how to get it, but now it'll print it backwards, and I want it forwards.

    305

    305%10 = 5;

    305/10 = 30;

    30%10 = 0;

    30/10 = 3;

    it'll print
    5
    0
    3

    unless I can get it to print the other two after the 3 and in the right order.

  6. #5
    Banned
    Join Date
    May 2010
    Location
    North Central Illinois
    Posts
    1,631
    My Mood
    Sleepy
    Thanks
    390
    Thanked 112 Times in 110 Posts

    Default Ok, so I can get it to print it, but it'll print backwards.

    public void printDigits(int n)
    {
    if (0<=n<=9)
    int x = n;
    while (x/10 !=0)
    {
    x = x /10;
     
     
    }
     
     
     
     
     
     
    }
    5%10 = 5;

    25%10 = 5
    25/10 = 2;

    3005%10 = 5

    3005/10 = 300;

    300/10 = 30;
    300%10 = 0;
    30/10 = 3;
    30%10 = 0;
    3
    0
    0
    5


    n = 251
    int x = 0;

    251%10 = 1;

    251/10 = 25;

    25%10 = 5;

    25/10 = 2;



    251/10 = 25;

    25/10 = 2;
    25%10 = 5;

    2
    5
    1

    3245
    3245%10 = 5
    3245/10 = 324;
    324%10 = 4;
    324/10 = 32;
    32%10 = 2;
    32/10 = 3;
    Last edited by helloworld922; October 16th, 2010 at 08:39 PM.

  7. #6
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default Re: Recursion

    Please don't post multiple threads asking the same question. I've merged these two threads.

    Also, please use code tags. See my signature if you're unsure how to do this.

    You're printDigit codes doesn't have anywhere in it which invokes itself (that's the definition of recursion), also I don't see anywhere in it where anything is being printed out.

    I would recommend having your code return a string of what to display, this way you can build your string up from the right to left and print it out left to right (this will fix your reverse order problem).

  8. The Following User Says Thank You to helloworld922 For This Useful Post:

    javapenguin (October 16th, 2010)

  9. #7
    Banned
    Join Date
    May 2010
    Location
    North Central Illinois
    Posts
    1,631
    My Mood
    Sleepy
    Thanks
    390
    Thanked 112 Times in 110 Posts

    Default Re: Recursion

    I know what it should display, but even if I can figure out how to get it to print, it'll print backwards.

    I can store the values in an Integer ArrayList, but I still have no clue how to do this

    https://blackboard.ilstu.edu/webct/u...d/827617565041

    recursively
    Last edited by javapenguin; October 16th, 2010 at 09:24 PM.

  10. #8
    Banned
    Join Date
    May 2010
    Location
    North Central Illinois
    Posts
    1,631
    My Mood
    Sleepy
    Thanks
    390
    Thanked 112 Times in 110 Posts

    Default Re: Recursion

    public void printDigits(int n)
    {
     
    if (n < 0)
    {
    JOptionPane.showMessageDialog(null, "Hey, you can't have a negative value!", "No negatives please.", JOptionPane.ERROR_MESSAGE);
    return;
    }
    if (0<=n<=9)
    {
    System.out.println(n);
    return;
    }
     
     
     
    int x = n;
    int i = 0;
    ArrayList<Integer> aList = new ArrayList<Integer>();
     
    while (x/10 !=0)
    {
     
    x = x / 10;
     
    aList.add(i, x%10);
    i++;
     
    if (0 < x < 10)
    {
    System.out.println(x);
     
    for (int j = aList.length; j > 0; j--)
    System.out.println(aList.get(j));
     
    }
     
     
    }
     
     
     
     
     
     
    }

    Should I increment j forwards from 0 to length or downwards like I am from length to 0?

    How would you make this method recursive?

    Does ArrayList have a length method and/or variable and does it have a get(int index) method?

  11. #9
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default Re: Recursion

    I don't think you quite understand how recursion works.

    Here's a similar problem: factorials.

    Every recursive function has 3 basic parts:

    1. Base case(s). These are cases where the answer to this problem are "trivial". In this case, the base case is the number 0. 0! = 1
    2. Reduction step. Take the problem and reduce it. In this case, n! = n * (n-1)!
    3. Recursion call. The recursive function must call itself with the simplified problem until the problem reduces to a base case.

    Without these 3 steps, you don't have a recursive algorithm.

    So,

    public int recursiveFactorial(int n)
    {
        if(n == 0) // we have the simplest problem possible
        {
            return 1; // base case
        }
        return n * recursiveFactorial(n-1); // reduce the problem, recursively solve the factorial
    }

    Now you apply this process to your problem.

  12. The Following 2 Users Say Thank You to helloworld922 For This Useful Post:

    c.P.u1 (February 11th, 2011), javapenguin (October 17th, 2010)

  13. #10
    Banned
    Join Date
    May 2010
    Location
    North Central Illinois
    Posts
    1,631
    My Mood
    Sleepy
    Thanks
    390
    Thanked 112 Times in 110 Posts

    Default Re: Recursion

    Both these programs should have a main method that accepts the number ‘n’ as a command-line argument. That is, if I run your program from the command prompt, I should be able to enter a value of n as follows: java Binary 53
    What does that mean? Does he mean that I'm supposed to take it in like this:

    int n = console.nextInt();

    or, like I fear:

    make it part of args[] somehow?

    ---------------------------------

    What I want this program to do. I think I can figure out all parts except how to store the values, what to do with args[], and how to get it to print in the right order.

    1.) I want it to do something when 0 <= n <= 9;

    2.) I want int x to equal n and then make x = x /10;

    3.) I want it to store x%10.

    4.) I want it to store the value when 0<=x<=9. (or to be more specific, when x/10 = 0)

    5.) I want it to print the values, one per line;

    6.) The way I do it right now will likely print it backwards, so I'll probably need to reverse it.

    7.) Base cases
    a.) 0 <= n <= 9;
    prints n;
    exits method;

    b.) x/10 = 0;
    This should be the last value, but it'll be in reverse order unless I can figure out how to fix that.

    8.) Other cases: (Likely recursive here);

    a.) store value x%10;
    x = x / 10;

    b.) keep doing this till x/10 = 0;

    9.) It'd be nice if this could be done without using a second method to divide the value by 10
    and store the values until x/10 = 0;

    10.) n must be positive.
    Last edited by javapenguin; October 17th, 2010 at 06:09 PM.

  14. #11
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default Re: Recursion

    Ok, so another thing about recursion is a simpler problem shouldn't have any knowledge of the more complicated problem

    Your problem should fit into this general template:

    public String recurseNumber(int n)
    {
        if(/*TODO: test to see if base case is true*/)
        {
            return /* TODO: return the string which corresponds to the base case*/;
        }
        return /* TODO: reduce the problem. A simple way to do this is to divide your number by 10. This will remove the least significant digit.
            You will need to add on a "correction factor" to the result of the reduced problem. This factor would just be recurseNumber(n%10).*/;
    }

    Both these programs should have a main method that accepts the number ‘n’ as a command-line argument. That is, if I run your program from the command prompt, I should be able to enter a value of n as follows: java Binary 53
    Yes, this does indeed use args to get the number. However, I think this method is almost easier than asking the user for an input. Here's that statement disected:

    jave - This means you're running the JVM from the command line
    Binary - The name of your class
    53 - This is a parameter being passed to your program's main function. It is the first argument, so it would be located as a string at args[0]. How it gets passed isn't important, just know that it does.

    So, to use this information:

    public static void main(String[] args)
    {
        System.out.println("the first argument inputted is " + args[0]);
        int n = /*TODO: how do you get an integer from a string to an int? Hint: use the Integer wrapper class*/;
    }

  15. The Following User Says Thank You to helloworld922 For This Useful Post:

    javapenguin (October 18th, 2010)

  16. #12
    Banned
    Join Date
    May 2010
    Location
    North Central Illinois
    Posts
    1,631
    My Mood
    Sleepy
    Thanks
    390
    Thanked 112 Times in 110 Posts

    Default Re: Recursion

    For n = 1234;

    1234 /10 = 123

    123/10 = 12;

    12%10 = 2;

    123%10 = 3;

    1234%10 = 4;


    This code below will only get first value. Also, it's supposed to be printlns, never returning Strings, at least that I'm aware of.

    public void printLines(int n)
    {
     
    if (0 <= n <= 9)
    {
    System.out.println(n);
    return;
    }
     
     
     
     
     
    }
     
    else
    {
     
     
    printLines(n/10);
     
    }

    To get the other values, it'll have to print out:

    where n >=10. and n < =99

    n = 12;

    12%10 = 2;

    Then it'll have to go:

    n>=100 and n <= 999;

    123 % 10 = 3;

    Then it'll go

    n>=1000 and n <=9999

    1234%10 = 4;

    Doing this:

    System.out.println(n%10)
    printLines(n/10);

    Will get for 1234

    1234%10 = 4;
    4

    1234/10 = 123;

    123%10 = 3;

    123/10 = 12;

    12%10 = 2;

    12/10 = 1;

    prints 1;

    exits;

    4
    3
    2
    1

    That's what I want, but backwards.
    Last edited by javapenguin; October 18th, 2010 at 02:13 PM. Reason: Confused

  17. #13
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default Re: Recursion

    In general, you want your methods to have as few side-effects as possible. These include asking users for keyboard input and giving user screen output. Your methods should do something and return something that the rest of your code can use.

    In this case, it's a string. What you end up doing with that string (such as printing it out to the screen) should be independent of what the method is doing. There are some obvious exceptions to this rule, but I wouldn't consider this one of them (unless your professor specifically stated that you can't return a string and print it out later).

    That asside, analyze the way the recursion reduces the problem. It reduces it by removing the least significant digit, so you want to append the "correction factor" after you print out the solution of the simplified problem. Another thing I would recommend is changing all your println's to prints. This way your output is all on one line rather than having 1 number per line (unless that's an assignment requirement). printing it out as one string at the end fixes this problem automatically.

    printLines(n/10); // it's very important you have it in this order!
    System.out.print(n%10);
    // the same code as the above two lines if you're returning a string
    return printLines(n/10) + printLines(n%10); // Note: while the second call to printLines isn't necessary, I did it because it will make this code more "general".
    Last edited by helloworld922; October 18th, 2010 at 03:44 PM.

Similar Threads

  1. New Recursion problem need lil help
    By Delstateprogramer in forum Algorithms & Recursion
    Replies: 21
    Last Post: July 8th, 2010, 06:35 PM
  2. Recursion Help
    By vmr in forum Algorithms & Recursion
    Replies: 3
    Last Post: April 1st, 2010, 11:27 PM
  3. Converting a recursion to iteration
    By javaplus in forum Algorithms & Recursion
    Replies: 7
    Last Post: March 3rd, 2010, 04:38 PM
  4. Recursion help
    By rhoruns in forum Algorithms & Recursion
    Replies: 4
    Last Post: January 8th, 2010, 10:50 PM
  5. Problems with recursion
    By KingLane in forum Algorithms & Recursion
    Replies: 4
    Last Post: September 20th, 2009, 11:02 PM