Sesión 07_Mg Orleans Gálvez Tapia

Vista previa del material en texto

ANÁLISIS DE ALGORITMOS Y 
ESTRATEGIAS DE PROGRAMACIÓN
Docente: 
Mg. Gálvez Tapia Orleans Moisés
CIP. 171497
UNIDAD 1:
LA COMPLEJIDAD ALGORÍTMICA Y 
PRINCIPALES ESTRATEGIAS DE 
PROGRAMACIÓN
SEMANA 07: Algoritmos recursivos
¿Qué es un algoritmo 
recursivo?
SABERES PREVIOS
AGENDA:
1. Partes de método recursivo
2. Ejemplo 01 - cálculo de una potencia en Python y Java
3. Ejemplo 02 - cálculo del factorial en Python y Java
4. Ejemplo 03 - cálculo del Fibonacci en Python y Java
5. Ejemplo 04 - cálculo de la serie de Fibonacci en Python y Java
6. Conclusiones
7. Referencias Bibliográficas
LOGRO DE LA SESIÓN
Al término de la clase, el estudiante implementa algoritmos 
recursivos en Python y Java mostrando dominio técnico del 
lenguaje y una lógica coherente.
Fuente: https://www.youtube.com/watch?v=vPEJSJMg4jY
RECURSIVIDAD
https://www.youtube.com/watch?v=vPEJSJMg4jY
RECURSIVIDAD
Dentro de una función recursiva suelen distinguirse dos partes:
o Los casos base: Son aquellos que para su solución no requieren utilizar la función que se está definiendo.
o Los casos recursivos: Son aquellos que sí que requieren utilizar la función que se está definiendo.
Una función es recursiva cuando el
cuerpo de la función utiliza a la propia
función
EJEMPLO 1 - CÁLCULO DE LA POTENCIA (𝒃𝒏)
Fuente: https://larepublica.pe/videos/espectaculos/2021/12/09/milagros-leiva-guido-bellido-incomoda-a-la-periodista-con-pregunta-matematica
Vamos a calcular una potencia (cualquier
base elevada a cualquier exponente),
mediante un algoritmo recursivo en Python.
https://larepublica.pe/videos/espectaculos/2021/12/09/milagros-leiva-guido-bellido-incomoda-a-la-periodista-con-pregunta-matematica
EJEMPLO 1 - CÁLCULO DE LA POTENCIA (𝒃𝒏)
Caso Base
(caso para el cual existe un 
resultado directo 𝟐𝟎=1)
Caso Recursivo
(la función se llama así misma con los 
parámetros decrementados)
EJEMPLO 1 - CÁLCULO DE LA POTENCIA (𝒃𝒏)
EJEMPLO 1 - CÁLCULO DE LA POTENCIA (𝒃𝒏)
EJEMPLO 2 - CÁLCULO DEL FACTORIAL (𝒏!)
Caso Base
(caso para el cual existe un 
resultado directo 𝟎!=1)
Caso Recursivo
(la función se llama así misma con los 
parámetros decrementados)
EJEMPLO 2 - CÁLCULO DEL FACTORIAL (𝒏!)
EJEMPLO 2 - CÁLCULO DEL FACTORIAL (𝒏!)
EJEMPLO 3 - CÁLCULO DEL FIBONACCI DE UN NÚMERO
EJEMPLO 3 - CÁLCULO DEL FIBONACCI DE UN NÚMERO
𝒇𝒏= 𝒇𝒏−𝟏+ 𝒇𝒏−𝟐
𝑓0 = 0
𝑓1 = 1
𝑓2 = 𝑓1+ 𝑓0 = 1
𝑓3 = 𝑓2+ 𝑓1 = 2
𝑓4 = 𝑓3+ 𝑓2 = 3
…
0 1 1 2 3 5 8 13 21 34 55 89
fibo[0] fibo[1] fibo[2] fibo[3] fibo[4] fibo[5] fibo[6] fibo[7] fibo[8] fibo[9] fibo[10] fibo[11]
fibo(0) = 0
fibo(1) = 1
public int fibonacci (int n){
…
if (n==0 || n==1)
return n;
else{
…
}
}
EJEMPLO 3 - CÁLCULO DEL FIBONACCI DE UN NÚMERO
Forma Iterativa
0 1 1 2 3 5 8 13 21 34 55 89
fibo[0] fibo[1] fibo[2] fibo[3] fibo[4] fibo[5] fibo[6] fibo[7] fibo[8] fibo[9] fibo[10] fibo[11]
fibo(9) = ?
i
ant1 ant2
termino = ant1 + ant2
EJEMPLO 3 - CÁLCULO DEL FIBONACCI DE UN NÚMERO
0 1 1 2 3 5 8 13 21 34 55 89
fibo[0] fibo[1] fibo[2] fibo[3] fibo[4] fibo[5] fibo[6] fibo[7] fibo[8] fibo[9] fibo[10] fibo[11]
i
ant1 ant2
termino = ant1 + ant2
EJEMPLO 3 - CÁLCULO DEL FIBONACCI DE UN NÚMERO
fibo(9) = ?
0 1 1 2 3 5 8 13 21 34 55 89
fibo[0] fibo[1] fibo[2] fibo[3] fibo[4] fibo[5] fibo[6] fibo[7] fibo[8] fibo[9] fibo[10] fibo[11]
i
ant1 ant2
termino = ant1 + ant2
EJEMPLO 3 - CÁLCULO DEL FIBONACCI DE UN NÚMERO
fibo(9) = ?
0 1 1 2 3 5 8 13 21 34 55 89
fibo[0] fibo[1] fibo[2] fibo[3] fibo[4] fibo[5] fibo[6] fibo[7] fibo[8] fibo[9] fibo[10] fibo[11]
i
ant1 ant2
termino = ant1 + ant2
fibo(9) = ?
EJEMPLO 3 - CÁLCULO DEL FIBONACCI DE UN NÚMERO
0 1 1 2 3 5 8 13 21 34 55 89
fibo[0] fibo[1] fibo[2] fibo[3] fibo[4] fibo[5] fibo[6] fibo[7] fibo[8] fibo[9] fibo[10] fibo[11]
i
ant1 ant2
termino = ant1 + ant2
fibo(9) = ?
EJEMPLO 3 - CÁLCULO DEL FIBONACCI DE UN NÚMERO
0 1 1 2 3 5 8 13 21 34 55 89
fibo[0] fibo[1] fibo[2] fibo[3] fibo[4] fibo[5] fibo[6] fibo[7] fibo[8] fibo[9] fibo[10] fibo[11]
i
ant1 ant2
termino = ant1 + ant2
fibo(9) = ?
EJEMPLO 3 - CÁLCULO DEL FIBONACCI DE UN NÚMERO
0 1 1 2 3 5 8 13 21 34 55 89
fibo[0] fibo[1] fibo[2] fibo[3] fibo[4] fibo[5] fibo[6] fibo[7] fibo[8] fibo[9] fibo[10] fibo[11]
i
ant1 ant2
termino = ant1 + ant2
fibo(9) = ?
EJEMPLO 3 - CÁLCULO DEL FIBONACCI DE UN NÚMERO
0 1 1 2 3 5 8 13 21 34 55 89
fibo[0] fibo[1] fibo[2] fibo[3] fibo[4] fibo[5] fibo[6] fibo[7] fibo[8] fibo[9] fibo[10] fibo[11]
i
¿Cómo actualizar las variables en cada iteración?
ant1 = ant2
ant2= = termino
termino = ant1 + ant2
ant1 ant2
termino = ant1 + ant2
fibo(9) = ?
EJEMPLO 3 - CÁLCULO DEL FIBONACCI DE UN NÚMERO
0 1 1 2 3 5 8 13 21 34 55 89
fibo[0] fibo[1] fibo[2] fibo[3] fibo[4] fibo[5] fibo[6] fibo[7] fibo[8] fibo[9] fibo[10] fibo[11]
i
ant1 ant2
termino = ant1 + ant2
public int fibonacci(int n){
…
else{
ant1=0; ant2=1;
for(int i=2;i<=n;i++) { 
termino=ant1+ant2;
ant1=ant2;
ant2=termino;
}
return termino;
}
}
fibo(9) = ?
EJEMPLO 3 - CÁLCULO DEL FIBONACCI DE UN NÚMERO
EJEMPLO 3 - CÁLCULO DEL FIBONACCI DE UN NÚMERO
Forma Recursiva
𝒇𝒏= 𝒇𝒏−𝟏+ 𝒇𝒏−𝟐
𝑓0 = 0
𝑓1 = 1
𝑓2 = 𝑓1+ 𝑓0 = 1
𝑓3 = 𝑓2+ 𝑓1 = 2
𝑓4 = 𝑓3+ 𝑓2 = 3
…
EJEMPLO 3 - CÁLCULO DEL FIBONACCI DE UN NÚMERO
Forma Recursiva
𝒇𝒏= 𝒇𝒏−𝟏+ 𝒇𝒏−𝟐
𝑓0 = 0
𝑓1 = 1
𝑓2 = 𝑓1+ 𝑓0 = 1
𝑓3 = 𝑓2+ 𝑓1 = 2
𝑓4 = 𝑓3+ 𝑓2 = 3
…
0 1 1 2 3 5 8 13 21 34 55
s[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10]
¿Cómo obtener un término de la serie de Fibonacci?
public int[] serieFibonacci(int cantidadTerminos)
{ …
int s[]=new int[cantidadTerminos];
if (cantidadTerminos==1){
s[0]=0;
}
else{ …
}
return s;
}
EJEMPLO 4 - CÁLCULO DE LA SERIE DE FIBONACCI
0 1 1 2 3 5 8 13 21 34 55
s[0] s[1] [2] [3] [4] [5] [6] [7] [8] [9] [10]
¿Cómo obtener los 10 primeros 
términos de la serie de Fibonacci?
i
s[i] = s[i-1]+s[i-2]
public int[] serieFibonacci(int cantidadTerminos)
{ …
else{
s[0]=0;
s[1]=1;
for(int i=2;i<= cantidadTerminos -1;i++){
s[i]=s[i-1]+s[i-2];
}
}
return s;
}
s[i] = s[i-1]+s[i-2]
EJEMPLO 4 - CÁLCULO DE LA SERIE DE FIBONACCI
EJEMPLO 4 - CÁLCULO DE LA SERIE DE FIBONACCI
EJEMPLO 4 - CÁLCULO DE LA SERIE DE FIBONACCI
CONCLUSIONES
i. Una función es recursiva cuando el cuerpo de la función utiliza a la propia función.
ii. Dentro de una función recursiva suelen distinguirse dos partes:
o Los casos base: Son aquellos que para su solución no requieren utilizar la función que
se está definiendo.
o Los casos recursivos: Son aquellos que sí que requieren utilizar la función que se
está definiendo.
REFERENCIAS BIBLIOGRÁFICAS
REFERENCIA ENLACE 
Una introducción a las matemáticas para el 
análisis y diseño de algoritmos 
https://elibro.bibliotecaupn.elogim.com/es/lc/upnort
e/titulos/35059
Manual de algorítmica: recursividad, complejidad y 
diseño de algoritmos 
https://elibro.bibliotecaupn.elogim.com/es/lc/upnort
e/titulos/56561
Introducción práctica a la programación con 
Python 
https://elibro.bibliotecaupn.elogim.com/es/lc/upnort
e/titulos/124259
Criptografía sin secretos con Python https://elibro.bibliotecaupn.elogim.com/es/lc/upnort
e/titulos/106497
ACM UVA Online http://uva.onlinejudge.org/
ACM ICPC Competition https://icpc.global/compete/preparation
https://elibro.bibliotecaupn.elogim.com/es/lc/upnorte/titulos/35059
https://elibro.bibliotecaupn.elogim.com/es/lc/upnorte/titulos/35059
https://elibro.bibliotecaupn.elogim.com/es/lc/upnorte/titulos/56561
https://elibro.bibliotecaupn.elogim.com/es/lc/upnorte/titulos/56561
https://elibro.bibliotecaupn.elogim.com/es/lc/upnorte/titulos/124259
https://elibro.bibliotecaupn.elogim.com/es/lc/upnorte/titulos/124259
https://elibro.bibliotecaupn.elogim.com/es/lc/upnorte/titulos/106497
https://elibro.bibliotecaupn.elogim.com/es/lc/upnorte/titulos/106497
http://uva.onlinejudge.org/
https://icpc.global/compete/preparation
	Diapositiva 1
	Diapositiva 2
	Diapositiva 3: UNIDAD 1: LA COMPLEJIDAD ALGORÍTMICA YPRINCIPALES ESTRATEGIAS DE PROGRAMACIÓN
	Diapositiva 4
	Diapositiva 5
	Diapositiva 6
	Diapositiva 7
	Diapositiva 8
	Diapositiva 9
	Diapositiva 10
	Diapositiva 11
	Diapositiva 12
	Diapositiva 13
	Diapositiva 14
	Diapositiva 15
	Diapositiva 16
	Diapositiva 17
	Diapositiva 18
	Diapositiva 19
	Diapositiva 20
	Diapositiva 21
	Diapositiva 22
	Diapositiva 23
	Diapositiva 24
	Diapositiva 25
	Diapositiva 26
	Diapositiva 27
	Diapositiva 28
	Diapositiva 29
	Diapositiva 30
	Diapositiva 31
	Diapositiva 32
	Diapositiva 33
	Diapositiva 37
	Diapositiva 38
	Diapositiva 39