Recursión
[Link]
Recursión
• El concepto de recursión. Es un concepto que se define
en términos de él mismo, ya sea directa o indirectamente,
de la misma forma que un procedimiento recursivo es
aquel que se llama así mismo directa o indirectamente.
• Las definiciones recursivas de funciones son muy
frecuentes en las matemáticas.
Ejemplos:
– Factorial
– Números de Fibonacci
– Torrres de Hanoi
[Link]
Divide y Vencerás
• Descomponer recursivamente un problema
grande y complejo en otros subproblemas de
igual naturaleza, pero más pequeños y simples,
para finalmente mezclar los resultados del
proceso para resolver el problema.
• Normalmente estos problemas poseen dos
llamadas recursivas y cada una opera
aproximadamente sobre la mitad de los datos.
[Link]
Problemas recurrentes
• Algunos de estos son los algoritmos conocidos como: el
factorial, el preorder, donde las llamadas se realizan de la
siguiente forma:
[Link]
Torres de Hanoi
• Las Torres de Hanoi : (Matemático Francés Edouard Lucas en
1883) Consisten de tres postes, en uno de ellos se encuentran
una serie de discos ordenados de mayor a menor magnitud, el
problema consiste en pasar todos los discos (moviendo uno a la
vez) de un poste a otro utilizando el poste restante como
auxiliar. La restricción que existe es que no se puede colocar un
disco sobre otro de menor magnitud.
• ¿Cómo se puede realizar un algoritmo recursivo que sirva para
realizar la tarea?. Primero observemos lo que sucede con casos
pequeños:
[Link]
N=2 A Movimient A B C Total
o
1, 2 1, A, B 2 1
2, A, C 1 2
1, B, C 1, 2 3
N=3 A Movimient A B C Total
o
1, 2, 3 1, A, C 2, 3 1
2, A, B 3 2 1
1, C, B 3 1, 2
3, A, C 1, 2 3
1, B, A 1 2 3
2, B, C 1 2, 3 7
1, A,w Cw w . i n a c a p . c l 1, 2, 3
• El experimento con tres discos nos indica que la idea es
transferir los dos discos de arriba de A al poste B, luego mover
el tercer disco a C y traer los otros dos a C.
• La idea general entonces es : Transferir del poste inicial, Pi, los
n - 1 discos al poste auxiliar Pa, luego mover el disco n de Pi al
poste final, Pf, y finalmente transferir los n - 1 discos de Pa a Pf.
[Link]
Entrada : n, Pi, Pf, Pa.
Salida : Movimientos necesarios para transferir los n discos de Pi a Pf
Método : Descrito anteriormente.
HANOI(n, X, Y, Z)
{
if(n = 0) return;
if(n = 1) MOVE(X,Y);
else {
HANOI(n-1, X, Z, Y);
MOVE(X, Y);
HANOI(n-1, Z, Y, X);
}
}
[Link]
• Entonces, ¿Cuántos movimientos se necesitan para mover los n
discos?. Digamos que Tn es el mínimo número de movimientos
que transfieren los discos de Pi a Pf, entonces T1 = 1 y T2 = 3 y
añadimos T0 = 0.
• Como observamos en este ejemplo, determinar el tiempo de
recorrido de un procedimiento recursivo requiere más trabajo
que analizar procedimientos no recursivos.
[Link]
Análisis de procedimientos recursivos
• Requiere asociarle a un procedimiento P un tiempo de recorrido
TP(n) que se desconoce. Después se establece la ecuación de
recurrencia que relaciona a TP(n) con una función de la forma
TQ(k) para los otros procedimientos Q y sus entradas asociadas
k. Si P es directamente recursivo, entonces las Q serán iguales a
las P.
• El valor TP(n) se establece por una inducción sobre el
argumento de tamaño n. Es necesario tener una noción del
tamaño del argumento que garantice que los procedimientos
son llamados con argumentos progresivamente más pequeños
conforme la recursión procede.
[Link]
• Una vez que se tiene una noción del tamaño de los
argumentos, se deben considerar los siguientes casos:
1. El tamaño del argumento es suficientemente pequeño que no
se realizarán llamadas recursivas. Este caso será entonces la
base de la definición inductiva.
2. El tamaño del argumento es suficientemente grande que se
realizarán llamadas recursivas. Sin embargo se debe asumir que
siempre que P realice llamadas recursivas así mismo o a otro
procedimiento Q serán hechas con argumentos más pequeños.
Este caso corresponde a el paso inductivo.
[Link]
• La ecuación de recurrencia se obtiene examinando el código del
procedimiento P y haciendo lo siguiente:
a. Para cada llamada al procedimiento Q en una expresión
(recuerde que Q puede ser P), use TQ(k) como el tiempo de
recorrido de la llamada, donde k es el tamaño del argumento de
la llamada a Q.
b. Evalúe el tiempo de corrida del cuerpo del procedimiento P, pero
dejando los términos como TQ(k) como funciones desconocidas.
Se debe analizar P dos veces, en una se asume que no se hacen
llamadas recursivas y en la otra sí.
c. En las expresiones para el tiempo de recorrido de P, sustituya los
términos en notación O, como O(f(n)) por una constante
especifica del número de veces c(f(n)).
d. Si a es el valor base del tamaño de la entrada, haga TP(a) igual
a la expresión resultante del paso c) cuando se asume que no
hay llamadas recursivas. De la misma forma, haga Tp(n) igual a
la expresión encontrada en c) cuando hay llamadas recursivas.
[Link]
• El tiempo total de recorrido del programa será la solución a la
ecuación de recurrencia.
• Ejemplo : En la ecuación de recurrencia para las Torres de Hanoi,
transferir los n - 1 discos de Pi a Pa se requieren Tn-1 movimientos.
Mover el disco n de Pi a Pf requiere un sólo movimiento y
transferir los n - 1 discos de Pa a Pf requiere otros Tn-1
movimientos. Entonces se puede transferir n discos (n > 0) en a
lo más 2Tn-1+1 movimientos. Esto se puede indicar de la siguiente
forma: Tn ≤ 2Tn-1+1 para n > 0. Al añadir la solución trivial para n
= 0 obtenemos el siguiente conjunto de igualdades, las cuales se
denominan relación de recurrencia o ecuación de recurrencia.
T0 = 0
Tn =2Tn-1 + 1 para n > 0
[Link]
• Esta recurrencia cumple para los casos 1 y 2. La recurrencia nos
permite calcular Tn para cualquier n. Pero cuando n es grande
es muy engorrosa calcularla, por ello es necesario resolver la
recurrencia. Para ello volvemos a los casos pequeños y
observamos que:
T3 =2 * 3 + 1=7
T4 =2 * 7 + 1=15
T5 =2 * 15 + 1=31
[Link]
• Ejemplo : Factorial de un número
function fact(n:integer) : integer;
begin
1. if n <= 1 then
2 fact:=1;.
else
3. fact:= n * fact (n-1)
end;
[Link]
• Obtener la ecuación de recurrencia para T(n)
– Base : n = 1 : El factorial ejecuta las líneas 1 y 2 por lo que
T(1) = 2; O(1).
– Paso inductivo n > 1 : Se ejecutan las líneas 1 y 3, la
línea 1 toma una unidad de tiempo y la línea 3 toma 1
unidad para la asignación más T(n-1).
– Entonces obtenemos la siguiente ecuación:
[Link]
• Ejercicio : Calcule la ecuación de recurrencia del siguiente
programa:
function fibonacci(n:integer): integer;
begin
1. if n <= 2 then
2. fibonacci := 1
else
3. fibonacci := fibonacci(n-1) + fibonacci (n-2)
end.
[Link]
• base 1 ≤ n ≤ 2 :
Fibonacci ejecuta las líneas 1 y 2 lo cual nos da T(1) = 2 y
T(2) = 2
• paso inductivo n > 2 :
Se ejecuta la línea 3, T(n - 1) + T(n - 2)
• La ecuación de recurrencia es:
[Link]
Solución de recurrencias
• Existen 3 métodos que permiten resolver las ecuaciones de
recurrencia:
– Método de iteración (Expansión).
– Método de substitución .
– Método maestro.
[Link]
Método de iteración
• Al calcular la complejidad de los algoritmos recursivos
frecuentemente se encuentran recurrencias del tipo:
• Este método consiste en expandir la recurrencia para encontrar
patrones.
[Link]
Dada la siguiente ecuación:
[Link]
Lo que se quiere calcular es:
T(n) = 2T(n/2) + c2n (1)
Como donde está T(n) se tiene el valor de n/2, se asume este
valor como una cota superior de la función, por lo tanto se
reemplaza n por n/2 y se obtiene:
T(n/2) = 2T(n/4) + c2n/2 (2)
[Link]
Luego se despeja se debe despejar T(n), utilizando la
función 2 y 1, de lo que se obtiene:
T(n) = 2 (2T(n/4) + c2n/2) + c2n (3)
T(n) = 4T(n/4) + 2c2n
[Link]
Tal como se observa, donde se quiere calcular T(n) se tiene el
valor de n/4, se asume este valor como una cota superior de la
función, por lo tanto realiza el mismo procedimiento anterior y
se obtiene:
T(n) = 8T(n/8) + 3 c2n
Ahora es posible determinar un patrón:
T(n) = 2kT(n/2k) + kc2n
[Link]
Este proceso terminará tan pronto como se alcance T(1) al lado
derecho. Al analizar las dos funciones obtenidas:
c1 si n = 1
T(n) =
2kT(n/2k) + kc2n si n>1
Se tiene que T(n) = O(1) + O(logn) * O(n)
T(n) = O(nlogn)
[Link]
c1 si n<=1
T(n) =
T(n-1) + c2 si n > 1
La recurrencia a calcular es T(n) = T(n-1) + c2
Se asume que n-1 es una cota superior, por lo que se reemplaza
este valor en n y se obtiene:
T(n) = T(n-2) + c2
[Link]
T(n-1) = T(n-2) + c2
T(n) = (T(n -2) + c2) + c2
T(n) = T(n-2) + 2c2
T(n-3) = T(n-3) + c2
T(n) = (T(n-3) + c2) + 2c2
T(n) = T(n-3) + 3c2
T(n) = T(n-k) + kc2
[Link]
Por lo tanto lo que se desea calcular es el T(n) de :
c1 si n<=1
T(n) =
T(n-k) + kc2 si n > 1
T(n) = O(1) + O(n) * O(1)
Finalmente, se concluye que T(n) = O(n)
[Link]
Método de Sustitución
• Consiste en probar una solución en la fórmula de recurrencia,
por ejemplo
[Link]
Para este caso se sabe que T(n) = (nlogn) + n
Si n = 1, T(n) = 1:
1log1 + 1 = 0 + 1 = 1 (Verifica)
Como n/2 < n
Por inducción
T(n/2) = (n/2)log(n/2) + n/2
[Link]
Si se reemplaza en la función original, se obtiene:
T(n) = 2((n/2) log (n/2) + n/2) + n
= (n log n/2 + n) + n
= n(logn – log2) + 2n
= n(logn – 1) + 2n
= (n nlogn – n) + 2n
= nlogn + 2n
T(n) = O(nlogn)
[Link]
Método Maestro
• Teorema : Sea
donde a ≥ 1 y b > 1 son constantes y f(n) es una función
asintótica positiva. (Esta recurrencia describe el tiempo de
recorrido de un algoritmo que divide un problema de tamaño n
en “a” subproblemas de tamaño n/b, donde a y b son
constantes positivas. Los “a” subproblemas son resueltos
recursivamente en un tiempo T(n/b). El costo de dividir el
problema y combinar los resultados de los subproblemas es
descrito por la función f(n)).
[Link]
Método Maestro
Teorema: Sea:
T(n) = aT(n/b) + nk
Si a >= 1 y b > 1
Entonces:
Caso 1: Si a > bk entonces T(n) pertenece al O(nlogba)
Caso 2: Si a = bk entonces T(n) pertenece al O(nklogn)
Caso 3: Si a < bk entonces T(n) pertenece al O(nk)
[Link]
Ejemplo
Lo que se quiere calcular es T(n) = 2T(n/2) + c2n, se tiene que:
a=2
b=2
k=1
[Link]
Ejemplo
De esto se obtiene que a = bk , por lo que se está en
presencia del caso 2.
Esto indica que el algoritmo es de O(n1logn)
Lamentablemente no todas las recurrencias tienen la forma
que requiere el teorema maestro, por lo que a veces no queda
más remedio que aplicar el “método de expansión de
recurrencias o iterativo”.
[Link]