Curso de C++ (Página 26)

pagina025 Principal pagina026

CAPITULO 26 Funciones V: 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, 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 1

3ª Instancia
(recupera n=2 de la pila) retorna 1*2=2

2ª 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.


pagina025 Principal pagina026