recursividad c++
Post on 18-Apr-2015
88 Views
Preview:
TRANSCRIPT
1
07/05/2012Mg. Edgar Ruiz Lizama
1
UNMSM –FACULTAD DE INGENIERIA INDUSTRIALALGORITMOS Y PROGRAMACION
RECURSIVIDAD
DEFINICIÓN: La recursividad, es unconcepto muy importante en matemáticas,pues muchas definiciones se sustentan enla recursividad. Se dice que un objeto esrecursivo, cuando en parte esta formado odefinido en términos de sí mismo.
07/05/2012Mg. Edgar Ruiz Lizama
2
2
SON EJEMPLOS DE DEFINICIONES RECURSIVAS:
1. LAS ESTRUCTURAS DE ÁRBOL EN COMPUTACION:SEA T UN ÁRBOL
a) t=0 es un árboldenominado árbolvacío.
b) Si t1 y t2son árboles,entonces lasestructuras formadaspor un nodo con dosárboles descendientestambién son un árbol.
07/05/2012Mg. Edgar Ruiz Lizama
3
t
t1
t2
2. LOS NÚMEROS NATURALES
a) 0 (CERO) es un número naturalb) El sucesor de un número natural es otro
número natural.
c) 0,1,2,3,4,5,6, . . .
07/05/2012Mg. Edgar Ruiz Lizama
4
3
3. EL FACTORIAL DE UN ENTERO NONEGATIVO
07/05/2012Mg. Edgar Ruiz Lizama
5
>−=
=0);1(*
0;1)(
nsinFactn
nsinFact
El cálculo manual para el factorial de 5 se presenta acontinuación y luego el programa que implementa ladefinición recursiva para el factorial.
CALCULO PARA EL FACTORIAL DE 5:
5!
5*4!
3*2!
4*3!
2*1!
1*0!
5!
2*1!
3*2!
4*3!
5*4!
1*0!
1 1Caso base
1 es devuelto
1!=1*1=1 es devuelto
2!=2*1=2 es devuelto
3!=3*2=6 es devuelto
4!=4*6=24 es devuelto
5!=5*24=120 es devuelto
120 es el valor final devuelto
( 1 )
( 2 )
( 3 )
( 4 )
( 5 )
( 6 )
(a) Secuencia de llamadas recursivas (b) Valores devueltos en cada llamadarecursiva
07/05/2012Mg. Edgar Ruiz Lizama
6
4
#include <iostream>//funcion factorial recursivousing namespace std;float fact(int n);int main() //recur1.cpp{
int n;cout<<"Ingrese n : ";cin>>n;cout<<"el factorial de "<<n<<" es: "<<fact(n)<<endl;
return 0;}float fact(int n){
if(n==0)return 1;
elsereturn n*fact(n-1);
}
07/05/2012Mg. Edgar Ruiz Lizama
7
3. LA SUCESIÓN DE FIBONACCI
07/05/2012Mg. Edgar Ruiz Lizama
8
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55...........
>−+−==
=1);2()1(
1o0;)(
nsinFibonFibo
nnsinnFibo
El programa que implementa esta definición recursivaviene a continuación.
5
CONJUNTO DE LLAMADAS RECURSIVAS ALA FUNCIÓN FIBONACCI DE 4
fib(4)
fib(3)fib(2)
fib(0)
fib(1)fib(2)
fib(1)
return 1
return 1
return 0
return +
+
+
return
return
fib(0)fib(1)
return 1 return 0
+return
07/05/2012Mg. Edgar Ruiz Lizama
9
#include <iostream>// funcion fibonacci recursivafloat fibo(int n);using namespace std;int main() //recur2.cpp{
int n;cout<<"Ingrese n : ";cin>>n;cout<<"El numero de Fibonacci es : "<<fibo(n)<<endl;
return 0;}float fibo(int n){
if(n==0 || n==1)return n;
elsereturn fibo(n-1)+fibo(n-2);
}
07/05/2012Mg. Edgar Ruiz Lizama
10
6
EJECUCION DEL PROGRAMA:07/05/2012Mg. Edgar Ruiz Lizama
11
TODA FUNCIÓN RECURSIVA TIENE 2 PARTES:
1. El caso Base: Es el caso trivial2. El caso general: Es el que se acerca al
caso base.
07/05/2012Mg. Edgar Ruiz Lizama
12
Sin duda la utilidad de la recursión radica en laposibilidad de expresar un conjunto infinito deobjetos mediante una proposición finita.
7
PASOS A SEGUIR PARA DESARROLARPROBLEMAS DE RECURSIVIDAD
1. Dividir el problema en dos partes.2. Tener un caso base trivial.3. Combinar la regla de paro usando if.4. Verificar que la recursion pueda
terminar.5. Dibujar un árbol de recursion.
07/05/2012Mg. Edgar Ruiz Lizama
13
4. ALGORITMO RECURSIVO PARA LAMULTIPLICACIÓN
07/05/2012Mg. Edgar Ruiz Lizama
14
>−+=
=1);1,(
1;),(
bsibaMultipa
bsiabaMultip
La prueba para multiplicar 6 x 4 y el programaque implementa la definición recursiva para lamultiplicación de dos números enteros viene acontinuación.
8
DESARROLLO RECURSIVO PARA ELPRODUCTO
Sea a=6 y b=4prod(6,4)=6+prod(6,3)
prod(6,3)=6+prod(6,2)prod(6,2)=6+prod(6,1)
prod(6,1)=6prod(6,2)=6+6
prod(6,3)=6+12=6+18
prod(6,4)=24 Rpta!.
07/05/2012Mg. Edgar Ruiz Lizama
15
//multiplicacion a*b recursiva#include <iostream>
int multrec(int a, int b);using namespace std;int main(){
int a, b;cout<<"Ingrese dos enteros ";cin>>a>>b;cout<<"\nEl producto es "<<multrec(a,b)<<endl;
return 0;}
int multrec(int a, int b){
if (b == 1)return a;
elsereturn (a + multrec(a,b-1));
}
07/05/2012Mg. Edgar Ruiz Lizama
16
9
5. FUNCIÓN POTENCIA RECURSIVA XN
07/05/2012Mg. Edgar Ruiz Lizama
17
>=
=− 0);(
0;11 nsiXX
nsiX
n
n
La prueba manual para elevar 2 a la 4 y elprograma que implementa la definiciónrecursiva para la potencia X a la n, viene acontinuación.
DESARROLLO RECURSIVO PARA LAPOTENCIA
07/05/2012Mg. Edgar Ruiz Lizama
18
potencia (2,4)=2*potencia(2,3)
potencia(2,3)=2*potencia(2,2)
potencia(2,2)=2*potencia(2,1)potencia(2,0)=1
=2*2=>4
=2* 4
=2*8
potencia(2,4)=16
10
//funcion potencia x a la n#include <iostream>
float potenrec(float x, int n);using namespace std;int main() //recur4.cpp{
int x, n;cout<<"Ingrese base y exponente enteros positivos ";cin>>x>>n;
cout<<x<<" a la "<<n<<" = "<<potenrec(x,n)<<endl;return 0;
}float potenrec(float x, int n){
if (n==0)return 1;
elsereturn (x*potenrec(x,n-1));
}
07/05/2012Mg. Edgar Ruiz Lizama
19
6. SUMAR RECURSIVAMENTE LOSELEMENTOS DE UN ARRAY
07/05/2012Mg. Edgar Ruiz Lizama
20
Suma con 1 elemento: suma(a,1) = a[0]
Suma con 2 elementos: suma(a,2) = a[0] + a[1] = a[1] + suma(a,1)
Suma con 3 elementos: suma(a,3) = a[0]+a[1]+a[2] = a[2] +suma(a,2)
. . .
Suma con n elementos:
Suma(a,n) = a[0]+a[1]+a[2]+a[3]+...+a[n-1] = a[n-1] + suma(a,n-1)
1 3 5 7 1 5 2 1
a [ 0 ] a [ 1 ] a [ 2 ] a [ 3 ] a [ n - 2 ] a [ n - 1 ]
. . .
11
LA RELACIÓN DE RECURRENCIA PARA LA SUMARECURSIVA DE UN ARRAY ES:
>−+−=
=1);1,(]1[
1];0[),(
nsinaSumarecna
nsianaSumarec
07/05/2012Mg. Edgar Ruiz Lizama
21
El programa que implementa la definición recursivapara la suma de los n, elementos de un array viene acontinuación.
//sumar recursivamente los elementos de un array#include <iostream>
int sumarec(int a[], int n);using namespace std;int main(){
int a[] = {1,2,3,4,5};int n = 5;
cout<<"Suma de elementos = "<<sumarec(a,n)<<endl;
return 0;}int sumarec(int a[], int n){
if (n == 1)return a[0];
elsereturn (a[n-1] + sumarec(a,n-1));
}
07/05/2012Mg. Edgar Ruiz Lizama
22
12
7. ENCONTRAR EL MÁXIMO VALOR DE UNARREGLO POR RECURSIVIDAD
Máximo con 1 elemento: Máximo(a,1) = a[0]
Máximo con 2 elementos: Máximo(a,2) = Máximo(a[1], Máximo(a,1))
Máximo con 3 elementos: Máximo(a,3) = Máximo(a[2], Máximo(a,2))
. . .
Máximo con n elementos:
Máximo(a,n) = Máximo(a[n-1], Máximo(a,n-1))
07/05/2012Mg. Edgar Ruiz Lizama
23
7 3 5 9 5 1 5 2 5
a [ 0 ] a [ 1 ] a [ 2 ] a [ 3 ] a [ n - 2 ] a [ n - 1 ]
. . .
El programa que implementa la función recursiva parahallar el máximo valor en una array de n, elementos es
//encuentra recursivamente el maximo elemento de un array#include <iostream>const int MAX=20;int max(int n,int x[]);using namespace std;int main() //recur8.cpp E. Raffo Lecca{
int x[MAX], n;cout<<"Cuantos elementos en el array? ";cin>>n;for (int i=0; i<n; i++)
cin>>x[i];cout<<"El maximo elemento es: "<<max(n,x)<<endl;return 0;
}int max(int n,int x[]){
if(n==1)return x[0];
if(x[n-1]>max(n-1,x))return x[n-1];
elsereturn max(n-1,x);
}
07/05/2012Mg. Edgar Ruiz Lizama
24
13
8. INVERTIR UNA CADENA DE CARACTERES ENFORMA RECURSIVA//imprime una cadena en reversa
#include <iostream>#include <stdio.h>
const int MAX = 80;
void reversa_frase(int n);using namespace std;
int main() //reverfra.cpp E. Raffo Lecca{
int n=8; // Hola C++cout<<"Ingrese caracter a caracter con un ENTER cada vez: ";
reversa_frase(n); cout<<endl;return 0;
}
07/05/2012Mg. Edgar Ruiz Lizama
25
CONTINUACIÓN...
void reversa_frase(int n){
char s[MAX];if (n>1)
{ gets(s);reversa_frase(n-1);
}else
gets(s);puts(s);
}
07/05/2012Mg. Edgar Ruiz Lizama
26
14
EJECUCIÓN DEL PROGRAMA07/05/2012Mg. Edgar Ruiz Lizama
27
9. CONTAR LA OCURRENCIA DE UN CARÁCTEREN UNA CADENA/*cuenta recursivamente la ocurrencia de un caracter en una
cadena */#include <iostream>#include <stdio.h> // para getchar()int contador(char ch, char s[]);using namespace std;
int main() //recur6.cpp{ char ch, s[80];
cout<<"ingrese cadena : ";cin.getline(s,80);cout<<"ingrese caracter a contar : ";ch=getchar();cout<<"cantidad de ocurrencias del caracter "<<ch<<" = "
<<contador(ch,s)<<endl;cout<<endl;return 0;
}
07/05/2012Mg. Edgar Ruiz Lizama
28
15
CONTINUACIÓN...
int contador(char ch, char s[])
{
if (s[0]=='\0')
return 0; //caso base
else
if (ch==s[0]) //posicion actual
return 1+contador(ch,&s[1]); //incrementar en 1
else
return contador(ch,&s[1]);
}
07/05/2012Mg. Edgar Ruiz Lizama
29
EJECUCIÓN DEL PROGRAMA07/05/2012Mg. Edgar Ruiz Lizama
30
16
10. BÚSQUEDA BINARIA RECURSIVA
#include <iostream>
//binsearch : busqueda binaria recursiva
int binsearch(int a[],int x,int der, int izq);
using namespace std;
int main() //recur7.cpp E. Raffo Lecca
{
int der=0,izq=6,x=5;
int a[]={1,2,3,4,5,6,7};
cout<<x<<" esta en la posicion "<<binsearch(a,x,der,izq) << endl;
cout<<endl;
return 0;
}
07/05/2012Mg. Edgar Ruiz Lizama
31
CONTINUACIÓN...
int binsearch(int a[],int x,int der,int izq)
{
int mitad;
if(der>izq)
return -1;
mitad=(der+izq)/2;
return (x==a[mitad]?mitad:x<a[mitad]?
binsearch(a,x,der,mitad-1):
binsearch(a,x,mitad+1,izq));
}
07/05/2012Mg. Edgar Ruiz Lizama
32
17
11. CASO DE UNA INVERSIÓN Y EL CÁLCULORECURSIVO PARA EL CAPITAL Y SU INTERÉS
Supóngase que se deposita un monto m para lo cual serecibe i % de interés anual. Se pide determinar mediante larecursividad el capital que se tendrá al cabo de n años.
Solución:Asuma que m = 4000 y un interés i = 10%
Co = 4000 //capital inicialC1 = Co + Co*10% //capital al finalizar el 1° añoC2 = C1 + C1*10% //capital al finalizar el 2° añoC2 = C2 + C2*10% //capital al finalizar el 3° año
07/05/2012Mg. Edgar Ruiz Lizama
33
(Tomado de la referencia número 1)
EN GENERAL:CN=1.10*CN-1
OBTENIDO APARTIR CN=CN-1+CN-1*10%
De lo anterior puede ahora plantearse la siguienterelación recursiva
07/05/2012Mg. Edgar Ruiz Lizama
34
>−+=
=0si);1(*)1(
0si;)(
nnCapitalreci
nmnCapitalrec
18
ALGORITMO
capitalRec(n,m,i)if n = 0 then
capitalRec = melse
capitalRec = (1+i)*capitalRec(n-1,m,i)end
07/05/2012Mg. Edgar Ruiz Lizama
35
SEA N = 4. LA TABLA SIGUIENTE MUESTRA LOS CÁLCULOSQUE SE VAN SUCEDIENDO EN LAS VARIABLES Y LOSVALORES ALMACENADOS EN LA PILA
Paso n Pila CapitalRec0 41 4 1.102 3 1.10,1.103 2 1.10,1.10,1.104 1 1.10,1.10,1.10,1.105 0 1.10,1.10,1.10,1.10 40006 1 1.10,1.10,1.10 4400=4000*1.107 2 1.10,1.10 4840=(4400)*1.108 3 1.10 5324=4840*1.109 4 5856=5324*1.10
07/05/2012Mg. Edgar Ruiz Lizama
36
19
07/05/2012Mg. Edgar Ruiz Lizama
37
Capital Rec.(4)
1.10*Capital Rec.(3)
1.10*Capital Rec.(2)
1.10*Capital Rec.(1)
1.10*Capital Rec.(0)
4000
5856.4 (Valor final devuelto)
Capital Rec.(4)
1.10*5324=5856.4 es devuelto
1.10*Capital Rec.(3)
1.10*4840=5324 es devuelto
1.10*Capital Rec.(2)
1.10*4400=4840 es devuelto
1.10*Capital Rec.(1)
1.10*4000=4400 es devuelto
1.10*Capital Rec.(0)
4000 es devuelto
4000
(a) Secuencia de llamadasrecursivas
(b) Valoresdevueltos en cadallamada recursiva
CÓDIGO DEL PROGRAMA#include <iostream>#include <stdlib.h>// capital recursivofloat CapitalRec(int n,float m, float x);using namespace std;int main() //capitrec.cpp{
int n;float m, i;cout<<"Ingrese el capital: ";cin>>m;cout<<"\nIngrese el tiempo en años: ";cin>>n;cout<<"\nIngrese porcentaje o interes anual: ";cin>>i;cout<<"\nEl capital al cabo de "<<n<<" años es = $"<<
CapitalRec(n,m,i);cout<<endl<<endl;return 0;
}
07/05/2012Mg. Edgar Ruiz Lizama
38
20
CONTINUACIÓN...
float CapitalRec(int n,float m,float i)
{
if (n==0)
return m;
else
return (1.0+i)*CapitalRec(n-1,m,i);
}
07/05/2012Mg. Edgar Ruiz Lizama
39
REFERENCIAS1. Cairo O. Y Guardati S. “Estructura de datos” 2da. Ed. Editorial
McGrawHill. México 2002.2. Deitel y Deitel, “Como programar en C++” 4ta. ed. Editorial Prentice Hall.
México, 2003.3. Langsam; Augenstein; y Tenenbaum, “Estructuras de Datos con
C++”Editorial Prentice Hall, México 1996.4. Raffo Lecca E. “Turbo C 3.0” Raffo Lecca Editores, Lima,1995.5. Ruiz Lizama Edgar, “Programación con C++” 1ra. ed. Fondo Editorial de
la UNMSM., Lima Perú, 20096. Ruiz Lizama Edgar, “Curso de Lenguaje C” 1ra. ed. Facultad de
Ingeniería Industrial UNMSM. Lima, 1999.7. Savitch Walter, “Resolución de problemas con C++” 2da. Ed. Editorial
Pearson de México, 2000.8. Sedgewick “Algoritmos en C++” 1ra. Ed. Addison Wesley Iberoamericana
U.S.A. 1995.
ERL/2012
07/05/2012Mg. Edgar Ruiz Lizama
40
top related