Optimize Collatz conjecture

Question

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);
            }
        }
    }

Answer 1

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();
}

Answer 2

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.

Answer 3

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