Informatica

Estructuras de Datos

1

La Matrushka es una artesanía tradicional rusa.
Es una muñeca de madera que contiene otra
muñeca más pequeña dentro de sí. Esta
muñeca, también contiene otra muñeca dentro.
Y así, una dentro de otra.

Printed with FinePrint trial version - purchase at www.fineprint.com

2

La recursividad es un concepto fundamental en
matemáticas y en computación.
Es unaalternativa diferente para implementar
estructuras de repetición (ciclos). Los módulos
se hacen llamadas recursivas.
Se puede usar en toda situación en la cual la
solución pueda ser expresada como una
secuencia
de
movimientos,
pasos
o
transformaciones gobernadas por un conjunto de
reglas no ambiguas.
3

Las funciones recursivas se componen de:
Caso base: una solución simple paraun caso
particular (puede haber más de un caso
base). La secuenciación, iteración
condicional y selección son estructuras
válidas de control que pueden ser
consideradas como enunciados.
NOTA: Regla recursiva Las estructuras de control que se pueden
formar combinando de manera válida la secuenciación,
iteración condicional y selección también son válidos.

Printed with FinePrint trialversion - purchase at www.fineprint.com

4

Caso recursivo: una solución que involucra
volver a utilizar la función original, con
parámetros que se acercan más al caso
base. Los pasos que sigue el caso
recursivo son los siguientes:
1. El procedimiento se llama a sí mismo
2. El problema se resuelve, resolviendo el
mismo problema pero de tamaño menor
3. La manera en la cual el tamaño delproblema disminuye asegura que el caso
base eventualmente se alcanzará
5

Escribe un programa que calcule el factorial (!)
de un entero no negativo. He aquí algunos
ejemplos de factoriales:
0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120

2! = 2 * 1!
3! = 3 * 2!
4! = 4 * 3!
5! = 5 * 4!

Printed with FinePrint trial version - purchase at www.fineprint.com

6

(iterativo)int factorial (int n)

int fact = 1;

comienza
fact

for (int i = 1; i 0 (recursión)

N! =

Un razonamiento recursivo tiene dos partes: la base y la
regla recursiva de construcción. La base no es recursiva y
es el punto tanto de partida como de terminación de la
definición.

Printed with FinePrint trial version - purchase at www.fineprint.com

10

Un método recursivo contienedos
elementos básicos que son
fundamentales para su funcionamiento.
Caso Base: Existe al menos una solución
para algún valor determinado.
Progreso: Cualquier llamada a si mismo
debe progresar (acercarse) a un caso base.
Define los elementos básicos de los ejemplos de la
lamina anterior.

Dado un entero no negativo x, regresar el factorial de x fact:
Entrada n entero no nogativo,Salida:entero.
Es importante determinar
un caso base, es decir un
punto en el cual existe una
condición por la cual no se
requiera volver a llamar a
la misma función.

int fact (int n)
{
if (n == 0)
return 1;
else
return fact(n – 1) * n ;
}

Printed with FinePrint trial version - purchase at www.fineprint.com

12

Llamadas recursivas

Resultados de las llamadas recursivas

13Son mas cercanos a la descripción
matemática.
Generalmente mas fáciles de analizar
Se adaptan mejor a las estructuras de
datos recursivas.
Los algoritmos recursivos ofrecen
soluciones estructuradas, modulares y
elegantemente simples.

Printed with FinePrint trial version - purchase at www.fineprint.com

14

 (){
[declaración de variables]
[condición de salida]
[instrucciones][llamada a ()]
return
}
15

Considere la siguiente ecuación recurrente:
an = an-1 + 2n
a0 = 1
Escribe el algoritmo de la solución.

Printed with FinePrint trial version - purchase at www.fineprint.com

16

Para simplificar el código.
Cuando la estructura de datos es recursiva
ejemplo : árboles.

Cuando los métodos usen arreglos largos.
Cuando el método cambia de manera...