La recursión no solo significa “funciones que se llaman a sí mismas”. Significa que algo se define de forma autorreferencial. Hay muchas, muchas variedades. No tengo ninguna esperanza de enumerarlos a todos: alguien está obligado a aparecer y mostrar un buen ejemplo que me perdí. Así que aquí hay una lista de todos los tipos diferentes que se me ocurren:
- Estructuras de datos recursivas (por ejemplo, árboles, listas enlazadas individualmente)
- Estructura cíclica de datos
- Algoritmos recursivos (por ejemplo, el algoritmo de Dijkstra)
- Consultas recursivas (sí, realmente, ¡las consultas recursivas SQL son una cosa!)
- Recursividad funcional
- Recursión mutua (se puede encontrar como variantes de la mayoría de las categorías anteriores)
- Corecursion
- Evaluación recursiva: una función como el combinador de punto fijo, cuya evaluación continúa para siempre, devolviendo repetidamente una nueva versión de sí mismo (a menos que la evaluación perezosa proporcione una excusa para detenerse). Esto se puede usar para implementar la recursión anónima.
- Recursión abierta: la forma dinámica en que los lenguajes orientados a objetos aplican la recursividad en la evaluación de objetos.
La recursión es generalizada en la informática. Es una pena que se enseñe tan poco.
Recursividad funcional
- Cómo escribir un algoritmo para la suma de n factoriales. es decir, 1! +2! +3! +… (N-1) + n
- ¿Cómo es posible que el hashing sea imposible de revertir? ¿Hay alguna prueba?
- Noto que las estructuras de datos son difíciles de entender y asimilar con solo leerlas. ¿Qué tengo que hacer?
- ¿Cuál es la forma más rápida (estructura de datos) para buscar la matriz multidimensional?
- ¿Qué temas básicos hay que saber en C ++ antes de aprender estructuras de datos y algoritmos?
¿Tu pregunta era solo sobre la recursión funcional? Bueno, gran parte de eso está cubierto anteriormente, directa o indirectamente. Dentro del tema limitado de la recursión funcional, hay algunos enfoques diferentes.
- Estricta recursividad funcional. El enfoque ingenuo, respaldado por el lenguaje de programación más imperativo. Del tipo que corre el riesgo de volar la pila.
- Recurrencia funcional mediante eliminación de llamadas de cola. Algunos idiomas (p. Ej., Scala) solo pueden lograr esto para las llamadas de cola recursivas individuales. Scheme requiere que todas las implementaciones también hagan esto para la recursividad mutua (y todas las llamadas de cola, de hecho, recursivas o no). Algunos lenguajes (por ejemplo, Haskell) tienen compiladores que también implementan contras de módulo de recursión de cola, lo que hace que algunos tipos de recursividad no recursiva de cola sean seguros.
- Evaluación perezosa. Haskell, por ejemplo, usa de manera predeterminada la implementación diferida y, como se implementa en el compilador de GHC, solo evalúa la mayor cantidad de funciones necesarias para devolver esa parte del resultado que se requiere actualmente. Si una función recursiva es productiva (es decir, cada iteración produce una parte útil del resultado), la función regresa al final de la primera iteración, con el resto de la recursión aún no evaluado en un thunk. Esto significa que la recursión de cola no es necesaria, porque solo hay un marco de referencia adjunto a la llamada de función. Si la salida se consume de forma recursiva, todo se puede evaluar de manera eficiente en un espacio constante.
- Pliegues. Esta es una forma de recursión anónima. Los pliegues abstraen los detalles de la recursividad, lo que permite a la persona que llama aplicar una función simple a una estructura de datos recursiva. Debido a que los detalles de implementación están ocultos, los pliegues pueden implementarse de manera segura incluso en lenguajes estrictos como Java o C ++ (donde la implementación real probablemente sea un bucle while). Los pliegues son muy poderosos; Casi todas las funciones que podría aplicar a una estructura de datos recursiva, incluidas todas las estándar que encuentre en la mayoría de las bibliotecas principales, se pueden implementar con pliegues.
- Trampolines Uso del estilo de paso continuo para implementar la recursividad.
