La recursión es una técnica de programación en la que divide sucesivamente un problema en partes más pequeñas y luego llama a ese mismo código para resolver sucesivamente esos subproblemas. La recursión es una de las principales formas en que perseguimos la estrategia de dividir y conquistar que es efectiva al resolver problemas grandes y complejos.
Una metáfora de la recursividad es cómo funciona la buena gestión organizacional en las empresas. Se basa en la delegación, no en superhéroes o microgestión . Lo que no desea es que una sola persona intente resolver cada problema por sí misma, esto podría funcionar para pequeños problemas, pero eventualmente esa persona se siente abrumada.
En cambio, los grandes gerentes podrían hacer esto:
- Cómo desarrollar autointeligencia para la codificación de software sin hacer algoritmos
- ¿Es c * O (n) = O (n) verdadero?
- ¿Cuáles son los mejores algoritmos de selección de apareamiento en informática evolutiva?
- ¿Es la composición musical un problema NP?
- Cómo resolver el problema M_SEQ en SPOJ
- Pregunte “¿Es este problema lo suficientemente pequeño como para que yo pueda resolverlo de manera eficiente? ”
- Si es así, resuelva el problema inmediatamente (¡sin molestar al equipo!).
- De lo contrario (si es demasiado complejo para 1 persona), involucre al equipo para resolverlo juntos:
- Divide el problema en piezas más pequeñas que se puedan resolver de forma independiente,
- Delega esos subproblemas a los miembros del equipo,
- A medida que terminen su trabajo, intégrelo en una solución general.
- De cualquier manera, devuelva la solución (independientemente de cómo se resolvió el problema).
Hay algunas cosas a tener en cuenta aquí:
- ¡Lo que funciona bien para los altos directivos también puede funcionar bien para el resto de nosotros! Los miembros del equipo que tienen delegada una subtarea pueden seguir este mismo sistema.
- Cuando los miembros del equipo completan las tareas que les delegaste, no sabes hasta qué punto los resolvieron solos, en lugar de delegar más , y realmente no debes preocuparte (todo lo que importa es que el trabajo se haya realizado).
- Por el contrario, cuando recibe una tarea para completar, no necesariamente sabe si se le ha delegado una parte de un problema mayor, o si este es un problema original y específico en sí mismo (de cualquier manera, resolverá usando el mismo método …)
- El sistema no funciona si el gerente intenta hacer todo (no ser un superhéroe ). Tampoco funciona si el administrador no delega limpiamente los problemas más pequeños (no sea un microgerente ). Finalmente, el sistema no puede funcionar si el gerente no hace ningún trabajo (¿me atrevo a decir “pelo puntiagudo” ?): Para tareas demasiado grandes para resolver por sí solo, todavía necesita agregar un poco valor antes de delegar.
Bien, cambiemos de marcha, de metáfora a código.
En general, la recursión exitosa requiere estos pasos:
- Definición de un caso base: ¿cuál es el problema que puede resolver usted mismo?
- De lo contrario, divida el problema en piezas más pequeñas y más solucionables, o cree una cierta cantidad de Avance progresivo.
- Ahora vuelva a llamar a usted mismo (Llamada recursiva) para resolver los problemas más pequeños, como si se tratara de solicitudes originales del mismo código que lo llamó.
- Haga lo que sea necesario para la integración o limpieza una vez que regresen las llamadas recursivas.
Aquí hay un poco de código para mostrar estas diferentes piezas:
// Ejemplo de función recursiva
// Dados los índices 1,2,3,4,5,6, … deberíamos devolver 1,1,2,3,5,8, …
función fibonacciValue (fibIndex)
{
// 1: Caso base: es bastante fácil para mí devolver la respuesta ahora mismo.
if (fibIndex <= 2) {
retorno 1;
}
más {
// 2: Avance progresivo: acerca los problemas más pequeños a los casos base
// Ejemplo: sabemos que cada fibVal es la suma de dos fibVals anteriores.
// 3: Tenga en cuenta las llamadas recursivas: ¡nuestro código se llama a sí mismo!
const prevFibVal = fibonacciValue (fibIndex – 1);
const prevPrevFibVal = fibonacciValue (fibIndex – 2);
// 4: juntar las piezas y devolver una respuesta
volver prevFibVal + prevPrevFibVal;
}
}
// ¿Podemos _realmente_ saber si fuimos originalmente llamados, versus
// ser llamado por nosotros mismos? Realmente no. (¿Estamos en la matriz?)
// (Sí, codifique golfistas, me doy cuenta de que podríamos hacer esto en una línea)
