UNMSM FACULTAD DE INGENIERIA INDUSTRIAL ALGORITMOS Y PROGRAMACION

Mg. Edgar Ruiz Lizama

21/10/2012

DEFINICIN: La recursividad, es un concepto muy importante en matemticas, pues muchas definiciones se sustentan en la recursividad. Se dice que un objeto es recursivo, cuando en parte esta formado o definido en trminos de s mismo.

Mg. Edgar Ruiz Lizama

21/10/2012

a)

b)

t=0 es un rbol denominado rbol vaco. Si t1 y t2son rboles, entonces las estructuras formadas por un nodo con dos rboles descendientes tambin son un rbol.

t1

t2

Mg. Edgar Ruiz Lizama

21/10/2012

a) b)

0 es un nmero natural El sucesor de un nmero natural es otro nmero natural.

Mg. Edgar Ruiz Lizama

21/10/2012

si n0 1; Fact(n) n0 n * Fact(n 1); si

El clculo manual para el factorial de 5 se presenta a continuacin y luego el programa que implementa la definicin recursiva para el factorial.

Mg. Edgar Ruiz Lizama

21/10/2012

120 es el valor final devuelto 5! 5! 5!=5*24=120 es devuelto (1) 5*4! 5*4! 4!=4*6=24 es devuelto (2) 4*3! 4*3! 3!=3*2=6 es devuelto (3) 3*2! 3*2! 2!=2*1=2 es devuelto (4) 2*1! 2*1! 1!=1*1=1 es devuelto (5) 1*0! 1*0! 1 es devuelto (6) 1 Caso base 1

(a) Secuencia de llamadas recursivas

(b) Valores devueltos en cada llamada recursiva

Mg. Edgar Ruiz Lizama

21/10/2012

#include <iostream> //funcion factorial recursivo using 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; else return n*fact(n-1); }

Mg. Edgar Ruiz Lizama

21/10/2012

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55...........

si n 0 o n 1 n; Fibo(n) si n 1 Fibo(n 1) Fibo(n 2);
El programa que implementa esta definicin recursiva viene a continuacin.
Mg. Edgar Ruiz Lizama 21/10/2012 8

fib(4)

return

fib(2)

fib(3)

return fib(1)

fib(0)

return

fib(2)

fib(1)

return 1

return 0

return

fib(1)

fib(0)

return 1

return 1

return 0

Mg. Edgar Ruiz Lizama

21/10/2012

#include <iostream> // funcion fibonacci recursiva float 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; else return fibo(n-1)+fibo(n-2); }

Mg. Edgar Ruiz Lizama

21/10/2012

10

Mg. Edgar Ruiz Lizama

21/10/2012

11

1. 2.

El caso Base: Es el caso trivial El caso general: Es el que se acerca al caso base.

Sin duda la utilidad de la recursin radica en la posibilidad de expresar un conjunto infinito de objetos mediante una proposicin finita.
Mg. Edgar Ruiz Lizama 21/10/2012 12

1. 2. 3.

4.
5.

Dividir el problema en dos partes. Tener un caso base trivial. Combinar la regla de paro usando if. Verificar que la recursion pueda terminar. Dibujar un rbol de recursion.

Mg. Edgar Ruiz Lizama

21/10/2012

13

si b 1 a; Multip(a, b) a Multip(a, b 1);

si b 1

La prueba para multiplicar 6 x 4 y el programa que implementa la definicin recursiva para la multiplicacin de dos nmeros enteros viene a continuacin.
Mg. Edgar Ruiz Lizama 21/10/2012 14

Sea a=6 y b=4 prod(6,4)=6+prod(6,3) prod(6,3)=6+prod(6,2) prod(6,2)=6+prod(6,1) prod(6,1)=6 prod(6,2)=6+6 prod(6,3)=6+12 =6+18 prod(6,4)=24 Rpta!.
Mg. Edgar Ruiz Lizama 21/10/2012 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; else return (a + multrec(a,b-1)); }
Mg. Edgar Ruiz Lizama 21/10/2012 16

si 1; n 1 ); X ( X

n0 si n 0

La prueba manual para elevar 2 a la 4 y el programa que implementa la definicin recursiva para la potencia X a la n, viene a continuacin.
Mg. Edgar Ruiz Lizama 21/10/2012 17

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
Mg. Edgar Ruiz Lizama 21/10/2012 18

//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; else return (x*potenrec(x,n-1)); }

Mg. Edgar Ruiz Lizama

21/10/2012

19

a[0] 1

a[1] 3

a[2] 5

a[3] 7 . . .

a[n-2] a[n-1] 15 21

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)
Mg. Edgar Ruiz Lizama 21/10/2012 20

n 1 a[0]; si Sumarec(a, n) a[n 1] Sumarec(a, n 1);

si n 1

El programa que implementa la definicin recursiva para la suma de los n, elementos de un array viene a continuacin.
Mg. Edgar Ruiz Lizama 21/10/2012 21

//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]; else return (a[n-1] + sumarec(a,n-1)); }
Mg. Edgar Ruiz Lizama 21/10/2012 22

a[0] 7

a[1] 3

a[2] 5

a[3] 95 . . .

a[n-2] a[n-1] 15 25

Mximo con 1 elemento: Mximo(a,1) = a[0] Mximo con 2 elementos: Mximo(a,2) = Mximo(a[1], Mximo(a,1)) Mximo con 3 elementos: Mximo(a,3) = Mximo(a[2], Mximo(a,2)) ... Mximo con n elementos: Mximo(a,n) = Mximo(a[n-1], Mximo(a,n-1))

El programa que implementa la funcin recursiva para hallar el mximo valor en una array de n, elementos es
Mg. Edgar Ruiz Lizama 21/10/2012 23

//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]; else return max(n-1,x); }

Mg. Edgar Ruiz Lizama

21/10/2012

24

//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; }

Mg. Edgar Ruiz Lizama

21/10/2012

25

void reversa_frase(int n) { char s[MAX]; if (n>1) { gets(s); reversa_frase(n-1); } else gets(s); puts(s); }

Mg. Edgar Ruiz Lizama

21/10/2012

26

Mg. Edgar Ruiz Lizama

21/10/2012

27

//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; }

Mg. Edgar Ruiz Lizama

21/10/2012

28

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]); }

Mg. Edgar Ruiz Lizama

21/10/2012

29

Mg. Edgar Ruiz Lizama

21/10/2012

30

#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; }

Mg. Edgar Ruiz Lizama

21/10/2012

31

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)); }

Mg. Edgar Ruiz Lizama

21/10/2012

32

(Tomado de la referencia nmero 1)

Supngase que se deposita un monto m para lo cual se recibe i % de inters anual. Se pide determinar mediante la recursividad el capital que se tendr al cabo de n aos.

Solucin: Asuma que m = 4000 y un inters i = 10%

Co = 4000 C1 = Co + Co*10% C2 = C1 + C1*10% C2 = C2 + C2*10% //capital //capital //capital //capital inicial al finalizar el 1 ao al finalizar el 2 ao al finalizar el 3 ao
21/10/2012 33

Mg. Edgar Ruiz Lizama

De lo anterior puede ahora plantearse la siguiente relacin recursiva

m; si n 0 Capitalrec(n) (1 i) * Capitalrec(n 1); si n 0

Mg. Edgar Ruiz Lizama

21/10/2012

34

capitalRec(n,m,i) if n = 0 then capitalRec = m else capitalRec = (1+i)*capitalRec(n-1,m,i)

Mg. Edgar Ruiz Lizama

21/10/2012

35

Paso 0 1 2 3 4 5 6 7 8 9

n 4 4 3 2 1 0 1 2 3 4

Pila
1.10 1.10,1.10 1.10,1.10,1.10 1.10,1.10,1.10,1.10 1.10,1.10,1.10,1.10 1.10,1.10,1.10 1.10,1.10 1.10

CapitalRec

4000 4400=4000*1.10 4840=(4400)*1.10 5324=4840*1.10 5856=5324*1.10

Mg. Edgar Ruiz Lizama 21/10/2012 36

(a) Secuencia de llamadas recursivas

Capital Rec.(4)

5856.4 (Valor final devuelto) Capital Rec.(4) 1.10*5324=5856.4 es devuelto 1.10*Capital Rec.(3)

1.10*Capital Rec.(3)
1.10*Capital Rec.(2) 1.10*Capital Rec.(1) 1.10*Capital Rec.(0) 4000 (b) Valores devueltos en cada llamada recursiva

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
Mg. Edgar Ruiz Lizama 21/10/2012 37

#include <iostream> #include <stdlib.h> // capital recursivo float 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 aos: "; cin>>n; cout<<"\nIngrese porcentaje o interes anual: "; cin>>i; cout<<"\nEl capital al cabo de "<<n<<" aos es = $"<< CapitalRec(n,m,i); cout<<endl<<endl; return 0; }

Mg. Edgar Ruiz Lizama

21/10/2012

38

float CapitalRec(int n,float m,float i) { if (n==0) return m; else return (1.0+i)*CapitalRec(n-1,m,i); }

Mg. Edgar Ruiz Lizama

21/10/2012

39

1. 2. 3.

4.
5. 6. 7. 8.

Cairo O. Y Guardati S. Estructura de datos 2da. Ed. Editorial McGrawHill. Mxico 2002. Deitel y Deitel, Como programar en C++ 4ta. ed. Editorial Prentice Hall. Mxico, 2003. Langsam; Augenstein; y Tenenbaum, Estructuras de Datos con C++Editorial Prentice Hall, Mxico 1996. Raffo Lecca E. Turbo C 3.0 Raffo Lecca Editores, Lima,1995. Ruiz Lizama Edgar, Programacin con C++ 1ra. ed. Fondo Editorial de la UNMSM., Lima Per, 2009 Ruiz Lizama Edgar, Curso de Lenguaje C 1ra. ed. Facultad de Ingeniera Industrial UNMSM. Lima, 1999. Savitch Walter, Resolucin de problemas con C++ 2da. Ed. Editorial Pearson de Mxico, 2000. Sedgewick Algoritmos en C++ 1ra. Ed. Addison Wesley Iberoamericana U.S.A. 1995.

ERL/2011

Mg. Edgar Ruiz Lizama

21/10/2012

40