Turn a for loop into Recursion

user_15121032 0
Viewed 63

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;
    }
recursion for-loop list algorithm java
2 Answers

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).equals(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. This means you have to instantiate it again every time you want to call the method.

user_106876800

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:

  • Because Integer is an object, you should use method equals() to compare the values of two instances of Integer. By using double equals sign == you are checking whether two object references objects point at the same object in memory. And the code you've listed "seems to be working" only because you've tested it against the values that JVM caches integers in rage of byte, i.e. [-128,127] (for more information, you might have a look at this question). It will fail if you would pass let's say List.of(1, 1, 1, 180, 180) into it.

  • 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 element in the source list
    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;
    }
    // recursive case
    int currentInd = result.size() - 1; 
    
    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]
user_179499450
Related