How to break the recursion

Question

In below code, I am able to get the required answer where I am removing smaller number than its previous index and next index. However along with the answer also i am encountering the error- Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 4, Size: 4 Need help in identifying how to break recursion here. Thanks in advance.

public class numberProblem {

public static void main(String[] args) {
    ArrayList<Integer> list = new ArrayList<>();
    list.add(10);
    list.add(3);
    list.add(20);
    list.add(5);
    list.add(30);
    list.add(20);
    list.add(60);
    
    int len = list.size();
    System.out.println(list);
    testList(list, len);
}
    
public static void testList(ArrayList<Integer> list, int len) { 
    
    
    System.out.println("Len is:"+len);
    System.out.println(list.size());
    ArrayList<Integer> l = list;
    len= l.size();
    
    for(int i= 1;i<=len-1;i++) {
        
        if(l.get(i)<l.get(i-1) && l.get(i)<l.get(i+1)) {
            l.remove(i);
            testList(l, l.size());  
        }
        
    }
    
    System.out.println(list);   
    
}

}

You might want to look at https://stackoverflow.com/questions/40480/is-java-pass-by-reference-or-pass-by-value. `ArrayList l = list;` is not doing what you think it does. — Progman, Jun 28 '20 at 15:43
Whenever you ask a question like this, you should post the input along with the EXPECTED OUTPUT. — Idle_Mind, Jun 28 '20 at 16:28

score 0 · Answer 1 · answered Jun 28 '20 at 15:38

Here is the solution without recursion.

public static void numberList(ArrayList list){ int original = list.size();

    while(true){        
        for(int i = 0, j = 0, k = 0; k < list.size() - 1; ){
            j = i + 1;
            k = j + 1;
            if(list.get(j) < list.get(i) && list.get(j) < list.get(k)){
                list.remove(j);
            } else {
                i++;
            }
        }
        
        if(list.size() < original){
            original = list.size();
        } else {
            System.out.println(list);
             break;
        }
    }
}

score 0 · Accepted Answer · answered Jun 28 '20 at 16:24

Instead of passing the length of the list, pass the current index that you should be checking. Then you can get rid of the for loop since the recursion does the "looping" for you. You stop recursion when you are at the second to last element in the list, since there cannot be a value afterwards to compare with. Similarly, you start recursion at the second element since the first element doesn't have an element before it to compare with. Whenever you remove an element, your recursive call will use the SAME index value so that the position will be compared again. This is necessary since all the other elements will have shifted down after the removal. If nothing was removed, then the recursive call will pass the current index plus one:

import java.util.ArrayList;
public class numberProblem
{

    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        list.add(10);
        list.add(3);
        list.add(20);
        list.add(5);
        list.add(30);
        list.add(20);
        list.add(60);       

        System.out.println("Before:");
        System.out.println(list);
        
        testList(list, 1); // start at the 2nd position since the first value can't have a smaller value before it
        
        System.out.println("After:");
        System.out.println(list);
    }
    
    public static void testList(ArrayList<Integer> list, int index) {            
        if (index>0 && index<(list.size()-1))
        {
            int value = list.get(index);
            if(value<list.get(index-1) && value<list.get(index+1)) {
                list.remove(index);            
                index--; // need to check the same index on next recursive call since everything will shift after removal above
            }   
            testList(list, ++index);
        }        
    }
    
}

Output:

Before:
[10, 3, 20, 5, 30, 20, 60]
After:
[10, 20, 30, 60]

Thanks RiddhiK and @Idle_Mind, it helped!! – Ravi Kakadia Jun 29 '20 at 04:24 — Ravi Kakadia, Jun 29 '20 at 04:24

How to break the recursion

2 Answers2