Recursividad

RecursividadEl 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));
}
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ÓNLa memoria del ordenador se divide (de manera lógica, no física) en varios segmentos (4):
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. 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)
EJERCICIOSa). 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:
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] );
}
}