6
\$\begingroup\$

This was the exercise:

Exercise PSD

Think about a number under 25. Write down the number. If the number is even, divide in to two en write down the result below. If the number isn’t even (the number is odd) multiply the number with 3 and add 1. Write down this number. Repeat until the answer is 1. Write the code for this problem.

Example:

13    14
40    7
20    22
10    11
5     34
16    52
8     26
4     13
2     40
1     20
      10
      5
      16
      8
      4
      2
      1

How can I optimize this code? For example, is it possible to write it shorter or better performance?

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int i = sc.nextInt();
        PSD(i);
    }

    public static void PSD(int x) {
        if(x == 1){
            System.out.println(x);
        }
            else if (x % 2 == 0) {
            System.out.println(x);
                PSD((x / 2));
            } else {
            System.out.println(x);
                PSD((x * 3)+1);
            }
        }
    }
\$\endgroup\$
0

3 Answers 3

7
\$\begingroup\$

Printing in a Function

A function should really only be doing one thing. Yours calculates and prints. This makes it hard to reuse the function, and it also slows it down. Collect the result inside the function (ideally using a StringBuilder for performance reasons), return the result, and print it elsewhere.

Style

Your indentation is off, which makes your code hard to read. You can fix this easily with any IDE.

Duplication

Your else if and else blocks contain some duplication. You could calculate the value you pass to PSD in there, and call System.out.println and PSD outside, only once.

With these points, your code might look like this:

public static String PSD(int x, StringBuilder result) {
    if (x == 1) {
        result.append(x);
        return result.toString();
    }

    int value;
    if (x % 2 == 0) {
        value = x / 2;
    } else {
        value = (x * 3) + 1;
    }
    result.append(x);
    result.append("\n");
    return PSD(value, result);
}

Recursive Functions

Recursive functions generally perform worse than iterative approaches. An iterative approach might look like this:

public static String PSD(int x) {
    StringBuilder result = new StringBuilder();
    while (x != 1) {
        result.append(x);
        result.append("\n");
        if (x % 2 == 0) {
            x /= 2;
        } else {
            x = (x * 3) + 1;
        }
    }
    result.append(1);
    return result.toString();
}
\$\endgroup\$
5
  • \$\begingroup\$ I see! I didn't knew about the Stringbuilder. I guess I have to focus more on keeping my functions simple and let them do 1 specefic thing. Is there a reason why recursive functions perform worse than iterative? \$\endgroup\$
    – barthr2
    May 11, 2015 at 15:06
  • \$\begingroup\$ @Lozeputten Yes, definitely. Keeping functions simple leads to so much more readable and reusable code. StringBuilder is only relevant for performance, you can use + as well if performance isn't important (which will sometimes - like in this case - result in better looking code). Eg here, with + you would save quite a bit of lines and the argument, as you could simply do return x + "\n" + PSD(value); in the recursive example. \$\endgroup\$
    – tim
    May 11, 2015 at 15:09
  • \$\begingroup\$ Thank you for your explanation. Ur explanation was very clear and exactly what I needed. Thumbs up for you man! Thanks! \$\endgroup\$
    – barthr2
    May 11, 2015 at 15:22
  • 2
    \$\begingroup\$ Using recursion can also sooner or later cause a StackOverflowError \$\endgroup\$ May 11, 2015 at 15:57
  • \$\begingroup\$ Goes to show that style is subjective. To me the first code snippet looks worse than OPs code. Fiddling with strings and logic in one method, passing around strings as function arguments, etc. You did not separate two concerns: like OP you combine the logic with the formatting. The way you build up the string already determines the format in which it is outputted (unless the caller parses the string to unravel it again). The answer below by @t-fochtman returning an ArrayList of integers is much more elegant and leaves it up to the caller to format the output in any way. \$\endgroup\$ Jun 1, 2023 at 20:10
3
\$\begingroup\$

Your code has two scalability problems. The possible StackOverflowError from excessive recursion has already been mentioned, and the solution is to use a loop instead.

The other problem is that Collatz sequences can grow to unexpectedly large numbers. These are sometimes called "hailstone sequences" for that reason. Therefore, long would be a better choice than int.

\$\endgroup\$
2
\$\begingroup\$

Another Approach to the Collatz Sequence

In the implementation below we take advantage of the fact that when n starts the iteration as odd, n = (n * 3) + 1 will always result in an even n. It follows that we can execute n /= 2 every iteration because by the time we reach it, n is always even.

ArrayList

To add more variety to my implementation I thought I'd use the ArrayList container which has the notable benefit that add(...) runs in constant time.

import java.util.Scanner;
import java.util.ArrayList;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int i = sc.nextInt();
        for (int value : collatz(i)) 
            System.out.println(value);
    }

    public static ArrayList<Integer> collatz(Integer n) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        res.add(n);
        while (n != 1) {
            if (n % 2 == 1) {
                n = (n * 3) + 1;
                res.add(n);
            }
            n /= 2;
            res.add(n);
        }
        return res;
    }
}
\$\endgroup\$
1
  • \$\begingroup\$ +1 this code does what @tim said code should do (but failed to achieve in his own example): separate logic from printing. It very elegantly just returns an ArrayList of integers and leaves it entirely up to the caller to format the output in any way. \$\endgroup\$ Jun 1, 2023 at 20:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.