I have a list of elements that I wanted to print out. The way it is gonna work is that when we read aloud the list [1,1,1,1,4,4,4], we most likely say four 1s and three 4s, instead of uttering each number one by one.

Method readAloud(List) should return a List.

For example:

• readAloud(List(1,1,1)) should return List(3,1).

• readAloud(List(-1,2,7)) should return List(1,-1,1,2,1,7).

• readAloud(List(3,3,8,-10,-10,-10)) should return List(2,3,1,8,3,-10).

• readAloud(List(3,3,1,1,3,1,1)) should return List(2,3,2,1,1,3,2,1).

As you can see, I have already done it. But how can I turn this code into recursion?

        List<Integer> answer = new ArrayList<>();
        int count=1;
        int prev_elt = xs.get(0);
        for(int i=1;i<xs.size();i  ){
            if (prev_elt == xs.get(i)){
                count  = 1;
            }
            else{
                answer.add(count);
                answer.add(prev_elt);
                prev_elt=xs.get(i);
                count=1;
            }
            if(i == xs.size()-1){
                answer.add(count);
                answer.add(prev_elt);
                prev_elt=xs.get(i);
                count=1;
            }

        }
        return answer;
    }

CodePudding user response：

It isn't needed to recurse on this, but you can do this:

public static void readAloud (List<Integer> xs, int ind){
    if(ind == xs.size()) return;
    if(ind == 0 || answer.get(answer.size() - 1) != xs.get(ind)) {
        answer.add(1);
        answer.add(xs.get(ind));
    }
    else{
        answer.set(answer.size() - 2, answer.get(answer.size() - 2)   1);
    }
    readAloud(xs, ind   1);
}

Make sure to add ans as a global variable, or pass it in as an argument.

CodePudding user response：

In order to implement this problem recursively, you need to maintain position in the source list (denoted as pos in the code below). It will be passed as a parameter and get incremented at each method call.

Every recursive implementation consists of two parts:

• Base case - that represents a simple edge-case (condition when recursion terminates) for which the outcome is known in advance. In for this task, the base case will represent a situation when the source list was discovered completely and position is equal to its size (invalid index).

• Recursive case - a part of a solution where recursive calls are made and where the main logic resides.

In the recursive case, we need to determine whether the value at the current position matches the previous value. And if it is the case, increment the resulting count, otherwise add the previous value to the resulting list and add a counter-element (having a value of 1) for the next value.

My suggestion if to hide actual details of recursive implementation by providing a convenience method that requires only one parameter - the source list. And that method will be invoked from the client code.

Also, convenience method treats the edge case with the empty source and simplifies the conditional logic of the recursive method adding the counter-value for the first element (no need to treat the case when previous element doesn't exist because the very recursive call will have the position parameter 1).

Note that it's highly advisable to make the scope of your variables as narrow as possible. The benefit of this basic recommendation is better memory consumption and more transparent code, which easier to debug and maintain. And in this case doesn't make sense to make the resulting list a global variable because you will not able to call the method multiple times (with different input) because the next result will override the previous. result list must be limited to the scope of method.

The implementation might look that:

public static List<Integer> readAloud(List<Integer> source) {
    List<Integer> result = new ArrayList<>();
    if (source.isEmpty()) { // early kill
        return result;
    }
    
    result.add(1); // adding the count for the first value
    return readAloud(source, result, 1);
}

private static List<Integer> readAloud(List<Integer> source, List<Integer> result, int pos) {
    if (pos == source.size()) { // base case
        result.add(source.get(pos - 1)); // adding the last value from the source list
        return result;
    }
    
    int currentInd = result.size() - 1; // recursive case
    
    if (source.get(pos - 1).equals(source.get(pos))) {
        result.set(currentInd, result.get(currentInd)   1); // incrementing the count
    } else {
        result.add(source.get(pos - 1)); // adding the previous value
        result.add(1); // adding the count for a new value
    }
    return readAloud(source, result, pos   1);
}

main() - demo

public static void main(String[] args) {
    System.out.println(readAloud(List.of(3, 3, 1, 1, 3, 1, 1)));
    System.out.println(readAloud(List.of(1, 1, 1, 180, 180)));
}

Output

[2, 3, 2, 1, 1, 3, 2, 1]
[3, 1, 2, 180]