EstructuraDeDatos2 Clase05

Estructura de Datos 2
Algoritmos avanzados

Contenido




Introducción
Recursividad
Algoritmos recursivos
◼

Quicksort

Introducción

Recursividad

Recursividad




Propiedad que tienenlos algoritmos de
poder ser re-invocados sin haber
finalizado el proceso de las sentencias
correspondientes a una invocación previa
de si mismo.
El concepto deriva del de relación de
recurrencia.Recursividad

Recurrencia


Propiedad de aquellas secuencias en las
que cualquier término se puede calcular
conociendo los precedentes.

Recursividad

Relación de recurrencia


Una relación derecurrencia de orden
k, es una ecuación de la forma
F : Rk × R → R
an = F (an-1, an-2 , ..., an-k , n); ∀ n ≥ k



Definiendo las condiciones iniciales
a0 = αn, a1 = α1, ..., ak-1 = αk-1



Contrapartidadiscreta de las ecuaciones
diferenciales.

Recursividad

Ejemplos


Descendientes
Una persona es descendiente del Sr. Díaz
si:
es un hijo del Sr. Díaz, o
◼ es un hijo de un descendiente del Sr.Díaz.
◼



Factorial:
n ϵ ℕ0
◼ n! = n * (n-1)!, n > 0
◼ 0! = 1
◼

Recursividad

Ejemplos (cont.)


an = 3 * an-1 , ∀ n > 0, a0 = 5



Sucesión de Fibonacci
n ϵ ℕ0
◼ Fib(0) = 1
◼

◼

Fib(1) = 1

◼Fib(n) = Fib(n - 1) + Fib(n – 2)

n>1

Recursividad

Características


En todo proceso recursivo se distinguen
dos partes bien diferenciadas:
◼

Caso base: aquel que queda definido en si
mismo.

◼

Casorecursivo: basado en un caso base o
en otro caso recursivo.

Algoritmos recursivos

Algoritmos recursivos


Un método recursivo es aquel que se
llama a sí mismo.



Cuando un método se invoca así mismo
lo hace como si estuviera invocando a
otro método, y en esto se cumplen todas
las reglas de invocación de métodos por
parte de otros métodos.

Algoritmos recursivos

Ejemplo


Simple eincorrecto




public void hacerInfinito() {
/* no existe caso base */
this.hacerInfinito();
}

Factorial


public int factorial(int numero) {
int resultado;
if (numero < 2) {
/* caso base */...