Thread: Recursion

Originally Posted by Darryl.Burke

Are you aware of the modulo, aka remainder operator % ?
Assignment, Arithmetic, and Unary Operators (The Java™ Tutorials > Learning the Java Language > Language Basics)

db

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?

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;

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

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

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.

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.

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

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.

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