Estructuras de Datos II 

Inicio

Generalidades

Ejercicios

Talleres

Proyecto

Ejercicios "amistosos"

 Recursividad

 La recursividad o recursión es una de las herramientas de programación más poderosas y una de las más difíciles de entender por los estudiantes nuevos de programación.
Este importante tema se explica generalmente en los cursos avanzados de ciencias computacionales.

La recursión permite definir un objeto (problemas, estructuras de
datos) en términos de sí mismo. Casos típicos de estructuras de
datos definidas de manera recursiva son los árboles y las listas
enlazadas.
Un subprograma es recursivo si puede invocarse a sí mismo.
Los módulos recursivos generalmente resuelven un problema reduciéndolo
a un ejemplar del mismo problema para unos datos más pequeños. A veces,
una solución recursiva a un problema es la más natural y, por lo tanto,
ofrece el procedimiento más simple.
En matemáticas se definen muchos objetos presentando un proceso para
producir dicho objeto. Por ejemplo, pi es definido como la razón de la
circunferencia de un círculo a su diámetro. Esto es equivalente a 
establecer las siguientes instrucciones: obtenga la circunferencia de
un círculo y su diámetro, divida el primero por el último y llame al
resultado pi. Claramente, el proceso especificado debe terminar con un
resultado definido.

Otro ejemplo de una definición especificada por un proceso es el de la
función factorial, que juega un papel importante en matemáticas y 
estadística. Dado un entero positivo n, el factorial de n se define como 
el producto de todos los enteros entre n y 1. Por ejemplo, 5 factorial
es igual a 5*4*3*2*1=120 y 3 factorial es igual a 3*2*1=6. La definición
de esta función se puede escribir así:
n!=1 si n=0
n!=n*(n-1)*(n-2)*...*1 si n>0

Otro ejemplo menos familiar es la secuencia de Fibonacci, la secuencia
de enteros 0,1,1,2,3,5,8,13,21,34...
Cada elemento en esta secuencia es la suma de los dos elementos precedentes
(ej. 0+1=1,1+1=2,1+2=3,2+3=5,...). Si definimos fib(0)=0,fib(1)=1, y así
sucesivamente, podemos definir la secuencia de Fibonacci por medio de la
siguiente definición recursiva:
fib(n)=n si n=0  o  n=1
fib(n)=fib(n-2)+fib(n-1) si n>=2


Uno de los requisitos importantes para que un algoritmo recursivo sea
correcto es que no debe generar una secuencia infinita de llamadas a
él mismo. Obviamente, cualquier algoritmo que genera tal tipo de
secuencia, nunca termina. Al menos para un argumento o un grupo de
argumentos, se debe definir una función recursiva f en términos que no
involucren a f. Es decir, debe haber una "forma de salida" de la secuencia
de las llamadas recursivas:
factorial: 0! = 1
fibonacci: fib(0)=0, fib(1)=1
Sin esta salida no recursiva, no podría calcularse una función recursiva.
Cualquier llamada a una definición recursiva o a un algoritmo recursivo
debe eventualmente reducirse al cálculo o a la manipulación de una o más
formas simples de la secuencia no recursiva.

Algo es recursivo si se define en términos de sí mismo (cuando para definirse hace mención a sí mismo). Para que una definición recursiva sea válida, la referencia a sí misma debe ser relativamente más sencilla que el caso considerado.

Ejemplo: definición de nº natural:

-> el N º 0 es natural
-> El Nº n es natural si n-1 lo es.

En un algoritmo recursivo distinguimos como mínimo 2 partes:

a). Caso trivial, base o de fin de recursión:

Es un caso donde el problema puede resolverse sin tener que hacer uso de una nueva llamada a sí mismo. Evita la continuación indefinida de las partes recursivas.

b). Parte puramente recursiva:

Relaciona el resultado del algoritmo con resultados de casos más simples. Se hacen nuevas llamadas a la función, pero están más próximas al caso base.

EJEMPLO

int Factorial( int n )
{
   int i, res=1;
   for(i=1; i<=n; i++ )
      res = res*i;
  return(res);
}

int Factorial( int n )
{
   if(n==0) return(1);
   return(n*Factorial(n-1));
}

TIPOS DE RECURSIÓN

• Recursividad simple: Aquella en cuya definición sólo aparece una llamada recursiva. Se puede transformar con facilidad en algoritmos iterativos.
• Recursividad múltiple: Se da cuando hay más de una llamada a sí misma dentro del cuerpo de la función, resultando más dificil de hacer de forma iterativa.

  
   int Fib( int n )                                  /* ej: Fibonacci */
  {
      if(n<=1) return(1);
      return(Fib(n-1) + Fib(n-2));
  }
  
  

• Recursividad anidada: En algunos de los arg. de la llamada recursiva hay una nueva llamada a sí misma.

  
   int Ack( int n, int m )                        /* ej: Ackerman */
  {
      if(n==0 ) return(m+1);
      else if(m==0) return(Ack(n-1,1));
      return(Ack(n-1, Ack(n,m-1)));
  }
  
  

• Recursividad cruzada o indirecta: Son algoritmos donde una función provoca una llamada a sí misma de forma indirecta, a través de otras funciones.

  
  Ej: Par o Impar:
  int par( int nump )
  {
      if(nump==0) return(1);
      return( impar(nump-1));
  }
  
  int impar( int numi )
  {
      if(numi==0) return(0);
      return( par(numi-1));
  }
  

LA PILA DE RECURSIÓN

Segmento de código: Parte de la memoria donde se guardan las instrucciones del programa en cod. Máquina.
Segmento de datos: Parte de la memoria destinada a almacenar las variables estáticas.
Montículo: Parte de la memoria destinada a las variables dinámicas.
Pila del programa: Parte destinada a las variables locales y parámetros de la función que está siendo ejecutada.

Llamada a una función:

• Se reserva espacio en la pila para los parámetros de la función y sus variables locales.
• Se guarda en la pila la dirección de la línea de código desde donde se ha llamado a la función.
• Se almacenan los parámetros de la función y sus valores en la pila.
• Al terminar la función, se libera la memoria asignada en la pila y se vuelve a la instruc. Actual.

En el caso recursivo, cada llamada genera un nuevo ejemplar de la función con sus correspondientes objetos locales:

• La función se ejecutará normalmente hasta la llamada a sí misma. En ese momento se crean en la pila nuevos parámetros y variables locales.
• El nuevo ejemplar de función comieza a ejecutarse.
• Se crean más copias hasta llegar a los casos bases, donde se resuelve directamente el valor, y se va saliendo liberando memoria hasta llegar a la primera llamada (última en cerrarse)

Para mostrar el funcionamiento interno de la recursividad, en la siguiente tabla se presentan los valores que van adquiriendo las variables y los valores que son guardados en la pila, en el transcurso del cálculo del factorial de un número N = 4.

En el primer paso N es igual a 4; por lo tanto, debe hacerse 4*3!
Ante la imposibilidad de realizar esta operación (porque primero debe calcularse 3!) se guarda el valor de N en la pila y se continúa trabajando con N = 3. Con el nuevo valor de N procedemos de manera similar que con N = 4. La diferencia radica en que la entrada, N, está más cercana al estado básico. En consecuencia, en el paso 2 se agrega el valor 2 a la pila y en el paso 4 se guarda el valor 1 en la pila. Una vez alcanzado el estado básico, paso 5, se comienza a extraer los valores almacenados en la pila y a operar con ellos.
En el paso 6 se extrae de la pila el valor 1 y se multiplica por el factorial de 0, obteniendo 1!
Luego se extrae el 2 y se multiplica por el factorial de 1, para obtener 2!. Se continúa así hasta que la pila quede vacía, lo cual ocurre en el paso 9 donde se calcula el factorial de 4.

      _|_         |         |
     [___]        |         |
    [_____]       |         |
   [       ]      |         |
 -------------------------------------
       A          B         C

/* Solucion:
    1- Mover n-1 discos de A a B
    2- Mover 1 disco de A a C
    3- Mover n-1 discos de B a C  
*/
void Hanoi( n, inicial, aux, final )
{
   if( n>0 )
   {
       Hanoi(n-1, inicial, final, aux );
       printf("Mover %d de %c a %c", n, inicial, final );
       Hanoi(n-1, aux, inicial, final );
   }
}

b). Calcular x elevado a n de forma recursiva:

float xelevn( float base, int exp )
{
  if(exp == 0 ) return(1);
  return( base*xelevn(base,exp-1));
}

c). Multiplicar 2 nºs con sumas sucesivas recursivas:

int multi( int a, int b )
{
  if(b == 0 ) return(0);
  return( a + multi(a, b-1));
}

d). ¿Qué hace este programa?:

void cosa( char *cad, int i)
{
   if( cad[i] != '\0' )
   {
      cosa(cad,i+1);
      printf("%c", cad[i] );
   }
}