SLIDES - Tecnología Digital V Diseño de Algoritmos (2)

Vista previa del material en texto

RECURSIóN (REPASO)
Tecnología Digital V: Diseño de Algoritmos
Universidad Torcuato Di Tella
Ejemplo: Factorial
Problema
Dado un entero = ≥ 0, devolver =! = ∏=8=1 8.
i n t f a c t o r i a l ( i n t n )
{
i n t r e t = 1 ;
fo r ( i n t i =1 ; i <=n ; ++ i )
r e t = r e t ∗ i ;
re turn r e t ;
}
Se trata de un algoritmo iterativo.
TD5: Diseño de Algoritmos - UTDT 2
Ejemplo: Factorial
# Observación.
fact(=) =
=∏
8=1
8
=
(
1 · 2 · ... · (= − 1)
)
· =
= fact(= − 1) · =
# fact(=) = fact(= − 1) · = es una definición recursiva, pero todavía está
incompleta.
i n t f a c t o r i a l ( i n t n )
{
i n t r e t = f a c t o r i a l ( n−1) ∗ n ;
re turn r e t ;
}
TD5: Diseño de Algoritmos - UTDT 3
Ejemplo: Factorial
# i n t f a c t o r i a l ( i n t n )
{
i n t r e t = f a c t o r i a l ( n−1) ∗ n ;
re turn r e t ;
}
# Ejemplo: Queremos ejecutar fact(3),
pero esto requiere ejecutar fact(2),
que a su vez requiere ejecutar fact(1),
que a su vez requiere ejecutar fact(0),
que a su vez requiere ejecutar fact(−1),
que a su vez...
TD5: Diseño de Algoritmos - UTDT 4
Ejemplo: Factorial
# Nos faltó frenar la recursión: cuando llegamos a fact(0), ya podemos
parar y devolver el resultado (1).
# Esta situación se conoce como el caso base de la recursión.
i n t f a c t o r i a l ( i n t n )
{
i n t r e t ;
i f ( n==0 )
r e t = 1 ; // Caso base
e l s e
r e t = f a c t o r i a l (n−1) ∗ n ; // Caso recurs ivo
return r e t ;
}
TD5: Diseño de Algoritmos - UTDT 5
Ejemplo: Factorial
Sin caso base
Queremos ejecutar fact(3),
pero esto requiere ejecutar fact(2),
que a su vez requiere ejecutar fact(1),
que a su vez requiere ejecutar fact(0),
que a su vez requiere ejecutar fact(−1),
que a su vez...
Con caso base
Queremos ejecutar fact(3),
pero esto requiere ejecutar fact(2),
que a su vez requiere ejecutar fact(1),
que a su vez requiere ejecutar fact(0),
que devuelve 1, lo cual frena la recursión.
Después, a la vuelta de la recursión,
fact(1) retorna 1,
fact(2) retorna 2,
y por último fact(3) retorna 6.
TD5: Diseño de Algoritmos - UTDT 6
Ejemplo: Factorial
=! = 1 · 2 · ... · (= − 1) · =
=! =
=∏
8=1
8
Algoritmo iterativo
i n t f a c t o r i a l ( i n t n )
{
i n t r e t = 1 ;
fo r ( i n t i =0 ; i <=n ; ++ i )
r e t = r e t ∗ i ;
re turn r e t ;
}
=! =
{
1 si = = 0
(= − 1)! · = si = > 0
Algoritmo recursivo
i n t f a c t o r i a l ( i n t n )
{
i f ( n==0 )
re turn 1 ;
e l s e
re turn f a c t o r i a l ( n−1) ∗ n ;
}
TD5: Diseño de Algoritmos - UTDT 7
Recursión
Un objeto o estructura tiene un compor-
tamiento recursivo si se puede definir en base
a dos propiedades:
# Uno (o más) casos simples, denominados
casos base.
# Un conjunto de reglas que reducen todos
los demás casos al caso base.
En la práctica, los pasos a seguir son:
1. Resolver el problema para los casos base.
2. Suponiendo que se tiene resuelto el
problema para instancias de menor
tamaño, utilizar dichas soluciones para
obtener una solución al problema original
(caso recursivo).
Intuitivamente
Importante
La recursión es una alternativa a la iteración, con el mismo poder expresivo.
TD5: Diseño de Algoritmos - UTDT 8
Ejemplo: Suma de Gauss
Problema.
Escribir una función recursiva suma que, dado un entero = ≥ 0, devuelva∑=
8=1 8 = 1 + 2 + · · · + =.
La clave de plantear una recursión suele estar en encontrar una fórmula
recursiva para el cálculo que debemos realizar.
1 + 2 + · · · + = = (1 + 2 + · · · + = − 1) + =
suma(=) = = + suma(= − 1)
i n t gauss ( i n t n )
{
i f ( n == 0 )
re turn 0 ;
e l s e
re turn n + gauss (n−1 ) ;
}
TD5: Diseño de Algoritmos - UTDT 9
Sumar los elementos de un arreglo
Problema
Sumar los elementos de un arreglo de enteros.
Algoritmo iterativo:
i n t sumar ( i n t [ ] A, i n t n )
{
i n t r e t = 0 ;
fo r ( i n t i =0 ; i <n ; ++ i )
r e t += A[ i ] ;
re turn r e t ;
}
TD5: Diseño de Algoritmos - UTDT 10
Sumar los elementos de un arreglo
# Observación. sumar([4,1,3,7]) = 4 + sumar([1,3,7])
# En general, podemos definir sumar en forma recursiva:
sumar(�, =) =
{
0 si n = 0
A[n-1] + sumar(A, n-1) si no
i n t sumar ( i n t [ ] A, i n t n )
{
i f ( n == 0 )
re turn 0 ;
e l s e
re turn = A[n−1] + sumar (A, n−1 ) ;
}
# ¿Cómo es un algoritmo recursivo para encontrar el máximo elemento de
una lista?
TD5: Diseño de Algoritmos - UTDT 11
Conjunto de partes
Definición
Dado un conjunto ( de elementos (números, si resulta más simple) el
conjunto de partes (power set), denotado como P((), es un conjunto de
conjuntos que contiene todos los posibles subconjuntos de ( (incluyendo el
conjunto vacío, ∅).
Veamos un ejemplo. Consideremos ( = {1, 2, 3}. El conjunto P(() se
compone de los siguientes elementos:{
∅, {1}, {2}, {3}, {1, 2}, {2, 3}, {1, 3}, {1, 2, 3}
}
Problema
Dado un cojunto (, queremos implementar una algoritmo para calcular el
conjunto de partes P(().
Pregunta
Si |( | = = (el conjunto tiene = elementos), cuánto vale |P(()|?
TD5: Diseño de Algoritmos - UTDT 12
Conjunto de partes: ejemplo
# Si ( = ∅, entonces P(() = {∅}.
# Si ( = {1}, entonces P(() = {∅, {1}}.
# Consideremos ( = {1, 2}. Veamos de antemano que:
P(() = P({1, 2}) =
{
∅, {1}, {2}, {1, 2}
}
Consideramos ahora (′ = {1}, y por lo tanto ( = (′ ∪ {2}. Veamos que
del punto anterior tenemos que
P((′) = P({1}) =
{
∅, {1}
}
Los restantes elementos los podemos obtener agregando el nuevo
elemento (2) a los conjuntos de P((′):
◦ ∅ ∪ {2} = {2}
◦ {1} ∪ {2} = {1, 2}
Pregunta
Qué regla podemos inferir para la construcción de P(() = P((′ ∪ {2}) en
función de P((′)?
TD5: Diseño de Algoritmos - UTDT 13
Conjunto de partes: ejemplo
Un paso más.
# Consideremos ( = {1, 2, 3}. Veamos de antemano que:
P(() = P({1, 2, 3}) =
{
∅, {1}, {2}, {3}, {1, 2}, {2, 3}, {1, 3}, {1, 2, 3}
}
Consideramos ahora (′ = {1, 2}, y por lo tanto ( = (′ ∪ {3}. Veamos que
del punto anterior tenemos que
P((′) = P({1, 2}) =
{
∅, {1}, {2}, {1, 2}
}
Pregunta
Asumiendo que tenemos P((′), cómo podemos obtener los elementos que
nos faltan?
TD5: Diseño de Algoritmos - UTDT 14
Conjunto de partes: algoritmo recursivo
ConjuntoDePartes(()
if ( = ∅ then
return {∅}
else
Sea 0 ∈ (, y definimos (′ = (\{0}.
) = ConjuntoDePartes((′) ⊲ Llamamos al paso recursivo con (′
)aux = ∅ ⊲ Definimos un conjunto de conjuntos auxiliar
for B ∈ ) do
)aux = )aux ∪ {B ∪ {0}} ⊲ Agregamos 0 a cada elemento de )
end for
return ) ∪ )aux
end if
TD5: Diseño de Algoritmos - UTDT 15