• Author / Uploaded
• Cristian San Martin

Citation preview

Recursividad 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, sino que 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. Tampoco todos los lenguajes de programación permiten usar recursividad. C++ permite la recursividad. Cada vez que se llama a una función, se crea un juego de variables locales, de este modo, si la función hace una llamada a si misma, se guardan sus variables y parámetros, usando 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: Prodríamos crear una 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 Hay algunas limitaciones: • •

No es posible calcular el factorial de números negativos, no está definido. El factorial de cero es 1.

De modo que una función bien hecha para cálculo de factoriales debería incluir un control para esos casos:

/* Función recursiva para cálculo de factoriales */ int factorial(int n) { if(n < 0) return 0; else if(n > 1) return n*factorial(n-1); /* Recursividad */ return 1; /* Condición de terminación, n == 1 */ } Veamos paso a paso, lo que pasa cuando se ejecuta esta función, por ejemplo: factorial(4): 1a Instancia n=4 n>1 salida ← 4 * factorial(3) (Guarda el valor de n = 4) 2a Instancia n>1 salida ← 3*factorial(2) (Guarda el valor de n = 3) 3a Instancia n>1 salida ← 2*factorial(1) (Guarda el valor de n = 2) 4a Instancia n == 1 → retorna 1 3a Instancia (recupera n=2 de la pila) retorna 1*2=2 2a instancia (recupera n=3 de la pila) retorna 2*3=6

1a instancia (recupera n=4 de la pila) retorna 6*4=24 Valor de retorno → 24 Aunque la función factorial es un buen ejemplo para demostrar cómo funciona una función recursiva, la recursividad no es un buen modo de resolver esta función, que sería más sencilla y rápida con un simple 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. Veamos otro ejemplo: visualizar las permutaciones de n elementos. Las permutaciones de un conjunto son 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 using namespace std; /* Prototipo de función */ void Permutaciones(char *, int l=0); int main(int argc, char *argv[]) { char palabra[] = "ABCDE"; Permutaciones(palabra); cin.get(); 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