Estoy aprendiendo el concepto de recursión en js, tengo una pregunta muy básica sobre el problema de devolución del código base.
function factorial(n) { if (n === 1) { return 1; } return n * factorial(n - 1); }Así que este es un ejemplo factorial simple de explicar la recursividad.
factoriales(5) = 120
Mi pregunta es, ¿por qué no devuelve 1 cuando n llega a 1? Después del retorno dentro de la instrucción if, ¿seguirá ejecutándose el segundo retorno? ¿Y si devuelve 1, el segundo retorno continúa ejecutándose y hará 5 * 1 para siempre (digamos que n llega a 5)?
Hice un pequeño ejemplo, agregando algunos registros. La indent de atributo se agregó para ayudar en la sangría de registros y para comprender mejor lo que sucede.
En llamadas recursivas (como en llamadas no recursivas), cuando la función externa llama a la función interna, las variables actuales se almacenan en algún lugar de la memoria (en una pila) y luego llaman a la función.
Cuando la función interna regrese, los valores serán restaurados.
Si ve los registros de mi ejemplo, el parámetro n disminuye el valor en cada llamada, pero se restauró después de que regresa la función interna.
Respondiendo a tus preguntas:
My question is, why it's not returning 1 when the n reaches 1?
n llega a 1 , la función devuelve 1 , pero ese resultado se aplicará en el factorial(2) , que en ese momento está esperando el resultado, y así sucesivamente. After the return inside the if statement, the second return will continue to run?
And if it return 1, the second return continue to run and it will do 5 * 1 forever (let's say n reaches 5)???
No. El n se multiplicará con el resultado de la próxima llamada (la llamada externa espera la llamada interna):
5 * factorial(4) 4 * factorial(3) 3 * factorial(2) 2 * factorial(1) 1 2 * 1 = 2 3 * 2 = 6 4 * 6 = 24 5 * 24 = 120 function factorial(n, indent) { if (!indent) indent = ''; console.log(indent+'BEGIN: factorial('+n+')'); if (n === 1) { console.log(indent+'END: factorial('+n+'): 1'); return 1; } let factorialNMinus1 = factorial(n - 1, indent + ' '); let result = n * factorialNMinus1 ; console.log(indent+'END: factorial('+n+'): ' + n + ' * ' + factorialNMinus1 + ' = ' + result); return result; } console.log('result = ' + factorial(5));Una buena manera de analizar la recursión es usar una situación simple y pensar cómo se desarrollará la recursión.
Digamos n = 3.
function factorial(n) { if (n === 1) { return 1; } return n * factorial(n - 1); } console.log(factorial(3));Entonces, sucederán las siguientes iteraciones:
fac(3) == 3 * fac(3-1) fac(3-1) == 3-1 * fac(2-1) fac(2-1) == 2-1 * 1 La condición que hace que la recursividad se desarrolle y comience a regresar es n == 1 , por lo que cuando eso suceda, la última llamada a la función devolverá 1 en lugar de volver a llamarse a sí misma.
Pero el resultado real será la suma de todas las operaciones devueltas: (3 * ((3-1) * ((2-1) * 1)))
Entonces, factorial(5) devuelve 120 porque: (5 * ((5-1) * ((4-1) * ((3-1) * ((2-1) * 1))))) == 120 .