24 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

No se puede calcular el factorial de números negativos, y 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):

1^a Instancia
n=4
n > 1
salida ← 4 * factorial(3) (Guarda el valor de n = 4)

2^a Instancia
n > 1
salida ← 3*factorial(2) (Guarda el valor de n = 3)

3^a Instancia
n > 1
salida ← 2*factorial(1) (Guarda el valor de n = 2)

4^a Instancia
n == 1 → retorna 1

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

2^a instancia
(recupera n=3 de la pila) retorna 2*3=6

1^a instancia
(recupera n=4 de la pila) retorna 6*4=24
Valor de retorno → 24

La función factorial es un buen ejemplo para demostrar cómo se hace una función recursiva, sin embargo 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 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 <iostream> 
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 << 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 permutació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.