Fuente:
Programación en C++ / Principios y Aplicaciones (resumen)
Carlos Romero Shollande
1. Introducción
Un subprograma recursivo es cuando éste se llama a sí mismo, ya sea directa o indirectamente.
La solución recursiva es menos eficiente que la solución iterativa, pero existen numerosas situaciones en las que la recursividad es una solución simple y natural a un problema que en caso contrario sería difícil de resolver.
La mayoría de los subprogramas recursivos no ahorran significativamente memoria y funcionan ligeramente más lento que sus equivalentes iterativos, debido a que consumen mucho espacio de pila y la pueden desbordar. Pues, por cada llamada realizada las variables que intervienen en el subprograma son salvadas en la pila, para poder posteriormente iniciar el retorno.
La comprensión del concepto de recursividad es difícil, por lo que trataremos de explicarla con este ejemplo: Una persona es descendiente del Sr. Ortega si (1) esta persona es un hijo del Sr. Ortega o (2) esta persona es un hijo de un descendiente del Sr. Ortega.
Obsérvese que la palabra “descendiente” se utiliza para definirse a sí misma (descendiente del descendiente).
En la recursividad siempre existe un medio para salir. En el ejemplo anterior, la condición (1) se denomina salida de la definición, y la condición (2) viene a ser la parte recursiva propiamente dicha y que garantiza que siempre se alcance la salida: cuando el descendiente es hijo del Sr. Ortega, se termina el proceso recursivo.
2. Pilas
La implementación de la recursividad se hace con el uso de una estructura denominada pila (stack). Una pila es un espacio de memoria a la que se accede de un modo especial: el primer elemento en entrar es el último elemento en salir.
Su analogía más clara en la vida ordinaria está en la pila de platos de una cocina. La pila está limitada en espacio por unas direcciones de memoria fijas.
Conceptos fundamentales de una pila: puntero de pila, operación de meter datos en la pila, limpiar la pila o dejar la pila vacía y tamaño o longitud de la pila.
Gráfica 1. Conceptos básicos de una pila
El C++ utiliza al menos una pila durante la ejecución de cualquier programa para almacenar valores de variables, constantes, parámetros y direcciones de retorno.
Gráfica 2. Asignación de espacio en llamadas recursivas:
3. Funciones Recursivas
La ventaja principal de las funciones recursivas es que se pueden usar para crear versiones más claras y sencillas de los algoritmos que sus correspondientes iterativas.
Por ejemplo, el factorial de un entero no negativo n, que se define como n! (factorial de n), y que fue desarrollado en el problema ilustrativo (2) del capítulo 4 (sentencias repetitivas).
Matemáticamente se expresa como:
Donde 1! es igual a 1 y 0! se define como 1. Mediante la siguiente relación se llega a una definición recursiva de la función factorial.
n! = n * (n-1)!
Por ejemplo, 4! es igual que 4 * 3!, como se demuestra a continuación:
4! = 4 * (4 – 1) * (4 – 2) * (4 – 3) = 4 * 3 * 2 * 1 = 24
4! = 4 * (3 * 2 * 1)
4! = 4 * (3!)
Los subprogramas recursivos deben contener las dos partes o sentencias siguientes:
Una llamada a sí misma (recursiva), normalmente con el valor de los parámetros que cambian en cada llamada.
Una condición de terminación o salida, que es la condición que no produce ninguna autollamada.
En el ejemplo del factorial se tiene:
Llamada recursiva: n! = n * (n – 1)!
Factorial = n * Factorial (n – 1)
Condición de salida: n = 0
4. Procedimientos Recursivos
En el C++ también es posible realizar procedimientos recursivos.
Ejemplo: al obtener el número inverso de un número dado tal como 758, se puede observar que su inverso es 857.
Este se genera invirtiendo las cifras:
n = 758
758 % 10 = 8 r1 = 8 y 758 / 10 = 75
75 % 10 = 5 r2 = 5 y 75 / 10 = 7
7 % 10 = 7 r3 = 7
5. Seguimiento de la Recursividad
Cuando el subprograma recursivo es invocado por el programa principal u otro subprograma para solucionar algún problema. El subprograma recursivo de hecho sabe cómo resolver los casos más sencillos, los llamados casos base.
Si el subprograma es llamado mediante un caso base, éste simplemente devuelve un resultado.
Si es llamado por un problema más complejo, el subprograma divide al problema en dos partes conceptuales, una parte que dicho subprograma no sabe resolver (proceso de ida) y otra que si sabe resolver (proceso de vuelta).
Para hacer factible la recursión, la primera parte debe parecerse al problema original, pero debe ser ligeramente más sencilla o pequeña que él.
Debido a que este nuevo problema se parece al original, el subprograma llama a una nueva copia de él mismo, que se encargará del problema más pequeño, a esto se conoce como llamada recursiva o paso de recursión.
El paso de recursión también incluye la palabra clave return, pues su resultado se combinará con la parte del problema que el subprograma sabía cómo resolver, formando un resultado que se devolverá al primer invocador, probablemente al programa principal (main).
El paso de recursión se ejecuta mientras la llamada original del subprograma aún está abierta, es decir cuando éste no ha terminado de ejecutarse.
Además puede generar más de tales llamadas recursivas a medida que el subprograma sigue dividiendo, en dos partes, los nuevos subproblemas con los que se llama al subprograma.
Para que la recursión termine, finalmente, cada vez que el subprograma se llame a sí mismo mediante una versión ligeramente más sencilla del problema original, esta secuencia de problemas cada vez más pequeños debe desembocar eventualmente en el caso base.
Le devuelve un resultado a la copia previa de la función y una secuencia de instrucciones return recorre el camino hacia arriba, hasta que la llamada original de la función le devuelve el resultado final a main.
Como ejemplo del funcionamiento de estos conceptos, veamos el problema del factorial en su versión recursiva.
Consideremos el cálculo del factorial para n = 4, enviado como parámetro valor desde otro subprograma o desde el programa principal:
n = 4 Llamada a Factorial(4) es n = 0; No
Factorial = 4 * Factorial(3)
n = 3 Llamada a Factorial(3) es n = 0; No
Factorial = 4 * 3 * Factorial(2)
n = 2 Llamada a Factorial(2) es n = 0; No
Factorial = 4 * 3 * 2 * Factorial(1)
n = 1 Llamada a Factorial(1) es n = 0; No
Factorial = 4 * 3 * 2 * 1 * Factorial(0)
n = 0 Llamada a Factorial(0) es n = 0; Si
Factorial = 4 * 3 * 2 * 1 * 1
Factorial = 24
No es recomendable declarar a la función factorial como int, ya que cuando n = 8, 8! = 40320, este valor supera ampliamente el rango de los enteros (32767).
Es mejor definirla de tipo long int o de tipo float.
La evaluación del factorial de 4 procede como se muestra en la gráfica siguiente.
Gráfica 3. Seguimiento del algoritmo recursivo Factorial (4!).
En el extremo izquierdo se muestra el proceso de sucesión de llamadas recursivas (proceso de ida) hasta que se evalúa que 0! es igual a 1, con lo que termina la recursión.
En el extremo derecho, se muestran los valores que cada llamada recursiva que los devuelve al invocador, hasta que se calcula y se devuelve el valor final.
6. Tipos de Recursividad
La recursividad puede ser de dos tipos:
Recursividad directa (simple): un subprograma se llama a sí mismo una o más veces directamente.
Por ejemplo, la función recursiva del factorial.
Recursividad indirecta (mutua): dos o más subprogramas se llaman mutuamente; es decir, un subprograma A llama a otro subprograma B y éste a su vez llama al subprograma A.
Por ejemplo, las funciones recursivas para determinar si un número es par o impar
7. Recomendaciones para el Uso de la Recursividad
Si en un proceso las sucesivas llamadas a un subprograma suponen guardar valores de variables en cada etapa, que posteriormente deben ser procesados en orden inverso, entonces en estos casos es aplicable la recursividad.
La razón es la semejanza con la definición de pila.
Si un proceso se puede definir en términos más simples en función del mismo, como es el caso de sumas, factoriales, etc., se debe preferir el uso de la recursividad.
Si no existe una ventaja clara para utilizar la recursividad, no la utilice.
Por el contrario, si la definición del problema es inherentemente recursiva, entonces la solución recursiva debe ser considerada preferentemente.
Por ejemplo, el problema de las Torres de Hanoi.
Si un algoritmo no recursivo se puede obtener y es menos complejo que el recursivo, mejor usar el no recursivo
Cada llamada recursiva requiere la asignación de espacio de memoria (en la pila) para todas las variables locales, parámetros de valor y la dirección de retorno.
Si cada llamada usa memoria, y si existen limitaciones en memoria central, esto puede suponer una seria limitación.
No utilice la recursividad, a menos que tenga un medio para terminar las llamadas recursivas. Se debe tener la seguridad de que en los datos utilizados existe al menos uno que cumpla con la condición de terminación.
El problema más frecuente con un subprograma recursivo es que puede no terminar adecuadamente.
Por ejemplo, si la condición de terminación no es correcta o incompleta, entonces el subprograma puede producir una recursión infinita o bien llamarse hasta que se gaste toda la memoria disponible.
Ejemplo:
Ejemplo:
Usando una función recursiva denominada Factorial(), determinar el factorial de un número ingresado previamente.
Codificación
#include <iostream.h> // Factorial de un numero
#include <conio.h>
long int factorial(int);
void main() {
int n;// Número ingresado
int i; // Contador
clrscr();
gotoxy(1,2); cout<<"Ingresar un número: ";
gotoxy(30,2); cin>>n;
cout<<”\n”<<n<<"! = "<<factorial(n)<<"\n";
getch();
}
long int factorial(int n) {
if(n<=1) return 1;
else return n * factorial(n-1);
}
No hay comentarios:
Publicar un comentario