Una introducción a la Recursión
La recursión es una herramienta brillante para la programación. Le proporciona una solución directa pero poderosa para abordar varios problemas. Dicho esto, la recursividad puede ser a veces un poco complicada, especialmente para los principiantes. La gente a menudo tiene problemas para pensar de forma recursiva para ver cómo pueden abordarlo. Además, a la gente también le resulta difícil escribir un programa recursivo que no requiera una cantidad excesiva de tiempo para ejecutarse. Discutiremos los fundamentos de la recursividad en este artículo, ayudándole a refinar o desarrollar esta habilidad esencial de programación.
Explicación de la recursividad
La recursión es un método para resolver problemas a través de categorías más pequeñas de la misma cuestión. Resolvemos los problemas a través de los sub-problemas hasta llegar a su versión más menor, también conocida como el caso base. La gente a menudo tiene problemas para entender la recursión por varias razones. Una función recursiva sigue llamándose a sí misma hasta que la ejecución se detiene, y una condición base se hace realidad. Hay dos partes dos una función recursiva:
- El caso base
- La estructura recursiva
Caso base
La base es la parte más pequeña del problema. Sorprendentemente, conocemos la condición de terminación o solución donde la función podría devolver inmediatamente los resultados.
La estructura recursiva
Encontrar la respuesta a un problema a través de la solución de su sub-problema es una estructura recursiva. Una vez más, las cosas se vuelven confusas ya que la función se llama a sí misma para romper el desafío actual a un nivel directo.
Entendiendo la recursividad a través del problema de la cuenta atrás
Debes imprimir los números que comienzan de N a uno en orden descendente. Debemos romper la solución del problema para encontrar versiones más pequeñas de la cuestión. Por lo tanto, sería mejor imprimir primero el N y luego llamar a la función para imprimir el resto del N a un número.
Imprimir cifras de N a uno igual a imprimir (N) + Imprimir de N a uno
En este ejemplo, el primero es el problema original, y el segundo (N-uno a uno es el subproblema.) Debes estar pensando, la cadena de llamada funcional debe detenerse en algún lugar, y ¿cuál podría ser el caso base?
Caso base
La cuenta atrás debe concluir después de la impresión de uno. Ahora, debemos introducir una condición base para terminar la ejecución del programa. Ahora debemos mezclar el caso base, y la estructura recursiva para escribir toda la implementación recursiva del problema discutido anteriormente.
¿Cuál es el punto de usar la recursividad?
La recursión a menudo brilla en situaciones con problemas complejos. Incluso sería justo decir que se eleva a las ocasiones en que el asunto es más complicado de lo habitual. Es más, puedes aplicar la recursión con casi cualquier problema. Sin embargo, hay situaciones particulares en las que la recursión le resultará especialmente útil. A continuación se presenta una situación en la que la recursión brilla con luz propia.
Gráficos, redes, jerarquías
Cuando se habla de algoritmos y se habla de gráficos, no solemos conversar sobre el gráfico que resalta la relación entre las variables como el gráfico de calificación de Top Coder (se centra en la relación entre su calificación y el tiempo.) En lugar de ello, hablamos sobre todo de una red de personas, cosas y conceptos conectados de varias maneras.
Por ejemplo, uno podría imaginarse un mapa de carreteras como un gráfico que muestra las ciudades y sus conexiones con las carreteras. Los gráficos pueden ser masivos, complicados y difíciles de manejar, programáticamente hablando. Es más, son bastante similares en las competencias de algoritmos y en la teoría de algoritmos. Afortunadamente, se puede usar la recursión cuando se trabaja con elementos complicados como redes y gráficos.
¿Cómo resolver problemas usando la recursión?
Te sorprendería saber cuánto necesitarás utilizar tu proceso de pensamiento para resolver problemas de forma recursiva. He aquí un método efectivo que debería considerar ya que le ayudará a decidir los casos base y la estructura recursiva con facilidad:
- ¿Cómo puedo resolver puedo encontrar una solución encontrando sub-problemas de un tema más significativo?
- No tiene sentido preocuparse por el problema del sub-problema ya que la recursividad lo resolverá.
- Anota una estructura recursiva con las condiciones de límite correctas y el parámetro de función
- Determinar los casos base. Como se mencionó anteriormente, son la versión más pequeña del problema mayor. Usted ya conoce las soluciones. Además, piense en las consecuencias de no escribir una base o de elegir la base incorrecta.
Comprender los subproblemas y su naturaleza es esencial en las soluciones recursivas. Aquí hay un par de ejemplos:
Programación dinámica
Resolviendo problemas a través de múltiples sub-problemas, pero los sub-temas son dependientes.
Divide y conquista
Usando otros elementos además de los subproblemas, donde hay subproblemas independientes.
¿Dónde aplica la gente la recursión
- Diseño de algoritmos de aproximación relacionados
- Algoritmos de clasificación bien reconocidos como Merge Sort o Quick Sort
- Solución de problemas mediante el rastreo y la búsqueda exhaustiva
- Solución de problemas con la ayuda de la programación dinámica
- Usando un enfoque de divide y vencerás para resolver problemas
- Encontrar soluciones a los problemas de los gráficos
- Buscando respuestas a los problemas de los árboles
- Resolver los problemas de las listas de enlaces y matrices
Por qué la recursión es esencial
Aquí hay algunas excelentes razones por las que la recursión es beneficiosa para los programadores y desarrolladores:
- Las soluciones recursivas son en su mayoría más limpias comparadas con una solución iterativa. Hay casos en los que se puede reducir una línea de 50 a 5 o 10 líneas de recursividad.
- Pensar en la recursividad es más natural en algunos casos. La recursividad es posiblemente la forma más directa y transparente de resolver problemas de estructura de datos, por ejemplo, árboles con estructuras recursivas simples.
- Algunos problemas son bastante complicados, y en algunos casos, imposibles de resolver mediante el uso de la Iteración.
- La recursividad es una excelente opción, ya que divide los problemas en subproblemas independientes y más pequeños, lo que hace más sencillo el paralelismo.
Conceptos vitales de recursión que uno debe explorar
- Comparación de recursividad vs. iteración
- Diferentes tipos de recursividad y sus propiedades
- Usando el método del árbol de recursividad para analizar la recursividad
- Utilizando el Teorema Maestro para analizar la recursividad
- Pros y contras de la programación recursiva
- Comprender cómo convertir el conde iterativo en código recursivo y viceversa
¿Por qué se produce la recursividad con los errores de desbordamiento de la pila?
Debemos tener una comprensión completa de cada función para aprovechar la recursividad. De lo contrario, podríamos tener toneladas de complicados errores de depuración. Por supuesto, el tiempo puede ser corto a veces, pero es mejor empezar escribiendo precisamente cuál es el papel de una función en particular.
La recursividad será inmensamente útil en el mundo real y en la programación de Top Coder. Te sorprendería ver cuántos programadores experimentados encuentran la recursividad amenazante. Practicarla le ayudará a pensar de forma recursiva y eventualmente resolverá problemas de programación complicados.