1. Funciones recursivas, en términos sencillos, significa que la función misma se llama a sí misma...
Tales como: n!=n(n-1)!
Tu defines la función f(n)=nf(n-1)
Y f(n-1) es una función de esta definición. . esto es recursividad
2. Por qué utilizar la recursividad: el propósito de la recursividad es simplificar el diseño del programa y hacer que el programa sea más fácil de leer.
3. Desventajas de la recursividad: aunque las funciones no recursivas son muy eficientes, son difíciles de programar y tienen poca legibilidad. La desventaja de las funciones recursivas es que aumenta la sobrecarga del sistema, es decir, cada vez que se recurre, la memoria de la pila ocupa más espacio.
4. Condiciones para la recursividad: debe haber una declaración para completar la tarea y se deben cumplir los requisitos para la recursividad (reducir en lugar de divergir)
5. Avance recursivo:
1. Utilice la recursividad para calcular el factorial de n:
Análisis: n!=n*(n-1)*(n-2)...*1
public int dReturn(int n){ if(n==1){ return 1; else{ return n*dReturn(n-1);2. Utilice la función recursiva para calcular la acumulación de 1 a n: 1+2+3+4+..+n
public int dReturn(int n){ if(n==1){ return 1; else{ return n+dReturn(n-1); 3. Se requiere generar una secuencia: 1,1,2,3,5,8,11... (cada número es la suma de los dos números anteriores y se requiere una función recursiva)
Utilice la recursividad de Java para representar una función: F(n)=F(n-1)+F(n-2);F(0)=1;F(1)=1;
Análisis: X1=1; X2=1; X3=X1+X2;
public int F(int n){ if(n==1){ return 1 }si(n==2){ return }else{ return F(n-1)+F(n-2); } }4.Java utiliza un método recursivo para imprimir de forma inversa cada elemento en una matriz de enteros
public static void printAll(int index,int[] arr){ System.out.println(arr[index]); if(index > 0){ printAll(--index,arr); [] argumentos){ int[] arr={1,2,3,4,5}; printAll(arr.lenth-1,arr);5. Solución de programación: si una novilla da a luz una vaca cada año a partir del cuarto año después del nacimiento, ¿cuántas vacas hay en el enésimo año?
public static int ganado(int n){ if(n<=0){ return 0; }else if(n<=3){ return 1 }else{ return ganado(n-1)+ganado(n-3) ; } } public static void main(String[] args){ int n=10; System.out.println(n+"Habrá un total de "+ganado(n)+"vacas" después del año }¿Cuáles son los conceptos de recursividad, recursividad lineal y recursividad de cola?
Llamar a funciones recursivas en Java: encontrar el factorial de un número
No se considera el desbordamiento: generalmente sólo se puede calcular el factorial de 69...
Nota: ¡el factorial de 0 es 0! =1
La representación factorial de cualquier número natural n mayor que 1:
norte!=1×2×3×……×n
O n!=n×(n-1)!
Al buscar el factorial de 0 aparecerá una calculadora en línea, ¡que es muy útil! !
prueba de paquete;importar java.util.Scanner;clase pública DiGui {public static void main(String[] args) {// TODO Método generado automáticamente stubSystem.out.println("Ingrese un número entero:");Escaneo del escáner = nuevo Scanner(System.in);int x = scan.nextInt();int result = digui(x);System.out.println(result);}// Función recursiva public static int digui(int x){if(x <=0){return 1;}else{return x*digui(x-1);}}}Recursión: Un proceso o función tiene un método para llamarse a sí mismo directa o indirectamente en su definición o descripción. Generalmente transforma un problema grande y complejo en un problema más pequeño similar al problema original a resolver. Este caso ilustra claramente cómo la recursividad puede transformar un problema complejo en uno más pequeño de resolver. El siguiente es un pequeño ejemplo para ilustrar el principio de recursividad.
/*** @fileName Test.java* @description ??????????* @fecha 2012-11-25* @time 17:30* @author wst*/public class Prueba { static int multiplicar( int n) { int factorial; // ?? si ((n == 1) || (n == 0)) { factorial = n } else { factorial = n * multiplicar(n - 1); ; } public static void main(String[] args) { System.out.println(multiplicar(5)); Cuando se llama a una función, se crea espacio para sus variables en la pila de tiempo de ejecución. Las variables de la función llamada anteriormente permanecen en la pila, pero quedan ocultas por las variables de la nueva función y, por lo tanto, no se puede acceder a ellas.
La función en el programa tiene dos variables: parámetro n y variable local factorial. Los siguientes diagramas muestran el estado de la pila, con las variables actualmente accesibles en la parte superior. Todas las demás variables llamadas están sombreadas en gris para indicar que la función que se está ejecutando actualmente no puede acceder a ellas.
Supongamos que llamamos a la función recursiva con el valor 5. El contenido de la pila es el siguiente, con la parte superior de la pila en la parte inferior:
n multiplicar(n) factorial 5 multiplicar(5) 5*multiplicar(4) //Primera llamada 4 multiplicar(4) 4*multiplicar(3) //Segunda llamada 3 multiplicar(3) 3*multiplicar(2 ) //El tercera llamada 2 multiplicar(2) 2*multiplicar(1) //La cuarta llamada 1 multiplicar(1) 1 //La quinta llamada
A partir de la información anterior, se puede ver fácilmente cómo la recursividad minimiza gradualmente un problema para resolverlo. A partir de la llamada al método, los resultados factoriales se enviarán a la pila hasta que finalice la llamada al método y, finalmente, los resultados se devuelvan uno por uno. desde la parte superior de la pila. Después de sustituir uno por uno, el resultado es el siguiente:
n=1 1 devuelve 1 hacia arriba
n=2 2*multiplicar(1) devuelve 2*1=2 hacia arriba
n=3 3*multiplicar(2) devuelve 3*(2*1)=6 hacia arriba
n=4 4*multiplicar(3) devuelve 4*(3*(2*1))=24 hacia arriba
n=5 5*multiplicar(4) devuelve hacia arriba 5*(4*(3*(2*1)))=120
Nota: Porque multiplicar(1) o multiplicar(0) devuelve un valor de 1
Entonces hay 2*multiplicar(1)=2*1=2
Y como multiplicar(2) cumple la condición de recursividad, se puede transformar en 2*multiplicar(1) después de la recursividad.
Entonces hay 3*multiplicar(2)=3*(2*multiplicar(1))=3*(2*1)=6
Porque multiplicar(3) se puede reducir a 3*multiplicar(2) después de la recursividad
Entonces multiplicar(4)=4*multiplicar(3)=4*(3*multiplicar(2))=4*(3*(2*1))=24
Por analogía, multiplicar(5)=5*multiplicar(4)
Se puede reducir a 5*(4*multiplicar(3))=5*(4*3*(multiplicar(2)))=5*(4*(3*(2*1)))=120
Echemos un vistazo a la información del código de bytes:
prueba de clase pública extiende java.lang.Object{ prueba pública(); (int); Código: 0: iload_0 1: iconst_1 // Empuje la constante de tipo int 1 a la pila 2: if_icmpeq 9 // Compara dos valores de tipo int, si son iguales, salta a la posición 9, esto es || función 5: iload_0 //Esto se ejecuta cuando la primera condición no se cumple, cargando el valor de tipo int de la variable local 0 (empuja el valor de n a la pila) 6: ifne 14 //Comparar, si no, Si es igual a 0 , salte a la posición 14. Nota: Dado que la comparación predeterminada aquí es con 0, no es necesario insertar la constante 0 en la pila 9: iload_0 //Si no hay salto en ifne, cargue int desde la variable local 0 Escriba el valor (empuje el valor de n a la pila) 10: istore_1 //Almacene el valor de tipo int en la variable local 1 (el valor que aparece en la parte superior de la pila es el valor empujado a la pila por la variable local 0 y luego se almacena en la variable local 1) 11: goto 23 //Salto incondicional a la posición 23 14: iload_0 //Comparación en la posición 6, si no es igual a 0, ejecuta esta instrucción, carga el valor de tipo int de la variable local 0 (empuja el valor de n en la pila) 15: iload_0 //Carga el valor de tipo int de la variable local 0 (empuja el valor de n a la pila) 16: iconst_1 //Empuja la constante de tipo int 1 en la pila, la constante 1 es 1 de n -1 en el código 17: isub //Realizar operación de resta, n-1 18: invokestatic #2; //Método multiplicar:(I)I, llamar al método multiplicar 21: imul //Realizar operación de multiplicación, n * multiplicar(n - 1) 22: istore_1 // Will El valor de tipo int se almacena en la variable local 1, factorial=... 23: iload_1 // Carga el valor de tipo int de la variable local 1 (empuja el resultado de factorial a la pila) 24 : ireturn //El método devuelve public static void main( java.lang.String[]); Código: 0: getstatic #3 //Campo java/lang/System.out:Ljava/io/PrintStream; : invokestatic #2; //Método multiplicar:(I )I 7: invokevirtual #4; //Método java/io/PrintStream.println:(I)V 10: return }