Recursividad

El concepto de recursividad va ligado al de repetición. Son recursivos aquellos algoritmos que, estando encapsulados dentro de una función, son llamados desde ella misma una y otra vez, en contraposición a los algoritmos iterativos, que hacen uso de bucles while, do-while, for, etc.

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 ITERATIVO:


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


RECURSIVO:


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

• 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 argumentos 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 memoria del ordenador se divide (de manera lógica, no física) en varios segmentos (4):

1. Segmento de código: Parte de la memoria donde se guardan las instrucciones del programa en cod. Máquina.
2. Segmento de datos: Parte de la memoria destinada a almacenar las variables estáticas.
3. Montículo: Parte de la memoria destinada a las variables dinámicas.
4. 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.

Llamada a una función recursiva:

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)

a). Torres de Hanoi: Problema de solución recursiva, consiste en mover todos los discos (de diferentes tamaños) de una aguja a otra, usando una aguja auxiliar, y sabiendo que un disco no puede estar sobre otro menor que éste.

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

Solución:
 
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 recursivamente:

Solución:
 
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] );
   }
}
 
 
Solución: Imprime la cadena invertida.

<Volver a la sección de Tutoriales de Programación>