Algoritmos
Inga. M.A. Sheyla Esquivel
Curso: Algoritmos
Definición: Recursividad
• La recursividad es una característica de los
lenguajes de programación que permite que
un subprograma se invoque a sí mismo.
• En sí es una técnica muy utilizada en la
programación informática y consiste en que
una función se llame a sí misma.
Recursividad
• Una función que se llama a sí misma se llama
Recursiva.
• Es cuando utilizamos el mismo la función que
se está creando dentro de ella misma.
• La Recursividad es una característica aceptada
en C++ existen otros lenguajes de
programación que ésta no es válida.
• Podemos utilizar la recursividad en Funciones
exclusivamente.
Recursividad
• Son un conjunto de instrucciones que
resuelven un problema específico.
• También se pueden utilizar en rutinas,
procedimientos y funciones.
• El uso de recursividad permite la
reutilización de código.
Ejemplos
• Factorial
• Se define como el producto de todos los
números enteros positivos desde 1 hasta n.
• El signo de factorial es el siguiente !
• 5! = 5 x 4 x 3 x 2 x 1= 120
Veamos la secuencia:
Que componentes tiene una función
Recursiva
• Un caso base: Es una solución simple para un
caso particular.
• Una función recursiva: es una solución que
involucra volver a utilizar la función original,
con parámetros que se acercan al caso base.
Pasos del Caso Recursivo
• El procedimiento o función se llama a sí
mismo.
• El problema se resuelve tratando al mismo
problema pero de tamaño menor.
• La manera en la cual el tamaño del problema
disminuye asegura que el caso base
eventualmente se resolverá.
Ejemplo Factorial C++
• #include <iostream>
• #include <stdlib>
• int factorial(int n){
• if (n==1)
• return 1;
• else
• return n * factorial(n-1);
• }
• int main()
• {
• int n;
• cout<<"Ingrese un numero: ";
• cin>>n;
• cout<<"El factorial es: " <<factorial(n) <<endl;
• system("PAUSE");
• }
Sucesión de Fibonacci
• Es una sucesión finita de números naturales.
• 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55…
• Se puede expresar así:
Código en C++
• #include <iostream>
• #include <stdlib>
• int fibonacci(int n)
• {
• if (n<2)
• return n;
• else
• return fibonacci(n-1) + fibonacci(n-2);
• }
• int main()
• {
• int n;
• cout<<"Ingrese un numero: ";
• cin>>n;
• cout<<"La sucesión de Fibonacci es: " <<fibonacci(n) <<endl;
• system("PAUSE");
• }
Juego de las Torres de Hanoi
• Es un juego que consta de varios discos, en éste
caso vamos a hablar de 5 discos y 3 varillas.
• Tiene sus reglas y son las siguientes:
• Los discos se deben mover de la torre A a la torre
C.
• Sólo se puede mover un disco cada vez.
• Un disco de mayor tamaño no puede descansar
sobre uno más pequeño que él mismo.
• Sólo puedes desplazar el disco que se encuentre
arriba en cada torre.
Tarea
• Analice el caso de las Torres de Hanoi y realice
su solución en pseudocódigo, y en código C++
(utilizando una función recursiva).
• Además describa cada uno de los pasos que
realizó para pasar los discos de la torre A para
la torre C.
• Suba su solución a Canvas
Métodos de Ordenamiento
Método de Burbuja
• Es un algoritmo que funciona revisando cada
elemento de la lista que va a ser ordenada con
el siguiente, intercambiándolos de posición si
están en el orden equivocado. Es necesario
revisar varias veces toda la lista hasta que no
se necesiten más intercambios, lo cual significa
que la lista está ordenada.
Ejemplo
4 5 2 1 3
Si
numeroActual > numeroSiguiente
Cambio
Ejemplo
4 5 2 1 3
Si
numeroActual > numeroSiguiente
Cambio
Ejemplo
4 2 5 1 3
Si
numeroActual > numeroSiguiente
Cambio
Ejemplo
4 2 1 5 3
Si
numeroActual > numeroSiguiente
Cambio
Ejemplo
4 2 1 3 5
Si
numeroActual > numeroSiguiente
Cambio
Ejemplo
2 4 1 3 5
Si
numeroActual > numeroSiguiente
Cambio
Ejemplo
2 1 4 3 5
Si
numeroActual > numeroSiguiente
Cambio
Ejemplo
2 1 3 4 5
Si
numeroActual > numeroSiguiente
Cambio
Ejemplo
2 1 3 4 5
Si
numeroActual > numeroSiguiente
Cambio
Ejemplo
1 2 3 4 5
Si
numeroActual > numeroSiguiente
Cambio
Ejemplo
1 2 3 4 5
Ordenado
Si
numeroActual > numeroSiguiente
Cambio
• //Método Burbuja • }
• #include<iostream> –}
• #include<conio> • }
• Int main(){ • Cout<<“Orden
Ascendente: “;
• Int números
[]={4,1,2,3,5}; • For(i=0;i<5;i++){
• Int i, j, aux; • Cout<<números[i] <<“ “;
• //Algoritmo del método • }
de burbuja • Cout<<“Orden
• For(i=0; i<5; i++){ descendente: “;
– For(j=0; j<5;i++){ • For(i=4; i>=0; i++){
• If(números[j] > • Cout<<numeros[i] <<“ “;
numero[j+1]){ • }
– Aux = números[j]; • Getch();
– Numeros[j] =
números[j+1]; • Return 0;
– Numeros[j+1] = aux; • }
Búsqueda Secuencial
• #include <iostream> • if(bandera == 'F'){
• #include <conio> • cout<<"El numero a
• int main(){ buscar no existe en el
• int a[] = {3,4,2,1,5}; arreglo" <<endl;
• int i, dato; • }
• char bandera = 'F'; • else if (bandera =='V'){
• dato = 3; • cout<<"El numero ha sido
en contrado en la
• i=0; posición: " <<i-1<<endl;
• while((bandera =='F') && • }
(i<5)){ • getch();
• if(a[i] == dato){ • return 0;
• bandera = 'V'; • }
• }
• i++;
• }
Búsqueda Secuencial cadenas
• #include <iostream> • i++;
• #include <string> • }
• #include <conio> • if(bandera == 'F'){
• int main(){ • cout<<"El numero a buscar
• string a[] = no existe en el arreglo"
{"azul","blanco","amarillo", <<endl;
"rosado","negro"},dato; • }
• int i; • else if (bandera =='V'){
• char bandera = 'F'; • cout<<"El numero ha sido
• dato = "amarillo"; en contrado en la posición:
• i=0; " <<i-1<<endl;
• while((bandera =='F') && • }
(i<5)){ • getch();
• if(a[i] == dato){ • return 0;
• bandera = 'V'; • }
• }
Archivos
Resultado
Escribir un archivo
• #include <iostream> mi nombre es Sheyla";
• #include <fstream> • [Link]();
• #include <stdlib> • }
• void escribir(){ • int main(){
• ofstream archivo;
• [Link]("[Link]" • escribir();
,ios::out);
• if([Link]()){
• cout<<"No se pudo abrir • system("pause");
el archivo"; • return 0;
• exit(1); • }
• }
• archivo<<"Hola que tal?
Leer un archivo
• #include <iostream> • }
• #include <fstream> • while(![Link]()){
• #include <stdlib> • [Link](cadena,128
• #include <string> );
• void lectura(){ • cout<<cadena<<endl;
• ifstream archivo; • }
• char cadena[128]; • [Link]();
• [Link]("[Link]",i • }
os::in); • int main(){
• if([Link]()){ • lectura();
• cout<<"No se pudo abrir el • system("pause");
archivo"; • return 0;
• exit(1); • }
Añadir texto
• #include <iostream> • }
• #include <fstream> • archivo<<"Hoy es
• #include <stdlib> miércoles";
• #include <string> • [Link]();
• void aniadir(){ • }
• ofstream archivo; • int main(){
• [Link](“[Link] • aniadir();
",ios::app); • system("pause");
• if([Link]()){ • return 0;
• cout<<"No se pudo abrir • }
el archivo";
• exit(1);
Gracias por su Atención
• "Estas cosas os he hablado para que en mí tengáis paz. En el
mundo tendréis aflicción; pero confiad, yo he vencido al
mundo." ([Link] 16:33)
