Stackoverflow

Question

Hello, I wonder why I get the Stackoverflow error in this code, but if I add one more condition in the recursive method, that is if(list.contains(Numb)) I don’t get this error.

(This code would be to verify how many numbers exist in base 3 respecting the condition that from one digit D1 to one digit D2 there is the relation |D2-D1|<=2)

public static int recursive(int base,int numb,ArrayList<Integer> lista){
    inst=inst+1;
    if(numb<0 || numb>base-1) return 0;
    ArrayList<Integer> newArray=new ArrayList<Integer>(lista.size()+1); 
    for(int i=0;i<lista.size();i++)
        newArray.add(lista.get(i));
    newArray.add(numb);
    cont++;

    recursive(base,numb-2,newArray);
    recursive(base,numb-1,newArray);
    recursive(base,numb+1,newArray); 
    recursive(base,numb+2,newArray);
    return cont;
}

public static void main(String[] args){
    ArrayList<Integer> test=new ArrayList(11);
    int base=3;

    for(int i=1;i<11;i++){
        recursive(base,i,test);
    }
    System.out.println("Numeros validos "+ cont);
    System.out.println("Numero de instruções:"+inst);
}

Answer 1

The answer is very simple:

If you not check If a given number already exists in your list, your code will remain running recursively forever. And how recursive calls involve creating another item in the call stack, an hour the memory in your system runs out and gives the cited error - which literally translates as "overload" (overflow) of the "pile" (stack).

How can you see this happening? Just debug the code (even if mentally):

1. The first time recursive is called, the value of i is 1 (because it is at the very beginning of the loop in main), and thus the value of numb will also be 1.
2. This value is greater than 0 and less than 3, so ok, the process continues.
3. Ignoring the other calls (to facilitate), eventually the execution will arrive on the call with numb+1 (resulting in 2).
4. On that next call from recursive, the value of numb as 2 also goes through simple checks (it is greater than 0 and less than 3), so the process continues.
5. Ignoring the other calls (again, to facilitate), eventually the execution will arrive on the call with numb-1 (which becomes 1 again).

Thus, it should be possible to realize that this form of implementation has everything to go wrong and stay eternally running (in loop), unless you ignore calls to values that have already been processed (which is just add the condition you mention).