Java Recursion - MDC

Asked

Viewed 659 times

2

How can I implement a counter in the code below to know how many recursive calls will happen to calculate the MDC of 14 and 18?

package Aula01;

import javax.swing.JOptionPane;

public class Exer01 {

    public static double mdc(double dividendo, double divisor) {
        if ((dividendo % divisor == 0)) {
            return divisor;
        } else {
            return mdc(divisor, (dividendo % divisor));
        }

    }

    public static void main(String[] args) {
        double n1;
        double n2;
        double resp;

        n1 = Double
                .parseDouble(JOptionPane.showInputDialog(null, "Digite o primeiro número ou -1 para sair do programa"));
        n2 = Double
                .parseDouble(JOptionPane.showInputDialog(null, "Digite o segundo número ou -1 para sair do programa"));

        while (n1 != -1 || n2 != -1) {
            resp = mdc(n1, n2);
            String result = String.format("%.0f", resp);
            JOptionPane.showMessageDialog(null, "O resultado do MDC é: " + result);
            System.exit(0);

        }

    }

}
java recursion

1 answer

4


First, I think you should read the n1 and n2 within the while, otherwise it doesn’t make much sense for you to ask the user that and the while would end up being equivalent to a if.

Second, what to use System.exit(0) is not good programming practice. Avoid using this.

Third, that the mdc is an operation that only makes sense with whole numbers, so it’s weird to use double for that reason.

Fourth, package names should always be in lower case letters, and therefore Aula01 would be called aula01.

Fifth, that it is not good practice to eat letters from the name of the variables, and therefore Exercicio01 it would be better if Exer01.

But now focusing on your doubt, there are several ways to do this. I list 5 of these forms below:

  • Static variable - It’s considered the simplest alternative. But it doesn’t work when you have multiple threads.

    package aula01;

import javax.swing.JOptionPane;

public class Exercicio01 {

    private static int contador = 0;

    public static int mdc(int dividendo, int divisor) {
        contador++;
        if (dividendo % divisor == 0) {
            return divisor;
        }
        return mdc(divisor, dividendo % divisor);
    }

    public static void main(String[] args) {
        while (true) {
            int n1 = Integer.parseInt(JOptionPane.showInputDialog(null,
                    "Digite o primeiro número ou -1 para sair do programa."));
            int n2 = Integer.parseInt(JOptionPane.showInputDialog(null,
                    "Digite o segundo número ou -1 para sair do programa."));
            if (n1 == -1 || n2 == -1) break;

            contador = 0;
            int resposta = mdc(n1, n2);
            JOptionPane.showMessageDialog(null,
                    "O resultado do MDC é: " + resposta +
                    "\n Ocorreram " + contador + " recursões.");
        }
    }
}

  • Thread-local variable - Similar to the above option, but slightly more complicated, it works when there are multiple threads.

    package aula01;

import javax.swing.JOptionPane;

public class Exercicio01 {

    private static final ThreadLocal<Integer> CONTADOR = new ThreadLocal<>();

    public static int mdc(int dividendo, int divisor) {
        CONTADOR.set(CONTADOR.get() + 1);
        if (dividendo % divisor == 0) {
            return divisor;
        }
        return mdc(divisor, dividendo % divisor);
    }

    public static void main(String[] args) {
        while (true) {
            int n1 = Integer.parseInt(JOptionPane.showInputDialog(null,
                    "Digite o primeiro número ou -1 para sair do programa."));
            int n2 = Integer.parseInt(JOptionPane.showInputDialog(null,
                    "Digite o segundo número ou -1 para sair do programa."));
            if (n1 == -1 || n2 == -1) break;

            CONTADOR.set(0);
            int resposta = mdc(n1, n2);
            JOptionPane.showMessageDialog(null,
                    "O resultado do MDC é: " + resposta +
                    "\n Ocorreram " + CONTADOR.get() + " recursões.");
        }
    }
}

  • Create a class to represent the output of the function also containing recursion data - Tends to complicate the use of the function a lot.

    package aula01;

import javax.swing.JOptionPane;

public class Exercicio01 {

    public static final class ResultadoMdc {
        private final int valor;
        private final int recursoes;

        public ResultadoMdc(int valor, int recursoes) {
            this.valor = valor;
            this.recursoes = recursoes;
        }

        public int getValor() {
            return valor;
        }

        public int getRecursoes() {
            return recursoes;
        }
    }

    private static ResultadoMdc mdc(int dividendo, int divisor, int recursoes) {
        if (dividendo % divisor == 0) {
            return new ResultadoMdc(divisor, recursoes);
        }
        return mdc(divisor, dividendo % divisor, recursoes + 1);
    }

    public static ResultadoMdc mdc(int dividendo, int divisor) {
        return mdc(dividendo, divisor, 0);
    }

    public static void main(String[] args) {
        while (true) {
            int n1 = Integer.parseInt(JOptionPane.showInputDialog(null,
                    "Digite o primeiro número ou -1 para sair do programa."));
            int n2 = Integer.parseInt(JOptionPane.showInputDialog(null,
                    "Digite o segundo número ou -1 para sair do programa."));
            if (n1 == -1 || n2 == -1) break;

            ResultadoMdc resposta = mdc(n1, n2);
            JOptionPane.showMessageDialog(null,
                    "O resultado do MDC é: " + resposta.getValor() +
                    "\n Ocorreram " + resposta.getRecursoes() + " recursões.");
        }
    }
}

  • Pass an additional parameter to the function representing a counter - Complicates the method signature. There are two ways to do this. One is by using int[] and the other is using AtomicInteger.

    With int[]:

    package aula01;

import javax.swing.JOptionPane;

public class Exercicio01 {

    public static int mdc(int dividendo, int divisor, int[] contador) {
        contador[0]++;
        if (dividendo % divisor == 0) {
            return divisor;
        }
        return mdc(divisor, dividendo % divisor, contador);
    }

    public static void main(String[] args) {
        while (true) {
            int n1 = Integer.parseInt(JOptionPane.showInputDialog(null,
                    "Digite o primeiro número ou -1 para sair do programa."));
            int n2 = Integer.parseInt(JOptionPane.showInputDialog(null,
                    "Digite o segundo número ou -1 para sair do programa."));
            if (n1 == -1 || n2 == -1) break;

            int[] contador = {0};
            int resposta = mdc(n1, n2, contador);
            JOptionPane.showMessageDialog(null,
                    "O resultado do MDC é: " + resposta +
                    "\n Ocorreram " + contador[0] + " recursões.");
        }
    }
}

    With AtomicInteger:

    package aula01;

import javax.swing.JOptionPane;
import java.util.concurrent.atomic.AtomicInteger;

public class Exercicio01 {

    public static int mdc(int dividendo, int divisor, AtomicInteger contador) {
        contador.increment();
        if (dividendo % divisor == 0) {
            return divisor;
        }
        return mdc(divisor, dividendo % divisor, contador);
    }

    public static void main(String[] args) {
        while (true) {
            int n1 = Integer.parseInt(JOptionPane.showInputDialog(null,
                    "Digite o primeiro número ou -1 para sair do programa."));
            int n2 = Integer.parseInt(JOptionPane.showInputDialog(null,
                    "Digite o segundo número ou -1 para sair do programa."));
            if (n1 == -1 || n2 == -1) break;

            AtomicInteger contador = new AtomicInteger(0);
            int resposta = mdc(n1, n2, contador);
            JOptionPane.showMessageDialog(null,
                    "O resultado do MDC é: " + resposta +
                    "\n Ocorreram " + contador.get() + " recursões.");
        }
    }
}

  • Eat lyrics? Go that’s a greedy algorithm

  • 1

    @Jeffersonquesado There are a lot of people I know who are quite greedy about variable names, but not about good practice.

  • I’m new in Java, you gave me a super class and clarified a lot! Thank you very much! I only have one question left: how to replace the system.out(0)? @Victorstafusa

  • @Anabeatrizaraujo in place of System.exit(0) you normally use break or return. In some cases, an exception may be made.

  • And why is System.Exit(0) not a good practice in programming? @Victorstafusa (I’m going to question you really, sorry kkk I’m having a lot of doubts on this list of exercises)

  • 3

    @Anabeatrizaraujo Because the System.exit(0) It’s the button to make the world end in the blink of an eye. He doesn’t ask you if you’re sure, he doesn’t let you save open files, he doesn’t care how many lawsuits would have to be orderly canceled, and he doesn’t give you any satisfaction about what happened. None of this, the result is just a sudden and instant death. [continue...]

  • 2

    [continuation...] In a simple project like yours, it is not problematic, but in large projects, where you have hundreds of classes doing a lot of things at the same time, just stick a System.exit(0) there in the middle for you to have all kinds of bug Reports, users swearing and programmers witch-hunting each other. I work with Java since 2003 and until today never I saw a single place where the System.exit(0) was a good thing to do or at least better than any alternative to it.

  • 4

    Guys, they don’t teach this in college haha! I get it now, thank you so much! <3 @Victorstafusa

Show 3 more comments

Browser other questions tagged java recursion

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