PDF de programación - Recursividad

Recursividad

Una función que se llama a sí misma se denomina recursiva



Utilidad


Cuando la solución de un problema se puede expresar en términos de la
resolución de un problema de la misma naturaleza, aunque de menor
complejidad.


Sólo tenemos que conocer la solución no recursiva para algún caso
sencillo (denominado caso base) y hacer que la división de nuestro problema
acabe recurriendo a los casos base que hayamos definido.


Como en las demostraciones por inducción, podemos considerar que
“tenemos resuelto” el problema más simple para resolver el problema más
complejo (sin tener que definir la secuencia exacta de pasos necesarios para
resolver el problema).


Funcionamiento

- Se descompone el problema en problemas de menor complejidad (algunos de

ellos de la misma naturaleza que el problema original).


- Se resuelve el problema para, al menos, un caso base.

- Se compone la solución final a partir de las soluciones parciales que se van

obteniendo.



Diseño de algoritmos recursivos


1. Resolución de problema para los casos base:


o Sin emplear recursividad.

o Siempre debe existir algún caso base.



2. Solución para el caso general:


o Expresión de forma recursiva.

o Pueden incluirse pasos adicionales

(para combinar las soluciones parciales).



Siempre se debe avanzar hacia un caso base: Las llamadas recursivas simplifican
el problema y, en última instancia, los casos base nos sirven para obtener la
solución.


int factorial (int n)
{
int resultado;

if (n==0)
resultado = 1;
else
resultado = n*factorial(n-1);

return (resultado);
}

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


// Caso base

// Caso general

// Caso general

// Caso base




Recursividad vs. iteración

Aspectos que hay que considerar al decidir cómo implementar la solución a un
problema (de forma iterativa o de forma recursiva):

- La carga computacional (tiempo de CPU y espacio en memoria) asociada a

las llamadas recursivas.


- La redundancia (algunas soluciones recursivas resuelven un problema en


- La complejidad de la solución (en ocasiones, la solución iterativa es muy

repetidas ocasiones).

difícil de encontrar).


- La concisión, legibilidad y elegancia del código resultante de la solución

recursiva del problema.



Ejemplo: Sucesión de Fibonacci



Solución recursiva

int fibonacci (int n)
{
if ((n == 0) || (n == 1))
return 1;
else
return fibonacci(n-1) + fibonacci(n-2);
}

Solución iterativa

int fibonacci (int n)
{
int actual, ant1, ant2;

ant1 = ant2 = 1;

if ((n == 0) || (n == 1)) {
actual = 1;
} else
for (i=2; i<=n; i++) {
actual = ant1 + ant2;
ant2 = ant1;
ant1 = actual;
}
}

return (actual);
}

Cálculo recursivo de fibonacci(5)



Ejemplo: Las torres de Hanoi



Mover n discos del poste 1 al poste 3 (utilizando el poste 2 como auxiliar):


hanoi (n, 1, 2, 3);



Solución recursiva:

void hanoi (int n, int inic, int tmp, int final)
{
if (n > 0) {

// Mover n-1 discos de "inic" a "tmp".
// El temporal es "final".

hanoi (n-1, inic, final, tmp);

// Mover el que queda en "inic" a "final"

printf (“Del poste %d al %d.\n”, inic, final);

// Mover n-1 discos de "tmp" a "final".
// El temporal es "inic".

hanoi (n-1, tmp, inic, final);
}
}


Solución para 3 discos


Según la leyenda, los monjes de un templo tenían que mover una pila de 64
discos sagrados de un sitio a otro. Sólo podían mover un disco al día y, en el
templo, sólo había otro sitio en el que podían dejarlos, siempre ordenados de



forma que los mayores quedasen en la base.



El día en que los monjes realizasen el último movimiento,

el final del mundo habría llegado…