Se dice que una función es recursiva cuando se define en función de si misma. No todas la funciones pueden llamarse a si mismas, deben estar diseñadas especialmente para que sean recursivas, de otro modo podrían conducir a bucles infinitos, o a que el programa termine inadecuadamente.
C++ permite la recursividad. Cuando se llama a una función, se crea un nuevo juego de variables locales, de este modo, si la función hace una llamada a si misma, se guardan sus variables y parámetros en la pila, y la nueva instancia de la función trabajará con su propia copia de las variables locales, cuando esta segunda instancia de la función retorna, recupera las variables y los parámetros de la pila y continua la ejecución en el punto en que había sido llamada.
Por ejemplo:
Función recursiva para calcular el factorial de un número entero. El factorial se simboliza como n!, se lee como "n factorial", y la definición es:
n! = n * (n-1) * (n-2) *… 1
/* Función recursiva para cálculo de factoriales */ int factorial(n) { if(1 == n) return 1; /* Condición de terminación */ else return n*factorial(n-1); /* Recursividad */ }
Veamos paso a paso, lo que pasa cuando se ejecuta esta función, por ejemplo: factorial(4):
1ª Instancia
n=4
n != 1
salida <- 4 * factorial(3) (Guarda el valor de n = 4)
2ª Instancia
n != 1
salida <- 3*factorial(2) (Guarda el valor de n = 3)3ª Instancia
n != 1
salida <- 2*factorial(1) (Guarda el valor de n = 2)4ª Instancia
n == 1 -> retorna 13ª Instancia
(recupera n=2 de la pila) retorna 1*2=22ª instancia
(recupera n=3 de la pila) retorna 2*3=6
1ª instancia
(recupera n=4 de la pila) retorna 6*4=12
Valor de retorno -> 12
La función factorial es un buen ejemplo para demostrar cómo se hace una función recursiva, pero la recursividad no es un buen modo de resolver esta función, que sería más sencilla y rápida con un bucle "for". La recursividad consume muchos recursos de memoria y tiempo de ejecución, y se debe aplicar a funciones que realmente le saquen partido.
Por ejemplo: visualizar las permutaciones de n elementos.
Las permutaciones de un conjunto es las diferentes maneras de colocar sus elementos, usando todos ellos y sin repetir ninguno. Por ejemplo para A, B, C, tenemos: ABC, ACB, BAC, BCA, CAB, CBA.
#include <iostream.h> /* Prototipo de función */ void Permutaciones(char *, int l=0); int main(int argc, char *argv[]) { char palabra[] = "ABCDE"; Permutaciones(palabra); return 0; } void Permutaciones(char * cad, int l) { char c; /* variable auxiliar para intercambio */ int i, j; /* variables para bucles */ int n = strlen(cad); for(i = 0; i < n-l; i++) { if(n-l > 2) Permutaciones(cad, l+1); else cout << cad << ", "; /* Intercambio de posiciones */ c = cad[l]; cad[l] = cad[l+i+1]; cad[l+i+1] = c; if(l+i == n-1) { for(j = l; j < n; j++) cad[j] = cad[j+1]; cad[n] = 0; } } }
El algoritmo funciona del siguiente modo:
Al principio todos los elementos de la lista pueden cambiar de posición, es decir, pueden permutar su posición con otro. No se fija ningún elemento de la lista, l = 0: Permutaciones(cad, 0)
0 | 1 | 2 | 3 | 4 |
A | B | C | D | /0 |
Se llama recursivamente a la función, pero dejando fijo el primer elemento, el 0: Permutacion(cad,1)
0 | 1 | 2 | 3 | 4 |
A | B | C | D | /0 |
Se llama recursivamente a la función, pero fijando el segundo elemento, el 1: Permutacion(cad,2)
0 | 1 | 2 | 3 | 4 |
A | B | C | D | /0 |
Ahora sólo quedan dos elementos permutables, así que imprimimos ésta permutación, e intercambiamos los elementos: l y l+i+1, es decir el 2 y el 3.
0 | 1 | 2 | 3 | 4 |
A | B | D | C | /0 |
Imprimimos ésta permitación, e intercambiamos los elementos l y l+i+1, es decir el 2 y el 4.
0 | 1 | 2 | 3 | 4 |
A | B | /0 | C | D |
En el caso particular de que l+i+1 sea justo el número de elementos hay que mover hacia la izquierda los elementos desde la posición l+1 a la posición l:
0 | 1 | 2 | 3 | 4 |
A | B | C | D | /0 |
En este punto abandonamos el último nivel de recursión, y retomamos en el valor de l=1 e i = 0.
0 | 1 | 2 | 3 | 4 |
A | B | C | D | /0 |
Permutamos los elementos: l y l+i+1, es decir el 1 y el 2.
0 | 1 | 2 | 3 | 4 |
A | C | B | D | /0 |
En la siguiente iteración del bucle i = 1, llamamos recursivamente con l = 2: Permutaciones(cad,2)
0 | 1 | 2 | 3 | 4 |
A | C | B | D | /0 |
Imprimimos la permutación e intercambiamos los elementos 2 y 3.
0 | 1 | 2 | 3 | 4 |
A | C | D | B | /0 |
Y así sucesivamente.
Veremos más aplicaciones de recursividad en el tema de estructuras dinámicas de datos.
© Septiembre de 2.000 Salvador Pozo, salvador@c-con-clase.every1.net