Recursion in Java Queue

Asked

Viewed 204 times

2

My teacher says it’s bad programming practice, passing the variable that interests us as a parameter of a recursive method, e.g.:

    int getMaior(Celula i, int maiorV)

He says it’s best 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 tried to do too:

    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 didn’t succeed. Thanks in advance!

java

  • Is this a queue or a list? Because the queue concept means to remove from the beginning and put at the end. If you are inspecting anything in between, then your problem is no longer a queue and degenerated into a list.

  • Also, your question is a little confused on one thing: Where is the code of the cell class?

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 recursion is a bad practice in your case is that it consumes space in the call stack. For lists of very long cells, this can end up causing a StackOverflowError. Even if it doesn’t, information about all cells is piled on the execution stack, while in the version with a loop, information from only one cell is kept in memory.

Another detail is that I emphasize that the concept of queue means to remove 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 queue concept and its implementation degenerates into a list. Using recursion instead of iteration doesn’t solve this problem, it 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 maximum.

If you for any reason really need to use recursion, 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 tail recursion, where the compiler or interpreter optimizes recursion by replacing it with an iteration (not Java, but let’s assume it was), in which case its original approach would be the best:

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);
}

Browser other questions tagged java

You are not signed in. Login or sign up in order to post.