recursividad básica comprensión

Question

public static void main (String[] args) 
{ 
    System.out.println(factorial(5)); 
} 

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

escribí lo anterior directamente en aquí así que no puede compilar pero piensa que lo hace.

¿Alguien puede explicar brevemente cómo funciona esto al decir que cómo se almacena? Empieza calculando 5 * (5-1), luego hasta 4 * (4-1) luego 3 * (3-1) ..... hasta que llegue a 1, que simplemente retornará 1 ¿verdad? lo siento por ser tan limitada simplemente estaría interesado en saber cómo esto funciona exactamente

gracias

pero a medida que trabaja hacia fuera - se pone los valores de las etapas individuales

5 * (5 -1) 4 * (4-1) ... ... ...

cómo se almacenan éstos y luego recuperado espalda o me estoy perdiendo algo?

Answer 1

Imagínate que eres el ordenador, y alguien le entrega un papel con

factorial(3) 

escrito en él. Luego ejecuta el procedimiento, mirando el argumento. Puesto que es> 1, se escribe

factorial(2) 

en otra hoja de papel y "mano a ti mismo", a la espera hasta que llegue la respuesta a esa pregunta antes de continuar.

Nuevamente ejecuta el procedimiento.Desde el 2 sigue siendo> 1 se escribe

factorial(1) 

en otra hoja de papel y la mano a sí mismo, a la espera hasta que llegue la respuesta a esta pregunta antes de continuar.

De nuevo, ejecuta el procedimiento. Esta vez, la entrada es 1, por lo que toma la primera rama y devuelve 1. La invocación que procesaba factorial (2) ahora tiene una respuesta, por lo que multiplica 2 por esa respuesta (1) y regresa. Ahora la invocación que maneja factorial (3) obtiene su respuesta (2) y la multiplica por 3, obteniendo 6. Luego devuelve esa respuesta a la persona que inició toda la operación.

Si imagina que guardó los pedazos de papel en una pila frente a usted mientras estaba trabajando, eso es una visualización de la "pila" en la memoria de la computadora. Cada invocación recursiva almacena el parámetro (y cualquier variable temporal) en su propia hoja de papel (estructura de pila) literalmente dispuesta como una pila de inserción al igual que los papeles, una encima de la otra.

Answer 2

.... luego 3 * (3-1) ..... hasta que llegue a 1, que simplemente devolverá 1 ¿verdad?

correcto, pero devuelve ese '1' a la penúltima invocación, que se multiplicará por dos, devolviendo '2' ... al siguiente-al-siguiente-último, que se multiplicará por tres .....

Answer 3

Sí, lo tienes bien en el código, primero comprueba el valor de n si es menor o igual a 1, que es lo que se conoce como tu caso base . Son importantes, le dicen a su función recursiva cuándo detenerse.

Si el valor de n no es menor que o igual, devuelve el valor de n multiplicado por la llamada recursiva de factorial pero con el valor n-1 arriba hasta que alcanza su caso base: if (n <= 1) donde vuelve 1

Su caso base fue configurado por la definición factorial de 0! y 1! que son ambos igual a 1.

Quizás este diagrama pueda ayudar a entender cómo funcionan las llamadas.

5 * fact(5-1) -> 
      4 * fact(4-1) -> 
        3 * fact(3-1) -> 
           2 * fact(1) 
             1 

¿Qué es la misma que 5! o 5 x 4 x 3 x 2 x 1

Espero que esto ayude.

Answer 4

¿Estás preguntando cómo funciona la recursividad internamente? La respuesta de una oración es que cada subproceso tiene una "pila de llamadas" y cada vez que se llama a un método, se inserta una nueva entrada en esta pila, que tiene información sobre qué método se llama y cuáles fueron los argumentos. Cuando el método finaliza, vuelve a colocar su valor de retorno en la misma pila y el método de llamada lo quita. Así que en su apogeo la pila se verá como

factorial (1) llamado por factorial (2) llamado por factorial (3) llamado por factorial (4) llamado por factorial (5)

El Wikipedia article en las pilas de llamadas parece bastante completo a primera vista.

Answer 5

1. En la llamada inicial a factorial, n = 5, y se coloca en la pila.
2. Luego, el otro se desencadena, por lo que 4 es pasado a factorial, y también es empujado a la pila.
3. Luego, el otro se desencadena por lo que 3 es pasado a factorial, y también es empujado a la pila.
4. Luego, el otro se desencadena por lo que 2 es pasado a factorial, y también es empujado a la pila.
5. Luego, el otro se desencadena por lo que 1 es pasado a factorial, y también es empujado a la pila.
6. Luego, el resto se desencadena por lo que 0 es pasado a factorial, y también es empujado a la pila.
7. If se activa y 1 es regresó al factorial de llamada.
8. If se activa y 2 * 1 es devuelto al factorial de llamada.
9. If se activa y 3 * 2 es regresó al factorial de llamada.
10. If se activa y 4 * 3 es regresó al factorial de llamada.
11. If se activa y 5 * 4 es devuelto al factorial de llamada.

La pila también se limpia, sin embargo, eso es demasiado tedioso para escribir. Esencialmente, todos los valores de una llamada a un método se insertan en la pila y se eliminan de la pila en la devolución de métodos. Esto los mantiene separados entre llamadas recursivas.

Answer 6

Es importante tener en cuenta que la "recursividad" funciona de manera diferente en java (un lenguaje de procedimiento) que en, por ejemplo, Haskell o F # (idiomas funcionales).

En Java cuando invocamos la recursión lo hacemos evaluando el árbol de expresiones y resolviendo cada parte de él hasta que determinemos el valor de cada parte de la expresión. Si necesitamos invocar otra función, colocamos un marcador de posición para todos los valores intermedios en ese punto y luego comenzamos a construir un nuevo árbol de expresión para la nueva función.

En el caso de recursividad, lo que estamos haciendo es hacer una llamada a la misma función, con suerte con diferentes valores de terminación, que debe resolverse antes de que podamos completar la evaluación de la expresión actual. Estas expansiones están encadenadas juntas hasta que ocurre una de estas dos cosas 1) Llegamos a una expresión de terminación que devuelve el control a la persona que llama (la primera parte de su si en este caso), o agotamos nuestra capacidad de almacenar valores intermedios y devolver una excepción (desbordamiento de pila).

En el primer caso, comenzamos resolviendo cada uno de los árboles de expresión de la parte superior de la pila, trabajando hacia atrás hasta que no quedan entradas de pila, en cuyo punto el árbol de expresión se resuelve en el valor final.

La respuesta de Jim es una excelente metáfora física para esto.

Answer 7

Es difícil de adivinar exactamente qué parte de la recursividad que está teniendo dificultad con, pero voy a ir fuera de esta parte de su pregunta:

hasta que se pone a 1, que acaba de regresar 1 ¿derecho?

supongo que quiere decir, "si se acaba de regresar 1, ¿por qué es el resultado de la función no 1?"

Tenga en cuenta que cuando regrese de una función (en este caso, factorial) está devolviendo un valor a quien originalmente lo solicitó.

Si digo "me dan factorial (5)", entonces factorial (5) me va a devolver un valor, pero antes de que me puede devolver el valor que tiene que pedir factorial (4) por su valor, factorial (5) dice esencialmente "dame factorial (4) para poder multiplicarlo por 5 y dárselo al tipo que pidió factorial (5)". Ahora factorial (4) devolverá su valor a factorial (5) que puede multiplicarlo por n y devolver su valor a mí. Recuerde, I no solicitó el valor factorial (4), ni siquiera me importa, y no regresó a mí, volvió a factorial (5).

En el momento en que golpee factorial (1) tendrá factoriales (2), factoriales (3), factoriales (4) y factoriales (5) esperando para obtener una respuesta. Factorial (1) devolverá su valor (que es 1, debido a su caso base) a factorial (2), que finalmente puede regresar a factorial (3) y así sucesivamente, en ese punto la recursión se completará y usted recupera el valor de Factorial (5).

Answer 8

Un enfoque práctico que requiere un buen IDE (Eclipse, NetBeans, IntelliJ):

Añadir un punto de interrupción en la línea que dice return 1 y depurar la aplicación. Cuando se detiene, mira el rastro de la pila. Verás que el método factorial ha sido llamado varias veces.

La vista de depuración de eclipse muestra el hilo suspendido y una pila con seis entradas, cada línea representa una línea de código donde se llama otro método (excepto la entrada superior, que es el punto de corte). factorial aparece cinco veces, puede seleccionar cada línea y ver el valor de n en la vista Variable (esto es básico y debería funcionar en el otro IDE de forma similar).

que debe dar otra idea de cómo método recursivo llamadas de trabajo (y por qué recibe un error de falta de memoria cuando no se definen los criterios de salida adecuadamente;))