Descripción

En mi experiencia. enseñar a los estudiantes a usar la recursividad siempre ha sido una tarea difícil. Cuando se presenta por primera vez, los estudiantes a menudo reaccionan con cierto recelo ante la idea en su totalidad, como si acabaran de verse expuestos a algún truco de prestidigitación en lugar de a una nueva metodología de programación. Dada esa reacción. muchos estudiantes nunca aprenden a aplicar técnicas recursivas y pasan a cursos más avanzados incapaces de escribir programas que dependen del uso de estrategias recursivas.

Este libro pretende desmitificar este material y animar al estudiante a “pensar recursivamente”. Este libro está diseñado para usarse como texto complementario en un curso intermedio en estructuras de datos, pero podría usarse igualmente con muchos otros cursos de este nivel. El único requisito previo para usar este texto es un curso de introducción a la programación. Dado que Pascal se usa en los ejemplos de programación, el estudiante también debe familiarizarse con la programación en Pascal. aunque esto se puede incluir fácilmente como parte del mismo curso. Para apoyar la presentación concurrente de Pascal y el material sobre recursividad, los ejemplos de programación en los primeros capítulos requieren solo las características más básicas de Pascal. Para desarrollar una comprensión más completa del tema, es importante que el estudiante examine la recursividad desde varias perspectivas diferentes. El Capítulo I proporciona una descripción general informal que examina el uso de la recursividad fuera del contexto de la programación.

El Capítulo 2 examina los conceptos matemáticos subyacentes y ayuda al estudiante a desarrollar un modelo conceptual apropiado. En particular. este capítulo cubre la inducción matemática y la complejidad computacional con considerable detalle. Esta discusión está diseñada para que no sea amenazante para el estudiante ansioso por las matemáticas y, al mismo tiempo, incluya suficiente estructura formal para enfatizar hasta qué punto las ciencias de la computación dependen de las matemáticas para sus fundamentos teóricos. El Capítulo 3 aplica la técnica de descomposición recursiva a varias funciones matemáticas y comienza a mostrar cómo se representa la recursividad en Pascal. El Capítulo 4 continúa esta discusión en el contexto de los procedimientos recursivos, enfatizando el paralelo entre la descomposición recursiva y la técnica más familiar de refinamiento por pasos. ¡Los capítulos 5 a 9 presentan severo! ejemplos del uso de la recursividad para resolver problemas cada vez más sofisticados.

El Capítulo 7 es de particular importancia y cubre las técnicas de clasificación recursiva, ilustrando la aplicabilidad de la metodología recursiva a la práctica) dominios de problemas. El capítulo 9 contiene muchos ejemplos deliciosos, que constituyen excelentes ejercicios y demostraciones si se dispone de hardware gráfico. El Capítulo 10 examina el uso de procedimientos recursivos en el contexto de estructuras de datos recursivas y contiene varios ejemplos importantes. Estructuralmente, este capítulo aparece tarde en el texto principalmente para evitar la introducción prematura de punteros. Para los cursos en los que los estudiantes han sido introducidos a los punteros relativamente temprano, puede ser útil cubrir el material del Capítulo 10 inmediatamente después del Capítulo 7. Finalmente, el Capítulo 11 examina la implementación subyacente de la recursividad y proporciona el enlace final para eliminar el misterio. Por otro lado, este material no es esencial para la presentación y puede interferir con la comprensión conceptual del estudiante si se presenta demasiado pronto.

Estoy profundamente agradecido por la asistencia de muchas personas que ayudaron a dar forma a la forma final del texto. Quiero expresar una nota especial de agradecimiento a Jennifer Friedman, cuyos consejos han sido invaluables tanto en cuestiones de sustancia como de estilo. También quisiera agradecer a mis colegas de la facultad de Wellesley, Douglas Long, K. Wojtek Przytula, Eleanor Lonske, James Finn, Randy Shull y Don Wolitzer por su apoyo. Joe Buhler en Reed College, Richard Pattis en la Universidad de Washington, Gary Ford en la Universidad de Colorado en Colorado Springs, Steve Berlín en M.I.T. y Suzanne Rodday (Wellesley ’85) han hecho importantes sugerencias que han mejorado drásticamente el resultado final.