Recursividad en Java

Para comprender qué es la recursividad, es necesario comprender qué es la recursividad. De hecho, no hay nada difícil en comprender tales funciones; solo es necesario comprenderlas bien una vez. Y practica en lo que respecta a la programación. Recursividad en Java - 1

La recursividad ocurre no sólo en la programación, sino también en la vida real. Toma un espejo en tus manos y párate frente a otro espejo. El reflejo del reflejo se reflejará en el reflejo y así sucesivamente. Verás una infinidad de reflejos llegando al infinito. Puede encontrar más información sobre la recursividad "real" en el artículo " Dedicado al Día de la Marmota... " Volvamos del mundo real a la vida cotidiana de un programador. Definición simple: las funciones recursivas en Java son funciones que se llaman a sí mismas. Déjame darte un ejemplo muy simple y muy dañino:

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

¿Por qué es perjudicial? ¡Te sugiero que lo compruebes tú mismo! Si decides emprender esta aventura (¡y lo más probable es que lo hagas, programador!), escribe en los comentarios qué error arrojará la JVM =) Este ejemplo, y muchos otros, demuestran que el uso de la recursividad en Java debe abordarse con cuidado. . Debe comprender dónde, cuándo y por qué se justifica este enfoque para resolver un problema y asegurarse de que su función no convierta la ejecución del programa en el "Día de la Marmota". Hay dos definiciones más importantes para entender la recursividad:

Base recursiva : la condición para salir del bloque de llamadas recursivas: la solución básica al problema, en condiciones en las que no es necesario llamar a la recursividad.
El paso de recursividad es cuando una función se llama a sí misma al cambiar parámetros.

Un ejemplo clásico del uso de una función recursiva es calcular el factorial de un número. En caso de que lo hayas olvidado, déjame recordarte: el factorial de un número entero positivo N(denotado como N!) es el producto de números de 1 до N: N! = 1 * 2 * 3 * … (N - 1) * N. Por cierto, el factorial de cero por definición es igual a 1. Entonces, el factorial se puede encontrar para cualquier número entero positivo y cero (en el lenguaje de las matemáticas, para el conjunto de números enteros no negativos o para el conjunto de números naturales y cero). Creo que entiendes que puedes programar factorial usando bucles. En realidad, aquí hay un método no 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;
}

Agreguemos una verificación de que el número sea positivo y un número entero, y una verificación separada de cero.

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

Ahora daré el código del método para resolver este problema de forma recursiva:

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

Veamos los resultados de salida de las llamadas:

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

Obtenemos los valores esperados:

Agreguemos un buen resultado y calculemos el factorial para un número mayor:

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) + "!");

Obtenemos: 15 * 14 * 13 * 12 * 11 * 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 1 307 674 368 000! En este caso, el uso de una función recursiva está justificado y es seguro. Hemos definido claramente la condición para salir del bloque recursivo y estamos seguros de que se puede lograr: ingresamos un número entero no negativo, si el número es igual a cero o uno, devolvemos el resultado, si el número es mayor , multiplicamos el resultado por una función del número n-1. Usando el factorial de tres como ejemplo:

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

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

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

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

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

Respecto a la precaución de uso: ¿cuál es la vulnerabilidad de esta función? Si le da a un método un número negativo como parámetro, entonces la verificación

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

no tiene sentido y terminaremos en un ciclo interminable de llamarnos a nosotros mismos. Vale la pena agregar una verificación de no negatividad:

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

Y todo estará bien.

¿Cuál es la ventaja de un método sobre otro? No parece que haya una gran diferencia, pero de hecho, muchas llamadas recursivas tendrán un impacto negativo en el rendimiento y el consumo de memoria: la pila de llamadas es un recurso casi incontrolable y bajo diferentes condiciones para llamar a la misma función recursiva, Es posible que tengamos o no problemas asociados con este recurso. Casi todos los problemas resueltos mediante iteraciones (ciclos como for-each) también se pueden resolver de forma recursiva. La ventaja de la recursividad es la legibilidad y la facilidad de escritura; ya hemos hablado de las desventajas anteriores: la oportunidad de "pegarse un tiro en el pie" no es ilusoria. Debe tener aún más cuidado al utilizar la llamada "recursividad compleja": una función A()llamará a una función B()que llama a una función A(). Resolver este tipo de problemas requiere una comprensión completa de cómo funciona la recursividad. Un ejemplo de tal tarea: calcular el valor de x^n/(n!). El factorial, como comentamos anteriormente, se define sobre el conjunto de números enteros no negativos. Finalmente, daré el código de solución. La recursividad compleja constará de dos 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 ingresar a la recursividad se utiliza un método calculate, el cual llama a un método power, el cual a su vez llama a un método calculate. Definimos la base de recursividad en el método de potencia:

if (n == 1) return x;

El paso de recursividad también se define allí:

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

Queda por agregar una verificación de la validez de los datos de entrada:

Cualquier número distinto de cero es igual a la potencia de cero 1. Si n = 0entonces n! = 1. Necesito devolverlo 1.
Cero elevado a cualquier potencia es igual a cero.
No consideraremos la incertidumbre de tipo 0^0y aceptaremos dichos datos de entrada como no válidos.

Con todas las comprobaciones, los métodos quedarán así:

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

Bueno, al llamar a una función debes recordar detectar el error:

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

Comentarios

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