USACO Sample Java Recursion Problem (Walkthrough #1)

Programming at its essence is simply pattern recognition. Through hard work and consistency, it becomes easier. Today we will be solving a simple Java question step by step and hopefully by the end of it we will have learned something.

Today we will be solving the question at this link: https://cses.fi/problemset/task/1068

Weird Algorithm - CSES Problem Set

First and foremost, and in the following classes/blogs I expect this to be the standard; you should attempt to solve the problem first and then proceed with the solution. So, give it a shot. I use the USACO Guide IDE, which I recommend to anyone who is attempting to solve the question; however, any sufficient IDE will work too.

The question clearly outlines that we have an arbitrary number n, and that IF this number is even, then we divide the program by 2 and IF it is odd, then n is multiplied by 3 and then we add 1 to it. Then finally it claims to repeat this until n is 1. So, from the question statement, we have identified 3 things we need to fulfill:

1. If the program is even, divide the program by 2

2. If it is odd, n is multiplied by 3 and add 1 to it

3. Finally, n needs to reach 1 by repetition of the program

So, we have outlined 2 If statements, the need for recursion (because of the mentioning repetition of the program) and another if statement that is easy to overlook. We must consider if the program reaches 1, then it will end.

We have understood the problem and now we can code.

As mentioned previously, I am using the USACO Guide IDE. This is how it looks upon opening it. In the next blog I will explain everything that is presented/given here.

First, I copy my input from the question into the input of the IDE.

From there, I make sure I register my input. In this case, I only have one variable, so I only need to read one variable.

So far, it should look something like this. From here, we’ll start writing the logic of our code.

We need to implement a method to call again for recursion, so let's write that. Since we’re returning a number, the method will return an integer value. And since we will be needing that number from the input, we’ll set it as a parameter.

You should have something like this:

Now within the method, we need to write our 3 If statements first. First, we need to account for whether out input / of int a will equal 1, because if it does, the method cuts right there. After that, we will create a second if statement, accounting for whether the number is even or odd. You can check either one first, but I decided to check odd first. The way I did this was by using the logic behind what makes a number even or odd. A number is odd depending on whether the number is divisible by two, or in other words, has a reminder of 1 or 0. We use modulus of 2 of int a to find the remainder.

If the remainder is one, multiply a by 3 and add 1, ELSE (we don't need to check if the remainder is 0 because that is the only other thing it could be) divide by 2. And now since we’ve covered the 3 if statements, we just need to call the function within the remainder finding if statements (both in the if part and the else part) which takes care of our recursion. Finally, we call the function the main method, and we have a successful program!

Thank you so much, and I hope you guys found this helpful.