Extenso tutorial de recursividad

Question

Algunos problemas que requieren recurrencia siempre me han puesto una solución. No siempre puedo encontrar un algoritmo recursivo, pero sé que hay una solución recursiva al problema.

Encuentro problemas como factorial y fibonacci fáciles de implementar mediante el enfoque recursivo. Pero cuando me enfrento a problemas más complejos, como generar la partición de un número http://en.wikipedia.org/wiki/Partition_%28number_theory%29, sé que existe un posible enfoque recursivo, pero me quedo atascado allí mismo. No puedo diseñar un algoritmo recursivo. Supongamos que quiero imprimir todas las combinaciones de una cadena o si quiero aplicar una fuerza bruta sobre un problema de cambio de moneda mediante la recursión, no puedo idear un enfoque recursivo.

¿Hay alguna manera particular de pensar para llegar a un enfoque recursivo? ¿Hay algún extenso tutorial de algoritmos recursivos que pueda ayudarme a resolver problemas más avanzados?

Answer 1

Mire a través del Structure and Interpretation of Computer Programs book, que es muy recomendable aquí en Stack Overflow y está disponible gratuitamente en línea. Utiliza el lenguaje de programación Scheme para enseñar conceptos fundamentales sobre programación. Dado que Scheme es un lenguaje de programación funcional, la recursión se usa ampliamente en todas partes, no solo donde la usaría incluso en lenguajes de programación imperativos como C o PHP, sino también donde normalmente usaría una construcción de bucle. Los ejemplos y problemas en el libro presentan la recursión en su hábitat natural, si se quiere, y no a través de intrincados escenarios inventados.