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, 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 <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.

Otras formas de recursividad

Existen otras formas de implementar algoritmos recursivos, no es necesario que una función se invoque a si misma.

Por ejemplo, un par de funciones A y B pueden crear un algoritmo recursivo si la función A invoca a la función B, y esta a su vez invoca a la función A.

Este mismo mecanismo se puede implementar con tres, cuatro o con cualquier número de funciones.

Veamos un ejemplo. Partamos de la siguiente serie:

1 - 1/2 + 1/3 - 1/4 + 1/5 - ... - 1/2*n + 1/2*n+1 - ...

Podemos diseñar un procedimiento recursivo para calcular la suma de los n primeros elementos de la serie, de modo que usemos una función diferente para los elementos pares e impares.

// Suma de la serie 1-1/2+1/3-1/4+1/5...
// (C) 2009 Con Clase
// Salvador Pozo

#include <iostream>

using namespace std;

double par(int);
double impar(int);
double suma(int);

int main() {

    cout << suma(3) << endl;
    cout << suma(13) << endl;
    cout << suma(23) << endl;
    cout << suma(87) << endl;
    cout << suma(250) << endl;
    cout << suma(450) << endl;
    return 0;
}

double suma(int n) {
    if(n % 2) return impar(n);
    else return par(n);
}

double par(int n) {
    return impar(n-1)-1/double(n);
}

double impar(int n) {
    if(n == 1) return 1;
    return par(n-1)+1/double(n);
}

Veremos más aplicaciones de recursividad en el tema de estructuras dinámicas de datos.

Problemas

  1. La sucesión de Fibonacci se define como una serie infinita de números naturales.

    El primer término, para n = 0, es 0 y el segundo, para n = 1 es 1. Los sucesivos se calculan como la suma de los dos términos anteriores. Por ejemplo, el término 5 es la suma de los términos 3 y 4.

    Los primeros términos son: 0, 1, 1, 2, 3, 5, 8...

    Hacer un programa que calcule el término n de la sucesión de Fibonacci de forma recursiva.

  2. Volvamos al problema de los palíndromos. Pero ahora usaremos una función recursiva para determinar si una cadena determinada es o no palíndroma.

  3. Veamos ahora un problema clásico: las torres de Hanói.

    Torres de Hanói
    Torres de Hanói

    El juego consiste en tres varillas verticales. En una de ellas están apiladas un número de discos, generalmente ocho, de diámetros diferentes, ordenados de mayor a menor (el de mayor diámetro abajo). Las otras dos varillas están vacías. El juego consiste en pasar todos los discos de la varilla ocupada a una de las varillas libres.

    Para llegar a ese objetivo hay que respetar tres reglas:

    1. Sólo se puede mover un disco cada vez.
    2. Un disco de mayor tamaño no se puede colocar encima de uno más pequeño.
    3. Sólo se puede mover el disco que se encuentre en la parte superior de cada varilla.

    Resolver el juego usando algoritmos recursivos.

Comentarios de los usuarios (9)

b0ch0n
2010-11-06 17:26:57

ejercicio de fibonacci

http://codepad.org/m3v0fWLz

b0ch0n
2010-11-11 00:58:55

/*

* Copypaste(p) by b0ch0n

* Volvamos al problema de los palíndromos.

Nota del administrador: Hemos eliminado el código ya que las soluciones a los problemas no se han incluido de forma intencionada. La idea es que cada uno haga sus propios problemas a su modo.

DEHNER, Heinz
2014-10-30 15:53:57

He tenido problemas con la aplicacion de recursivas en las siguientes funciones:

int MCD1(int a, int b)

{

if (b) MCD1(b, a%b);

else

return (a);

}

int MCD2(int a, int b)

{

if (a - b) MCD2(b, (a > b ? a - b : b - a));

return (b);

}

las que en teoria deberia devolverte el maximo comun divisor de los numeros ingresados... pero devuelve cero (0). Estas funciones andan perfectamente en Borland C++ pero no en el visual studio 2013... donde esta el error?

Gracias

Steven R. Davidson
2014-11-12 10:29:46

Hola Dehner,

Tienes el mismo tipo de error en ambas funciones. Cuando emprendes la recursividad, te adentras en una serie de invocaciones. Al terminar, la idea es regresar al punto de la primera invocación. Esto implica que tienes que "retornar" de cada invocación.

En tu caso, las funciones retornan un entero, por lo que te interesa retornar el entero calculado, especialmente de la invocación recursiva. Esto es,

if( b )
  return MCD1( b, a%b );

return a;

Aunque podemos reescribir las sentencias anteriores así,

return b ? MCD1( b, a%b ) : a;

Lo mismo sucede con 'MCD2()'.

Espero que esto te aclare la duda.

Steven

eduardo
2015-05-07 18:06:40

Disculpen me podrian ayudar con este problema soy algo novato con lo de programacion:

/*solicitar un numero al usuario y devlover la suma de los digitos que

involucran dicho numero(utilizar una funcion recursiva y/o la forma tradicional

de resolverlo). los resultados que pueden devlover serian los siguientes:

numero proporcionado=5,sumatoria de digitos=5

numero proporcionado=23,sumatoria de digitos=5

numero proporcionado 1305,sumatoria de digitos=9*/

BJNM
2015-10-13 19:30:18

Que tal compañeros, antes que nada agradecer por el material. Bueno, yo soy nuevo en este curso y de lo que eh aprendido es que para ingresar a los valores de un array se realiza desde el indice 0 hasta el indice n-1, donde n es el numero de elementos de dicho, en el ejemplo de Permutaciones ponen lo siguiente;

for(j = l; j < n; j++) cad[j] = cad[j+1];
         cad[n] = 0;

y en ambas sentencias acceden con el indice de la dimension.

Alguien me podria explicar gracias

BJNM
2015-10-13 19:36:02

Otra duda, aparte intente complementar ese programa para que el usuario definiera cuantos elementos tendria el conjunto y si me compila pero al ejecutarse solo me da dos permutaciones y luego se "traba" el programa y lo tengo que cerrar, mi codigo es el siguiente:

# include <iostream>
# include <string.h>
# include <stdio.h>

using namespace std;

void Permutaciones(int n, string *, int l=0);

int main(int argc, string *argv[])
{
    string *palabra=NULL;
    int t;
    cout<<"Ingrese el numero de elementos que tendra su conjunto: ";
    cin>>t;
    cout<<"Ingrese los "<<t<<" elementos del conjunto:"<<endl;
    palabra = new string[t];
    getline(cin, palabra[0]);
    for(int i=0;i<t;i++)
    {
            cout<<"Elemento "<<i+1<<": ";
            getline(cin, palabra[i]);
    }

    Permutaciones(t,palabra);



    cin.get();
    return 0;
}

void Permutaciones(int n, string * cad, int l)
{
     string c;            //variable auxiliar para intercambio
     int i, j;          //variables para bucles
     for(i=0; i<n-l; i++)
     {
              
              if(n-l>2) Permutaciones(n,cad,l+1);
              
              else
              {
                  cout <<"Permutacion: ";
                  for(int k=0; k<n; k++)
                  {
                          cout<<cad[k]<<", ";    //                          if(k==n-1)cout<<cad[k]<<endl;
                                                 //                          else cout<<cad[k]<<", ";
                          
                  }
                  
              }
              //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];

                          
              }
     }
}

De antemano gracias.

Steven R. Davidson
2015-10-25 17:35:31

Hola BJNM,

En la función 'Permutaciones()', 'n' no representa la dimensión del array; o sea, su cantidad máxima de elementos. La variable 'n' representa la cantidad de caracteres en la cadena: "ABCDE". Recuerda que cualquier cadena de caracteres debería terminar en cero, el cual representa el carácter nulo. Es decir, la cadena "ABCDE" contiene 5 caracteres, pero el array 'palabra', contiene 6 caracteres, porque una cadena literal ya guarda el carácter nulo al final.

Las sentencias que muestras ciertamente acceden al elemento de índice 'n', pero sólo se ejecutarán si intercambiamos el carácter nulo. Por lo tanto, tenemos que "arreglar" la situación mudando los caracteres finales a partir del elemento de índice 'l', que representa el comienzo de la subcadena. Al final, aseguramos que el elemento en el índice 'n' es el carácter nulo:

cad[n] = 0;  // Aseguramos que el final siempre sea el carácter nulo

Espero haber aclarado la duda.

Steven

Steven R. Davidson
2015-10-25 18:11:07

Hola BJNM,

Tienes algunos errores:

- Los ficheros de cabecera originalmente de C son renombrados en C++. En tu caso, sería,

#include <cstring>
#include <cstdio>

Como no usas ninguna entidad en <cstdio>, puedes eliminar esta inclusión.

- Como usas la clase 'string', lo más seguro es que no te interesa <cstring> sino <string>. Fíjate que no hay un ".h" en el nombre.

- Anteriormente en C++, usábamos 0 (cero) para representar un puntero nulo. En la versión estándar actual, que a veces se llama C++11, usamos el nuevo vocablo, 'nullptr', para representar cualquier puntero nulo.

- Adjudicas memoria dinámicamente usando 'new[]'. Esto implica que creas varios objetos de tipo 'string'. Sin embargo, no existe su operador complemento: 'delete[]', para liberar dinámicamente tal memoria.

- Escribes:

getline( cin, palabra[0] );

Esto no tiene mucho sentido porque realizas la misma sentencia en el siguiente bucle 'for'.

- El problema que estás teniendo se debe a que accedes al elemento posterior al final de 'palabra', a través de 'cad'. Como no existe tal objeto 'string', lo más seguro es que estés accediendo a memoria ocupada por otra entidad, que afortunadamente el sistema operativo deniega provocando un error visible.

- Para solucionar el problema, tenemos dos alternativas:

1. Antes de realizar el intercambio, tenemos que comprobar que no estamos accediendo a un elemento más allá del final del array. Si esto es cierto, entonces tenemos que realizar el "arreglo" usando el bucle 'for' para recolocar los elementos del sub-array en su orden original.

2. Siguiendo el ejemplo original en el curso, necesitamos un elemento nulo al final, para indicar que es el final de la información. Como has creado un array de objetos, tendríamos que crear un array de un elemento más:

palabra = new string[t+1];

y luego representar un objeto nulo, en la forma de una cadena. Por ejemplo,

palabra[t+1] = string("");

Ahora podemos implementar el algoritmo del ejemplo del curso.

Para aclarar, tu programa se basa en mostrar todas las permutaciones de cadenas de caracteres, mientras que el ejemplo del curso muestra todas las permutaciones de caracteres.

Espero que esto aclare las dudas.

Steven