Factorial utilizando Recursión en Java

Estoy aprendiendo Java usando el libro Java: The Complete Reference. Actualmente estoy trabajando en el tema Recursión.

Tenga en cuenta que hay preguntas similares en stackoverflow. Los busqué pero no encontré la solución a mi pregunta. Estoy confundido con la lógica en el siguiente progtwig.

Si ejecuto el siguiente progtwig, produce la salida correcta, pero no entendí la lógica.

  • No entendí la lógica en la siguiente línea: resultado = hecho (n-1) * n;
  • De mi conocimiento, si pasamos el valor de n = 4 como se muestra en el progtwig a continuación,
  • Entonces, 3 * 4 se almacena en el resultado, es decir, 12.
  • De nuevo, se llama hecho (n-1). Entonces n se convierte en 3.
  • Luego, el 2 * 3 se almacena en el resultado reemplazando los 12 anteriores.
  • Creo que entendiste dónde estoy atrapado / confundido.

  • Gracias.

class Calculation { int fact(int n) { int result; if(n==1) return 1; result = fact(n-1) * n; return result; } } public class Factorial { public static void main(String args[]) { Calculation obj_one = new Calculation(); int a = obj_one.fact(4); System.out.println("The factorial of the number is : " + a); } } 

result es una variable local del método de fact . Por lo tanto, cada vez que se llama al método de hecho, el resultado se almacena en una variable diferente de la invocación de hecho anterior.

Entonces, cuando se invoca el hecho con 3 como argumento, puede imaginarse que su resultado es

  result3 = fact(2) * 3 result3 = result2 * 3 result3 = 1 * 2 * 3 

Primero debes entender cómo funciona el factorial.

Vamos a tomar 4! como ejemplo.

 4! = 4 * 3 * 2 * 1 = 24 

Simulemos el código usando el ejemplo anterior:

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

En la mayoría del lenguaje de progtwigción, tenemos lo que llamamos function stack . Es como una baraja de cartas, donde cada carta se coloca sobre la otra, y cada carta puede considerarse como una función. Así que, pasando el fact método:

Pila nivel 1: fact(4) // n = 4 and is not equal to 1. So we call fact(n-1)*n

Nivel de stack 2: fact(3)

Nivel de stack 3: fact(2)

Pila nivel 4: fact(1) // ahora, n = 1. por lo que devolvemos 1 de esta función.

devolviendo valores …

Nivel de stack 3: 2 * fact(1) = 2 * 1 = 2

Nivel de stack 2: 3 * fact(2) = 3 * 2 = 6

Nivel de stack 1: 4 * fact(3) = 4 * 6 = 24

así que tenemos 24.

Toma nota de estas líneas:

 result = fact(n-1) * n; return result; 

o simplemente:

 return fact(n-1) * n; 

Esto llama a la función en sí misma. Usando 4 como ejemplo,

En secuencia de acuerdo a las stacks de funciones ..

 return fact(3) * 4; return fact(2) * 3 * 4 return fact(1) * 2 * 3 * 4 

Sustituyendo resultados …

 return 1 * 2 * 3 * 4 = return 24 

Espero que entiendas el punto.

Aquí hay otra explicación de cómo funciona el cálculo factorial usando recursión .

Modifiquemos un poco el código fuente:

 int factorial(int n) { if (n <= 1) return 1; else return n * factorial(n - 1); } 

¡Aquí está el cálculo de 3! en detalles:

enter image description here

Fuente: RECURSION (Java, C ++) | Algoritmos y estructuras de datos

Tu confusión, creo, proviene del hecho de que piensas que solo hay una variable de result , mientras que en realidad hay una variable de result para cada llamada de función. Por lo tanto, los resultados antiguos no se reemplazan, sino que se devuelven.

ELABORAR:

 int fact(int n) { int result; if(n==1) return 1; result = fact(n-1) * n; return result; } 

Asumir una llamada al fact(2) :

 int result; if ( n == 1 ) // false, go to next statement result = fact(1) * 2; // calls fact(1): | |fact(1) | int result; //different variable | if ( n == 1 ) // true | return 1; // this will return 1, ie call to fact(1) is 1 result = 1 * 2; // because fact(1) = 1 return 2; 

Espero que esté más claro ahora.

Lo que ocurre es que la llamada recursiva misma da como resultado un comportamiento recursivo adicional. Si fueras a escribirlo, obtienes:

  fact(4) fact(3) * 4; (fact(2) * 3) * 4; ((fact(1) * 2) * 3) * 4; ((1 * 2) * 3) * 4; 
 public class Factorial { public static void main(String[] args) { System.out.println(factorial(4)); } private static long factorial(int i) { if(i<0) throw new IllegalArgumentException("x must be >= 0"); return i==0||i==1? 1:i*factorial(i-1); } } 

El punto clave que falta aquí es que la variable “resultado” es una variable de stack, y como tal, no se “reemplaza”. Para elaborar, cada vez que se llama a un hecho, se crea una variable NUEVA llamada “resultado” internamente en el intérprete y se vincula a esa invocación de los métodos. Esto contrasta con los campos de objeto que se vinculan con la instancia del objeto y no con una llamada de método específica

Aunque esto es antiguo, sigue apareciendo bastante bien en Google. Así que pensé en mencionar esto. Nadie mencionó verificar cuando x = 0 .

0! ¡y 1! both = 1.

Esto no se verifica con las respuestas anteriores, y causaría un desbordamiento de la stack, si se ejecutara el hecho (0). De todos modos solución simple:

 public static int fact(int x){ if (x==1 | x==0) return 1; return fact(x-1) * x; }// fact 

Una solución recursiva usando operadores ternarios.

 public static int fac(int n) { return (n < 1) ? 1 : n*fac(n-1); } 

En mi opinión, y esa es la opinión de alguien con conocimiento de nivel principiante de Java, sugeriría que n == 1 se cambie a n <= 1 o (n == 0) || (n == 1) porque el factorial de 0 es 1.

El correcto es:

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

Esto devolvería 1 para factorial 0. ¿Me cree? Lo he aprendido de la manera difícil. Solo por no mantener la condición para 0 no pudo despejar una entrevista.

Para entenderlo, debes declarar el método de la manera más simple posible y Martynas lo ha identificado el 6 de mayo:

 int fact(int n) { if(n==0) return 1; else return n * fact(n-1); } 

lea la implementación anterior y lo entenderá.

En mi humilde opinión, la clave para entender las acciones relacionadas con la recursividad es:

  1. En primer lugar, nos sumergimos en la stack de forma recursiva, y con cada llamada de alguna manera modificamos un valor (por ejemplo, n-1 en func(n-1); ) que determina si la recursión debe ir más y más.
  2. Una vez que recursionStopCondition se cumple (por ejemplo, n == 0 ), las recursiones se detienen, y los métodos hacen el trabajo real y devuelven los valores al método de la persona que llama en las stacks superiores, por lo tanto, burbujea en la parte superior de la stack.
  3. Es importante capturar el valor devuelto de la stack más profunda, de alguna manera modificarlo (multiplicando por n en su caso), y luego devolver este valor modificado hacia arriba de la stack. El error común es que el valor del marco de stack más profundo se devuelve directamente a la parte superior de la stack, por lo que se ignoran todas las invocaciones de métodos.

Sin duda, los métodos pueden hacer un trabajo útil antes de sumergirse en la recursión (desde la parte superior hasta la parte inferior de la stack), o en el camino de regreso.

no crees una variable más

resultado

simplemente

hecho de retorno (n-1) * n;

 class Calculation { int fact(int n) { int result; if(n==1) return 1; return fact(n-1) * n; } } 
 import java.util.Scanner; public class Factorial { public static void main(String[] args) { Scanner keyboard = new Scanner(System.in); int n; System.out.println("Enter number: "); n = keyboard.nextInt(); int number = calculatefactorial(n); System.out.println("Factorial: " +number); } public static int calculatefactorial(int n){ int factorialnumbers=1; while(n>0){ factorialnumbers=(int)(factorialnumbers*n--); } return factorialnumbers; } } 
 public class Factorial2 { public static long factorial(long x) { if (x < 0) throw new IllegalArgumentException("x must be >= 0"); if (x <= 1) return 1; // Stop recursing here else return x * factorial(x-1); // Recurse by calling ourselves } } 
 public class Factorial { public static void main(String[] args) { int n = 7; int result = 1; for (int i = 1; i <= n; i++) { result = result * i; } System.out.println("The factorial of 7 is " + result); } } 

Bueno, aquí está la lógica para encontrar factorial de un número usando recurrencia,

 static int factorialFunction(int n) { int result; if(n == 1) { return 1; } // here we are calling the recursion function result = factorialFunction(n - 1) * n; return result; } 

Mientras tanto, puede consultar este recurso para encontrar ejemplos sobre el factorial de un número utilizando la recursión.