Recursão em Java

Para entender o que é recursão, você precisa entender o que é recursão. Na verdade, não há nada difícil em entender tais funções, você só precisa entendê-las bem uma vez. E pratique quando se trata de programação. Recursão em Java - 1

A recursão ocorre não apenas na programação, mas também na vida real. Pegue um espelho nas mãos e fique na frente de outro espelho. O reflexo do reflexo será refletido no reflexo e assim por diante. Você verá um número infinito de reflexos indo até o infinito. Você pode encontrar mais sobre recursão “real” no artigo “ Dedicated to Groundhog Day... ” Vamos voltar do mundo real para a vida cotidiana de um programador. Definição simples: funções recursivas em java são funções que chamam a si mesmas. Deixe-me dar um exemplo muito simples e muito prejudicial:

public void recursionFucn() {
    System.out.println("Привет, JavaRush!");
    recursionFucn();
}

Por que é prejudicial? Eu sugiro que você verifique você mesmo! Se você decidir embarcar nesta aventura (e provavelmente o fará, seu programador!), escreva nos comentários qual erro a JVM lançará =) Este exemplo, e muitos outros, demonstram que o uso de recursão em Java deve ser abordado com Cuidado. Você precisa entender onde, quando e por que tal abordagem para resolver um problema se justifica, e garantir que sua função não transforme a execução do programa no “Dia da Marmota”. Existem duas definições mais importantes para entender a recursão:

Base de recursão - condição para sair do bloco de chamadas recursivas - a solução básica do problema, em condições em que não há necessidade de chamar recursão.
A etapa de recursão ocorre quando uma função chama a si mesma ao alterar parâmetros.

Um exemplo clássico de uso de função recursiva é calcular o fatorial de um número. Caso você tenha esquecido, deixe-me lembrá-lo: o fatorial de um número inteiro positivo N(denotado como N!) é o produto dos números de 1 до N: N! = 1 * 2 * 3 * … (N - 1) * N. A propósito, o fatorial de zero por definição é igual a 1. Portanto, o fatorial pode ser encontrado para qualquer número inteiro positivo e zero (na linguagem da matemática - para o conjunto de inteiros não negativos ou para o conjunto de números naturais e zero). Acho que você entende que pode programar fatorial usando loops. Na verdade, aqui está um método não recursivo para resolver este problema:

private int fact(int n) {
    int result = 1;
    for (int i = 1; i <= n; i++) {
        result = result * i;
    }
    return result;
}

Vamos adicionar uma verificação de que o número é positivo e um inteiro, e uma verificação separada de zero.

private int fact(int n) {
    if (n < 0) {
        System.out.println("Зачем тебе факториал из отрицательного числа?");
         return null;
    }
    int result = 1;
    if (n == 0) {
        return result;
    }
    for (int i = 1; i <= n; i++) {
        result = result * i;
    }
    return result;
}

Agora darei o código do método para resolver recursivamente este problema:

private int factorial(int n) {
    int result = 1;
    if (n == 1 || n == 0) {
        return result;
    }
    result = n * factorial(n-1);
    return result;
}

Vejamos os resultados de saída das chamadas:

System.out.println(factorial(0));
System.out.println(factorial(1));
System.out.println(factorial(2));
System.out.println(factorial(3));
System.out.println(factorial(4));
System.out.println(factorial(5));
System.out.println(factorial(6));

Obtemos os valores esperados:

Vamos adicionar uma boa saída e calcular o fatorial para um número maior:

private int factorial(int n) {
    int result = 1;

    if (n == 0) {
        System.out.print(" = ");
        return result;
    }
    if (n == 1) {
        System.out.print(" * 1 = ");
        return result;
    }

    System.out.print(n);
    if (n != 2) {
        System.out.print(" * ");
    }

    result = n * factorial(n-1);
    return result;
}


System.out.println(factorial(15) + "!");

Obtemos: 15 * 14 * 13 * 12 * 11 * 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 1 307 674 368 000! Neste caso, o uso de uma função recursiva é justificado e seguro. Definimos claramente a condição para sair do bloco recursivo e temos certeza de que isso é alcançável: inserimos um número inteiro não negativo, se o número for igual a zero ou um, retornamos o resultado, se o número for maior , multiplicamos o resultado por uma função do número n-1. Usando o fatorial de três como exemplo:

factorial(3) внутри себя выполнит следующее:
	result = 3 * factorial(2); (рекурсивный вызов)

	factorial(2) внутри себя выполнит следующее:
		result = 2 * factorial(1); (рекурсивный вызов)

		factorial(1) вернет 1 (базис рекурсии)

	factorial(2) вернет 2 * 1

factorial(3) вернет 3 * 2 * 1

Quanto ao cuidado no uso: qual a vulnerabilidade desta função? Se você der a um método um número negativo como parâmetro, então a verificação

if (n == 1 || n == 0) {
    return result;
}

não faz sentido e terminaremos em um ciclo interminável de chamadas a nós mesmos. Vale a pena adicionar uma verificação de não negatividade:

if (n < 0) {
	System.out.println(«Зачем тебе факториал отрицательного числа?»);
	return null;
}

E tudo ficará bem.

Qual é a vantagem de um método sobre outro? Não parece haver uma grande diferença, mas na verdade muitas chamadas recursivas terão um impacto negativo no desempenho e no consumo de memória: a pilha de chamadas é um recurso quase incontrolável e sob condições diferentes para chamar a mesma função recursiva, podemos ou não ter problemas associados a este recurso. Quase todos os problemas resolvidos usando iterações (ciclos como for-each) também podem ser resolvidos recursivamente. A vantagem da recursão é a legibilidade e facilidade de escrita; falamos das desvantagens acima: a oportunidade de “dar um tiro no pé” não é ilusória. Você precisa ter ainda mais cuidado ao usar a chamada “recursão complexa": uma função A()chamará uma função B()que chama uma função A(). Resolver esses problemas requer um entendimento completo de como funciona a recursão. Um exemplo de tal tarefa: calcular o valor de x^n/(n!). O fatorial, como discutimos acima, é definido no conjunto de inteiros não negativos. Por fim, darei o código da solução. A recursão complexa consistirá em dois métodos:

private double calculate(int x, int n) {
    return power(x, n) / n;
}
private double power(int x, int n) {
    if (n == 1) return x;
    return x * calculate(x, n - 1);
}

Para entrar na recursão é usado um método calculate, que chama um método power, que por sua vez chama um método calculate. Definimos a base de recursão no método de potência:

if (n == 1) return x;

A etapa de recursão também é definida lá:

return x * calculate(x, n - 1);

Resta adicionar uma verificação da validade dos dados de entrada:

Qualquer número diferente de zero é igual à potência de zero 1. Se n = 0então n! = 1. Precisa devolvê-lo 1.
Zero elevado a qualquer potência é igual a zero.
Não consideraremos a incerteza de tipo 0^0e aceitaremos tais dados de entrada como inválidos.

Com todas as verificações, os métodos ficarão assim:

private double calculate(int x, int n) throws ArithmeticException {
    if (x == 0 && n == 0) {
        throw new ArithmeticException("Невалидные входные данные: Неопределенность типа 0^0");
    }

    if (n < 0) {
        throw new ArithmeticException("Невалидные входные данные: Факториал из отрицательного числа!");
    }

    if (n == 0) {
        return 1;
    }

    if (x == 0) {
        return 0;
    }

    if (x == 0) {
        return 0;
    }
    return power(x, n) / n;
}

private double power(int x, int n) {
    if (n == 1) return x;
    return x * calculate(x, n - 1);
}

Bem, ao chamar uma função você precisa se lembrar de capturar o erro:

try {
    System.out.println(calculate(x, n));
} catch (ArithmeticException e) {
    System.out.println(e.getMessage());
}

Comentários

TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION