La recursividad

Recursividad

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)

EJERCICIOS

      _|_         |         |
     [___]        |         |
    [_____]       |         |
   [       ]      |         |
 -------------------------------------
       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 recurs:

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] );
   }
}