¿Te cuesta entenderlo conceptualmente o te desconcierta la mecánica de la recursividad? ¿O ambos?
Conceptualmente
The Little Schemer es un excelente libro de enseñanza sobre el tema de la recursividad. Es muy accesible, habiendo sido
- ¿Los investigadores que elaboran algoritmos útiles ganan mucho dinero cuando sus algoritmos se aplican ampliamente en la industria?
- ¿Es necesario codificar todos los datos en estructuras como pilas en C ++, o es un conocimiento práctico suficiente para aclarar entrevistas?
- ¿Cómo se puede usar la IA para ayudar a los reclutadores en la toma de decisiones?
- Cómo resolver el problema de 'cortar el árbol' en HackerRank
- ¿Hay alguna guía sobre el uso de datos sintéticos para entrenar algoritmos de visión por computadora? ¿Hay alguna investigación al respecto?
basado en apuntes de una introducción de dos semanas “rápida” a Scheme para estudiantes sin experiencia previa en programación y una aversión admitida por cualquier cosa matemática.
El libro tiene un estilo muy fácil, no académico, enseñando con ejemplos y preguntas simples. La curva de aprendizaje es muy suave, con mucha repetición (cada vez, una pequeña variación o reutilización de algo que ya has aprendido). Se le enseña cómo resolver problemas simples y luego cómo juntar esas soluciones simples para resolver problemas más grandes. Te enseñan a analizar problemas y a encontrar patrones comunes en diferentes problemas.
El Capítulo 8 es más desafiante que los otros. No hay vergüenza en detenerse allí y volver más tarde, con una nueva perspectiva. En ese punto, ya has estado usando mucho la recursividad; Es posible que aún no lo entienda en un nivel fundamental, pero seguramente sabrá cómo usarlo.
Estructuras de datos recursivas
¿Puedes entender que algunas estructuras de datos son de naturaleza recursiva? Creo que puede ser útil porque los algoritmos recursivos funcionan particularmente bien con esas estructuras.
Por ejemplo, en un árbol de búsqueda binario, un nodo con dos descendientes es un nodo con dos árboles de búsqueda binarios. Cualquier nodo en un BST puede verse como la raíz de su propio árbol.
Imagine que el BST es una red de habitaciones vinculadas, cada una con un número diferente pintado en el piso. Se le pide que encuentre la suma de todos los números en el piso de todas las habitaciones.
Entras en la primera habitación; Tiene un seis en el piso y dos puertas por las que no has pasado. Te das cuenta de que el total es seis más la suma de todas las habitaciones más allá de la puerta de la izquierda y todas las habitaciones más allá de la puerta de la derecha. Entonces llamas a dos amigos para pedir ayuda, enviando uno por la puerta izquierda y el otro por la derecha.
Su primer amigo atraviesa la puerta de la izquierda, ve tres en el piso y dos puertas nuevas. Entonces llama a dos amigos … Su primer amigo pasa por la puerta izquierda, encuentra solo uno en el piso y ninguna otra puerta, así que regresa y dice “Uno”. Su segundo amigo vuelve igualmente rápido, diciendo “Dos”. Entonces agrega esas respuestas al número tres en su piso y vuelve a usted y dice “Seis”. Ahora sabes que el total es seis más seis más lo que sea que diga tu segundo amigo cuando finalmente regrese.
Eso es recursividad.
Tenías una red de amigos en constante expansión, cada uno con la misma tarea, cada uno resolviendo lo que podía resolver por sí mismo y confiando en que otros amigos hicieran el resto, cada uno usando el mismo plan pero encontrando una situación diferente. Finalmente, algunos amigos pudieron resolver su parte del problema sin ninguna ayuda. Lo que ayudó a los amigos que los llamaron a resolver su parte … y así sucesivamente hasta que sus dos amigos lo ayudaron a resolver su problema.
Eso es recursividad.
¿El plan para contar los números en todas las habitaciones se vuelve más confuso si todos tus amigos no solo siguen el mismo plan, sino que tienen el mismo nombre? No debería Después de todo, solo tiene que lidiar con dos de ellos directamente y creo que puede notar la diferencia entre usted y otras dos personas, incluso si todos tienen el mismo nombre. Uno atravesó la puerta izquierda, el otro atravesó la puerta derecha, usted se quedó en la habitación.
Eso es recursividad.
Mecánica
¿Realmente entiendes el alcance, la visibilidad y la vida útil? ¿Entiendes cómo se aplican cuando llamas a una función desde otra función? Es sorprendente cuántos programadores no lo hacen; se llevan bien buscándolo y copiando patrones de código estándar.
¿Le resulta confuso llamar a una función de otra? De lo contrario, no debería confundirse cuando la función que llama es la función desde la que llama.
¿Te confundiría si la función foo llama a la barra de funciones, y los parámetros de la barra y las variables locales tienen el mismo nombre que los parámetros y las variables locales de foo? No, porque sabes que tienen un alcance, visibilidad y vida útil completamente separados.
¿Te confundiría si el código de barras es una copia del código de foo? No debería Después de todo, la duplicación de código ocurre con demasiada frecuencia en la vida real.
Si no te confunde cuando foo y bar tienen los mismos nombres de variables / parámetros, y no te confunde cuando foo y bar contienen un código idéntico, ¿por qué debería confundirte cuando foo y bar tienen el mismo nombre? Todavía está llamando a una función desde otra función, cada una con su propio marco de referencia separado.
Puede ser útil si aprende lenguaje ensamblador y cómo se escriben las funciones en él. Eso le mostrará cómo se gestionan las pilas y los montones y cómo las pilas y los montones almacenan parámetros y variables locales. Eso puede darle una mejor comprensión de lo que quiero decir cuando digo que cada llamada a una función tiene su propio marco de referencia.
