Fundamentos de programación/Recursión
Esta página o sección necesita una revisión de ortografía y gramática.
Puedes ayudar editándolo
| Lección 9 |
| Recursión |
Los procesos recursivos son métodos para resolver problemas que están definidos en términos de si mismos.[1] Las subrutinas que implementan este tipo de procesos dividen una tarea en componentes o subtareas similares a la tarea principal pero de menor tamaño, calculan las soluciones invocándose a si mismas (de forma directa o indirecta a través de otra función)[2] y obtienen la solución al problema combinando los resultados que reciben.[3] Representan una alternativa al uso de las estructuras de control de flujo (también llamadas iterativas)[4][3], especialmente para aquellos problemas que se pueden modelar de modo natural en términos de si mismos o jerárquicos.[4][1]
Ambos métodos son similares porque ejecutan repetidamente un proceso pero son diferentes en la forma en que lo hacen.[3] El enfoque recursivo toma un problema y determina si se encuentra trabajando con el caso más sencillo posible, llamado «caso base». De ser así, la subrutina simplemente regresa el resultado. Si la función no está trabajando con el caso base, procede a dividir el problema en dos o más casos o secciones más sencillas o a simplificarlo de alguna manera y se llama a si misma con esas secciones del problema. Este proceso se repite hasta que la función se llama a si misma con el caso base. Al llegar a este punto, la función le regresa el resultado a la instancia de si misma que la llamó. La invocación de la función que realizó la llamada procede a combinar los resultados parciales y a regresar un resultado a la función que la llamó. Este proceso continúa hasta regresar a la llamada original de la función, la cual combina los resultados parciales que recibe para obtener la respuesta al problema original y entregarla al programa principal.[2]
Pasos básicos
[editar]La siguiente función calcula el factorial de un número usando recursión:
entero subrutina factorial (entero número)
entero resultado_parcial
entero caso_simplificado
entero resultado_simplificado
si número = 1 entonces
resultado_parcial := 1
sino
caso_simplificado := número - 1
resultado_simplificado := factorial (caso_simplificado)
resultado_parcial := número * resultado_simplificado
fin_si
regresar resultado_parcial
fin_subrutina
entero factorial_calculado
factorial_calculado := factorial (6)
Al analizar la función podemos ver que resuelve el problema a través de estos pasos básicos:[5]
| Verificar si el valor actual es el caso base. | ... si número = 1 ...
|
| Si se está trabajando con el caso base: | |
|
... resultado_parcial := 1 ...
|
| Si no se está trabajando con el caso base: | |
|
... caso_simplificado := número - 1 ...
|
|
... resultado_simplificado := factorial (caso_simplificado) ...
|
|
... resultado_parcial := número * resultado_simplificado ...
|
| Regresar la respuesta. | ... regresar resultado_parcial ...
|
Durante su ejecución la función se llama a si misma con casos cada vez más sencillos hasta llegar al caso base. Este ejemplo inicia invocandola con el valor 6. La función reconoce que no se trata del caso base y se llama a si misma con el valor 5, que corresponde a la versión simplificada del problema. El proceso continúa hasta que se llama a si misma con el valor 1. La nueva invocación reconoce el caso base y regresa el valor inmediatamente. Ese evento detiene la secuencia de invocaciones e inicia el proceso de retorno. En cada paso la función toma el valor que recibe y lo multiplica por el valor que recibió para construir su resultado y regresarlo a la función que la invocó. Este proceso se puede ver más claramente de forma gráfica a continuación:[1]
factorial (6) | factorial (5) | | factorial (4) | | | factorial (3) | | | | factorial (2) | | | | | factorial (1) = 1 | | | | 2 * 1 = 2 | | | 3 * 2 = 6 | | 4 * 6 = 24 | 5 * 24 = 120 6 * 120 = 720
Recursión de cola
[editar]La recursión es una herramienta muy potente y permite implementar con facilidad cálculos que se expresan en términos de si mismos. Por ejemplo, el cálculo de un número en la sucesión de Fibonacci se expresa formalmente de la siguiente manera:[4]
Con los siguientes casos báse:
Y en pseudocódigo, usando recursión, podemos escribirlo de esta forma:
entero subrutina fibonacci (entero número)
entero resultado_parcial
si (número = 0) o (número = 1) entonces
resultado_parcial := 1
sino
resultado_parcial := fibonacci (n - 1) + fibonacci (n - 2)
fin_si
regresar resultado_parcial
fin_subrutina
fibonacci para calcular el 6.º número de la secuencia.Sin embargo, esa implementación es muy ineficiente ya que calcula múltiples veces los mismos valores. Como se puede observar en la secuencia de llamadas ilustrada en la imagen, para calcular el sexto número de la secuencia, la función calcula el 5 y el 4 números, pero para calcular el 5 también debe calcular el 4 número, trabajo que realiza dos veces. La función debe realizar en total 8 invocaciones que regresan el caso base (F1 y F2), 3 invocaciones que calculan el tercer número de la secuencia (F3), 2 invocaciones que calculan el cuarto número (F4) y una invocación para calcular el quinto número (F5). Esto representa una gran cantidad de cálculos repetidos que afectan negativamente el rendimiento del algoritmo.[1]
Para resolver el problema en estos casos se usa una técnica llamada «recursión de cola». Una función recursiva por la cola es una que no realiza cálculos adicionales después de invocarse a si misma. El resultado de la función es simplemente el resultado de la invocación recursiva. Para evitar el trabajo adicional necesario para combinar los resultados y obtener la respuesta final, la función que realiza la invocación transfiere ese trabajo a la función invocada mediante parámetros adicionales[6] que consisten en uno o más resultados parciales según sea necesario y un contador que se modifica en cada invocación para indicar el estado del cálculo.[1]
El siguiente fragmento de un programa implementa el cálculo de los números de la secuencia de Fibonacci usando recursión de cola. A diferencia de la implementación anterior, esta recibe 3 parámetros. El parámetro contador se inicia con el número de la secuencia que se desea calcular y se decrementa en cada llamada recursiva. Los otros dos parámetros representan los dos valores previos de la secuencia y se inicializan con los casos base (1 y 0 respectivamente en este caso). En cada invocación, la función verifica si el contador ha llegado a cero y de ser así regresa el resultado parcial que ha recibido de la función invocadora. Si el contador no ha llegado a cero, procede a calcular el siguiente valor de la secuencia sumando los dos valores parciales que ha recibido y se llama a si misma con el nuevo resultado parcial. Finalmente, para que los usuarios de la función no deban preocuparse de conocer los casos base necesario para inicializar la función, se define una función con un solo parámetro que se encarga de hacer la llamada inicial con los valores adecuados.
entero subrutina fibonacci_auxiliar (entero contador, entero fibonacci_menos_1, entero fibonacci_menos_2)
entero resultado_parcial
entero fibonacci_actual
si contador = 0 entonces
resultado_parcial := fibonacci_menos_2
sino
fibonacci_actual := fibonacci_menos_1 + fibonacci_menos_2
resultado_parcial := fibonacci_auxiliar (contador - 1, fibonacci_actual, fibonacci_menos_1)
fin_si
regresar resultado_parcial
fin_subrutina
entero subrutina fibonacci (entero número)
regresar fibonacci_auxiliar (número, 1, 0)
fin_subrutina
Al analizar la secuencia de invocaciones que se producen durante la ejecución de este algoritmo vemos que se ha eliminado la necesidad de realizar el mismo cálculo de forma repetida y que una vez que se llega al final de la secuencia de invocaciones el programa regresa directamente a la llamada principal de la función con el resultado, sin necesidad de hacer cálculos adicionales.
fibonacci (6) | fibonacci_auxiliar (6, 1, 0) | | fibonacci_auxiliar (5, 1, 1) | | | fibonacci_auxiliar (4, 2, 1) | | | | fibonacci_auxiliar (3, 3, 2) | | | | | fibonacci_auxiliar (2, 5, 3) | | | | | | fibonacci_auxiliar (1, 8, 5) 8 < - - - - - fibonacci_auxiliar (0, 13, 8) = 8
Errores comunes
[editar]La recursión es una herramienta muy potente para resolver problemas pero su uso incorrecto puede dar lugar a problemas con el código que impiden el funcionamiento correcto de los programas. Es especialmente importante prestar atención a los siguientes pasos de un algoritmo recursivo:
- Definición del caso base. La función continuará llamándose a si misma hasta que se agote la memoria si el caso base se omite o está definido incorrectamente, ya que la evaluación comparando el problema con el caso base nunca será exitosa.[4][2]
- Simplificación del problema en el paso recursivo. Una implementación incorrecta del paso de simplificación del problema impedirá que las invocaciones sucesivas de la función se dirijan progresivamente al caso base.[2]
Resumen de la lección
[editar]- Los procesos recursivos resuelven los problemas expresándolos en términos de si mismos.
- Una función regresa el resultado directamente si está trabajando con el caso base.
- Si una función no está trabajando con el caso base, procede a descomponer el problema y a llamarse a si misma con los subproblemas.
- Una vez que las invocaciones recursivas regresan a la función que las invocó, esta procede a combinar los resultados y regresa el resultado a su invocadora.
- Una función recursiva por la cola es una que no realiza cálculos adicionales después de invocarse a si misma.
- La recursión de cola evita la necesidad de realizar el mismo cálculo de forma repetida.
- Los problemas más comunes al resolver un problema recursivamente incluyen la definición incorrecta u omisión del caso base y la simplificación inadecuada del problema.
Términos clave
[editar]Lecturas adicionales
[editar]Bibliografía
[editar]- ↑ 1,0 1,1 1,2 1,3 1,4 Abelson, Harold; Sussman, Gerald Jay; Sussman, Julie (1998). Structure and interpretation of computer programs. MIT electrical engineering and computer science series. (en inglés) (2.ª edición). Cambridge, Massachusetts, Estados Unidos: MIT Press. p. 683. ISBN 978-02-62-51087-5. Consultado el 25 de junio de 2016.
- ↑ 2,0 2,1 2,2 2,3 Deitel, H. M.; Deitel, P. J. (1995). C How to program [Cómo programar en C/C++] (2.ª edición). México: Prentice Hall Hispanoamericana, S. A. p. 927. ISBN 968-880-471-1.
- ↑ 3,0 3,1 3,2 Brookshear, J. Glenn (2012). Computer Science: An overview [Introducción a la computación] (11.ª edición). Madrid, España: Pearson Educación, S. A. p. 704. ISBN 978-84-78-29139-7.
- ↑ 4,0 4,1 4,2 4,3 Joyanes Aguilar, Luis (2013). Fundamentos generales de programación (1.ª edición). Ciudad de México, México: McGraw Hill. p. 368. ISBN 978-607-15-0818-8.
- ↑ Bartlett, Jonathan (16 de junio de 2005). «Mastering recursive programming». IBM developerWorks (en inglés). Consultado el 27 de junio de 2016.
- ↑ Scott, Michael L. (2000). Programming Language Pragmatics (en inglés) (1.ª edición). California, Estados Unidos: Morgan Kaufmann. p. 858. ISBN 1-55860-578-9.
| Proyecto: Fundamentos de programación |
| Anterior: Evaluación de la lección 8 — Recursión — Siguiente: Evaluación de la lección 9 |