Recursion in Java Queue

Question

Recursion in Java Queue

Navigation

#1 by (1 votes)

2

My teacher says that it is a bad programming practice, passing the variable that interests us as a parameter of a recursive method, eg:

    int getMaior(Celula i, int maiorV)

It says that it is better to do the following method:

    public int getMaior(){
        return getMaior(primeiro.prox);
    }

    public int getMaior(Celula i){


        if(i!=null){

            if(i.elemento>maior) maior= i.elemento ; 
            maior=getMaior(i.prox);
        }

        return maior;
    }

However, if the largest variable is not global, this method does not work.

I've also tried doing:

    public int getMaior(){
        return getMaior(primeiro.prox);
    }

    public int getMaior(Celula i){
        int maior=Integer.MIN_VALUE;

        if(i!=null){

            if(i.elemento>maior) maior= i.elemento ; 
            maior=getMaior(i.prox);
        }

        return maior;
    }

And I was not successful. Thanks in advance!

java

asked by anonymous 19.06.2018 / 15:01

1 answer

Problems developing a bricks-breaking game in tkinter (collisions with objects) Drop-down menu with bootstrap

score 1 · Answer 1

Use a loop for this instead of recursion:

public int getMaior() {
    int maior = Integer.MIN_VALUE;
    if (primeiro == null) return Integer.MIN_VALUE;

    for (Celula i = primeiro; i != null; i = i.prox) {
        int v = i.elemento;
        if (v > maior) maior = v;
    }

    return v;
}

The reason for recursion being a bad practice in your case is that it consumes space on the call stack. For very long cell lists, this may end up causing StackOverflowError . Even if it does not, information about all cells is piling up in the execution stack, whereas in the version with a loop, only one cell information is kept in memory.

Another detail is that I emphasize that the concept of queue means to withdraw from the beginning and put in the end and nothing else. If you are inspecting anything in between to find the biggest element then you are violating the concept of queuing and its implementation degenerates into a list. Using recursion instead of iteration does not solve this problem, just leaves it more hidden.

Finally, global variable is always a bad programming practice (remembering that variable and constant are different concepts). Avoid global variables to the max.

If you really need to use recursion for any reason, then do so:

public int getMaior(Celula i) {
    if (i == null) return Integer.MIN_VALUE;
    int maior = getMaior(i.prox);
    int v = i.elemento;
    return v > maior ? v : maior;
}

In programming languages that have a recursion of the tail, where the compiler or interpreter optimizes recursion by replacing it with an iteration (not Java, but supposing it to be), in which case its original approach would be to better:

public int getMaior(Celula i) {
    return getMaior(i, Integer.MIN_VALUE);
}

private int getMaior(Celula i, int maior) {
    if (i == null) return maior;
    int v = i.elemento;
    return v > maior ? getMaior(i.prox, v) : getMaior(i.prox, maior);
}