Memoization with recursive method in java

问题:

I am working on a homework assignment, and I have completely exhausted myself. I'm new to programming, and this is my first programming class.

this is the problem:

Consider the following recursive function in Collatz.java, which is related to a famous unsolved problem in number theory, known as the Collatz problem or the 3n + 1 problem.

public static void collatz(int n) {
StdOut.print(n + " ");
if (n == 1) return;
if (n % 2 == 0) collatz(n / 2);
else            collatz(3*n + 1);}

For example, a call to collatz(7) prints the sequence 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 as a consequence of 17 recursive calls. Write a program that takes a command-line argument N and returns the value of n < N for which the number of recursive calls for collatz(n) is maximized. Hint: use memoization. The unsolved problem is that no one knows whether the function terminates for all positive values of n (mathematical induction is no help because one of the recursive calls is for a larger value of the argument).

I have tried several things: using a for loop, trying to count the number of executions with a variable incremented each time the method executed, and hours of drudgery.

Apparently, I'm supposed to use an array somehow with the memoization. However, I don't understand how I could use an array when an array's length must be specified upon initiation.

Am I doing something completely wrong? Am I misreading the question?

Here is my code so far. It reflects an attempt at trying to create an integer array:

public class Collatz2 {
public static int collatz2(int n)
{

    StdOut.print(n + " ");
    if (n==1) {return 1;}
    else if (n==2) {return 1;}
    else if (n%2==0) {return collatz2(n/2);}
    else {return collatz2(3*n+1);}

}



public static void main(String[] args)
{
    int N = Integer.parseInt(args[0]);
    StdOut.println(collatz2(N));

}
}

EDIT:

I wrote a separate program

public class Count {
   public static void main(String[] args) { 
        int count = 0;       

        while (!StdIn.isEmpty()) {
            int value = StdIn.readInt();
            count++;
        }

        StdOut.println("count is " + count);
    }
}

I then used piping: %java Collatz2 6 | java Count

and it worked just fine.

回答1:

Since you are interested in the maximum sequence size and not necessarily the sequence itself, it is better to have collatz return the size of the sequence.

private static final Map<Integer,Integer> previousResults = new HashMap<>();

private static int collatz(int n) {
    int result = 1;
    if(previousResults.containsKey(n)) {
        return previousResults.get(n);
    } else {
        if(n==1) result = 1;
        else if(n%2==0) result += collatz(n/2);
        else result += collatz(3*n + 1);
        previousResults.put(n, result);
        return result;
    }
}

The memoization is implemented by storing sequence sizes for previous values of n in Map previousResults.

You can look for the maximum in the main function:

public static void main(String[] args) {
    int N = Integer.parseInt(args[0]);
    int maxn=0, maxSize=0;
    for(int n=N; n>0; n--) {
        int size = collatz(n);
        if(size>maxSize) {
            maxn = n;
            maxSize = size;
        }
    }
    System.out.println(maxn + " - " + maxSize);
}

回答2:

The trick here is to write a recursive method where an argument is the value you want to "memoize". For instance, here is a version of a method which will return the number of steps needed to reach 1 (it supposes that n is greater than or equal to 1, of course):

public int countSteps(final int n)
{
    return doCollatz(0, n);
}

public static int doCollatz(final int nrSteps, final int n)
{
    if (n == 1)
        return nrSteps;

    final int next = n % 2 == 0 ? n / 2 : 3 * n + 1;
    return doCollatz(nrSteps + 1, next);
}

If you were to record the different steps instead, you'd pass a List<Integer> as an argument and .add() to it as you went through, etc etc.