Análisis
y Diseño de Algoritmos
Prof: Ing.
Victor Garro
Asistente:
Marco Elizondo Vargas
Recursión
Conceptos de
Recursión
Recursión es una técnica para resolver problemas. Muchas veces resulta más fácil desarrollar un algoritmo recursivo que uno iterativo.
Definición: Una función f es recursiva si en su cuerpo
contiene una aplicación de f, es decir,
si se puede activarse a si misma.
Si la llamada sucede dentro de la propia función se
dice que es directamente recursiva. En cambio si la función llama
a otra y esta a su vez llama a la primera se dice que es recursión indirecta.
El objetivo del programa recursivo, es realizar una
serie de llamadas hasta que la secuencia se define en un punto.
Las directrices para una función recursiva son:
-
Cada vez que se hace una llamada recursiva en una función, el programa
deberá comprobar que se satisface una condición básica con un determinado
parámetro puesto al valor mínimo.
-
Cada vez que se hace la llamada
a la función, los parámetros enviados a la misma, deberán ser de algún
modo más “simple”, es decir, su valor tender a la condición básica.
Ejemplo
La función Factorial puede ser desarrollada iterativamente o recursivamente.
Matemáticamente de define como:
Recursión Lineal
Definición: Una función f es recursiva lineal si la activación
de f(n) de f puede iniciar como máximo una nueva activación de f.
La evaluación de una función recursiva lineal tiene
dos faces:
-
Fase de activación en la cual se hacen nuevas activaciones.
-
Fase de solución en la cual el control del programa regresa a las
activaciones con un la modalidad último en entrar primero en salir.
Ejemplo:
La función factorial anterior es recursiva lineal.
Para factorial(4) de tiene las siguientes entradas y
salidas.
Ejemplo: la secuencia de fibonacci
son 1, 1, 2, 3, 5, 8, ... los cuales se determinan por la función:
1 si n=0 o 1
Fib(n)
Fib(n-1)+fib(n-2) n>1
fib(int
n)
{
if(n==0 || n==1) return 1; /* condición básica */
else
return (fib(n-1)+fib(n-2)); /* doble
llamada */
}
Para fib(4) se tienen las
siguientes entradas y salidas.
En este caso se puede observar que la solución
planteada de fibonacci es impracticable para valores
de n grandes. Cada fib() realiza dos llamadas, por lo
que el número de llamadas aumenta en proporción
geométrica.
¿ Conviene usar recursión
siempre?¿ Que pasa con la memoria?
Caso
iterativo para fibonacci
Fib(int
i)
{
int i,j,k;
if(n>0) {
i=0;
j=1;
for(k=2;
k<=n; k++)
{
j=j+i;
i=j-i;
}
return(j);
else return(0);
}
Recursión de Cola
Una función f es recursiva de cola si devuelve un
valor sin necesidad de recursión o si devuelve un
valor en cada activación recursiva.
A veces las funciones recursivas pueden implantarse
con eficiencia si se aplica recursión de cola.
Ejemplo
Dada la función
a
si n=0
G(n,a)=
G(n-1,n*a) si n>0
G(int n, int a)
{
if( n==0)
return a;
else
g(n-1,n*a);
}
Para
g(3,1)=g(2,3)=g(1,6)=g(0,6)=6
Es otra forma de calcular 3!
Se puede observar que todo el trabajo de una función
con recursión de cola se realiza en la fase de
activación, es decir cuando se realiza la llamada. En el caso de la función
recursiva lineal este se realiza después de que el control regresa.
Ejemplo
factorial(3)=3*factorial(2) esta multiplicación se realiza después de que
el control regresa de la activación de factorial(2).
Construcción de una solución recursiva:
1.- definir un problema en términos de problemas
idénticos en naturaleza pero más pequeño.
2.- el tamaño del problema debe reducirse en las
llamadas anteriores.
3.- encontrara el caso degenerado y asegurar que se
llegue a este.
Métodos para la resolución de problemas que usan recursividad
Divide y vencerás
Consiste en dividir un problema en dos o más subproblemas, cada uno de los cuales es similar al original
pero más simple en tamaño.
Para resolver cada subproblema
se tienen dos alternativa:
El subproblema es
suficientemente pequeño para dar una solución o
El subproblema todavía es
de gran tamaño el cual se debe dividir aplicando recursivamente
la técnica.
Algoritmo
DivideyVencerás( limite del problema)
Inicio
Si
la condición define un caso suficientemente simple entonce
Dar
la solución del caso simple
Sino
Dividir
el problema en subproblemas
DivideyVencerás( límite del subproblema 1)
…………
DivideyVencerás( límite del subproblema 1)
Fin_si
Fin
Backtracking(retroceso)
La solución del problema se divide en pasos y la
solución del paso i-ésimo se define en función de la
solución del paso i-ésimo+1
Algoritmo
Ensayar( entrada entero i; entrada/salida booliano éxito;…)
Inicio
Inicializar
posibilidades
Mientras
hay posibilidades y no hay éxito Hacer
Tomar la siguiente pposibilidad
Si
es aceptable entonces
Anotarlo
como parte de la solución
Si
es solución general entonces
Éxito
es verdadero
Sino
Ensayar(i+1,
éxito;..)
Fin_si
Si
no hay éxito entonces
Desanotarlo como parte de la solución
Fin_si
Fin_si
Fin_mientras
Fin
Problema
Diseñar un programa que, dado un tablero de ajedrez
(n filas y n columnas) y un caballo que
se mueve según las reglas del juego, averigüe se es posible que el caballo
efectúe un recubrimiento del tablero completo, es decir, visite cada cuadro del
tablero exactamente una vez.
Torres de Hanoi
Problema: Se dispone de 3 columnas en las cuales se
apilan n discos, unos encima de otros, de mayor a menor diámetro.
En la posición inicial todos los discos están en la
primera columna de manera que los diámetros de los discos aumentan al descender
en la pila.
El objetivo es describir una secuencia de
movimientos de los discos de manera que estos finalicen en la tercera columna,
conservando el mismo orden que tenían inicialmente.. Las restricciones para
realizar los movimientos son:
1.- se puede mover un disco a la vez
2.- en ningún momento puede apoyarse un disco sobre
otro de menor diámetro.
