Entonces, sé cómo funciona la recursividad, para simplificar, una función se llama a sí misma hasta que se cumple una condición. Ahora, estoy leyendo eloquentJavaScript , es genial. Explica la recursividad con el siguiente ejemplo:
function findSolution(target) { function find(current, history) { if (current == target) { return history; } else if (current > target) { return null; } else { return find(current + 5, `(${history} + 5)`) || find(current * 3, `(${history} * 3)`); } } return find(1, "1"); } console.log(findSolution(13)); // result: (((1 * 3) + 5) + 5)Ahora bien, esta función con la ayuda de la recursividad descubre cómo, a partir de 1, puedes obtener un número solo multiplicando por tres o sumando 5, si es posible. Si no, devuelve nulo, si coincide con el número, imprimirá los pasajes (historial), saliendo así de la recursividad.
Lo que no puedo entender es cómo puede adivinar la secuencia de sumar y multiplicar y hacer la ramificación. La función de búsqueda devuelve nulo si el número es mayor que el objetivo, devuelve el historial si es igual, intenta sumar 5 llamándose a sí mismo o multiplicar por 3 también llamándose a sí mismo. Por lo tanto, no debería poder adivinar el camino a 13, sino que funciona.
Javascript sabio, ¿cómo es esto posible?
Así es como lo explica
Para comprender mejor cómo esta función produce el efecto que buscamos, veamos todas las llamadas a find que se realizan al buscar una solución para el número 13.
find(6, "(1 + 5)") find(11, "((1 + 5) + 5)") find(16, "(((1 + 5) + 5) + 5)") too big find(33, "(((1 + 5) + 5) * 3)") too big find(18, "((1 + 5) * 3)") too big find(3, "(1 * 3)") find(8, "((1 * 3) + 5)") find(13, "(((1 * 3) + 5) + 5)") found!¿Cómo puede volver? por favor, ayúdame
Lo que puede faltar en su conocimiento es cómo se maneja la pila de memoria durante las recursiones. Hagámoslo paso a paso.
Vocación
find(1, "1")Esas variables están en la pila de memoria #0:
current es 1history es "1"target es 13Hace:
find(1 + 5, `(${"1"} + 5)`) || find(1 * 3, `(${"1"} * 3)`);Se intentará el primer operando... Así que
find(1 + 5, `(${"1"} + 5)`)Esas variables están en la pila de memoria #1:
current es 6history es "(1 + 5)"target es 13Hace:
find(6 + 5, `(${"(1 + 5)"} + 5)`) || find(6 * 3, `(${"(1 + 5)"} * 3)`); find(6 + 5, `(${"(1 + 5)"} + 5)`)Esas variables están en la pila de memoria #2:
current es 11history es "((1 + 5) + 5)"target es 13Hace:
find(11 + 5, `(${"((1 + 5) + 5)"} + 5)`) || find(11 * 3, `(${"((1 + 5) + 5)"} * 3)`); find(11 + 5, `(${"((1 + 5) + 5)"} + 5)`)Esas variables están en la pila de memoria #3:
current es 16history es "(((1 + 5) + 5) + 5)"target es 13Ahora llega a la condición
else if (current > target) { return null; } // That is: else if (16 > 13) { return null; }La pila de memoria n.º 3 se descarta y la pila de memoria n.º 2 se extrae, por lo que se evaluará el segundo operando:
current es 11history es "((1 + 5) + 5)"target es 13Ahora tenemos:
null || find(11 * 3, `(${"((1 + 5) + 5)"} * 3)`); ¿Consíguelo? Nunca intentamos el segundo operando todavía...
Continúe haciéndolo paso a paso de esta manera y anote los valores de las variables para cada paso de recurrencia. Cuando regrese, haga estallar una pila y continúe hasta que esté todo reventado.
También anote cuidadosamente quién es la persona que llama para cada paso de recursión para saber a dónde va el valor devuelto.