7 recursividad c++

7/31/2019 7 Recursividad C++

1/40

21/10/2012Mg. Edgar Ruiz Lizama 1

UNMSMFACULTAD DE INGENIERIA INDUSTRIAL

ALGORITMOS Y PROGRAMACION


2/40

La recursividad, es un conceptomuy importante en matemticas, pues

muchas definiciones se sustentan en larecursividad. Se dice que un objeto es

recursivo, cuando en parte esta formado odefinido en trminos de s mismo.



3/40

a) t=0 es un rboldenominado rbol

vaco.b) Si t1 y t2son rboles,

entonces lasestructuras formadas

por un nodo con dosrbolesdescendientestambin son un rbol.


t

t1

t2


4/40

a) 0 es un nmero naturalb) El sucesor de un nmero natural es otro

nmero natural.



5/40


0);1(*

0;1)(

nsinFactn

nsinFact

El clculo manual para el factorial de 5 se presenta a

continuacin y luego el programa que implementa la

definicin recursiva para el factorial.


6/40

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





120 es el valor final devuelto

( 1 )

( 2 )

( 3 )

( 4 )

( 5 )

( 6 )

(a) Secuencia de llamadas recursivas (b) Valores devueltos en cada llamada

recursiva



7/40

#include //funcion factorial recursivo

using namespace std;float fact(int n);int main() //recur1.cpp{int n;coutn;cout


8/4021/10/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 definicin recursiva

viene a continuacin.


9/40

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



10/40

#include // funcion fibonacci recursivafloat fibo(int n);

using namespace std;int main() //recur2.cpp{int n;coutn;

cout


11/4021/10/2012Mg. Edgar Ruiz Lizama 11


12/40

1. El caso Base: Es el caso trivial

2. El caso general: Es el que se acerca al

caso base.


Sin duda la utilidad de la recursin radica en laposibilidad de expresar un conjunto infinito de

objetos mediante una proposicin finita.


13/40

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.



14/40


1);1,(

1;),(

bsibaMultipa

bsiabaMultip

La prueba para multiplicar 6 x 4 y el programa

que implementa la definicin recursiva para lamultiplicacin de dos nmeros enteros viene a

continuacin.


15/40

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!.



16/40

//multiplicacion a*b recursiva#include

int multrec(int a, int b);using namespace std;int main(){

int a, b;couta>>b;cout


17/40


0);(

0;1

1

nsiXX

nsiX

n

n

La prueba manual para elevar 2 a la 4 y el

programa que implementa la definicinrecursiva para la potenciaXa la n, viene a

continuacin.


18/40


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


19/40

//funcion potencia x a la n

#include

float potenrec(float x, int n);

using namespace std;int main() //recur4.cpp

{

int x, n;

coutx>>n;

cout


20/40


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 15 21

a[0] a[1] a[2] a[3] a[n-2] a[n-1]

. . .


21/40

1);1,(]1[

1];0[),(

nsinaSumarecna

nsianaSumarec


El programa que implementa la definicin recursivapara la suma de los n, elementos de un array viene a

continuacin.


22/40

//sumar recursivamente los elementos de un array#include

int sumarec(int a[], int n);

using namespace std;int main(){

int a[] = {1,2,3,4,5};int n = 5;

cout


23/40

Mximo con 1 elemento: Mximo(a,1) = a[0]

Mximo con2 elementos: Mximo(a,2) = Mximo(a[1], Mximo(a,1))

Mximo con3 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))


7 3 5 95 15 25

a[0] a[1] a[2] a[3] a[n-2] a[n-1]

. . .

El programa que implementa la funcin recursiva para

hallar el mximo valor en una array de n, elementos es


24/40

//encuentra recursivamente el maximo elemento de un array#include const int MAX=20;int max(int n,int x[]);using namespace std;

int main() //recur8.cpp E. Raffo Lecca{int x[MAX], n;coutn;for (int i=0; i>x[i];

cout


25/40

//imprime una cadena en reversa

#include

#include

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


26/40

void reversa_frase(int n)

{

char s[MAX];

if (n>1)

{ gets(s);

reversa_frase(n-1);}

else

gets(s);

puts(s);

}



27/40



28/40

//cuenta recursivamente la ocurrencia de un caracter en una cadena#include #include // para getchar()int contador(char ch, char s[]);using namespace std;int main() //recur6.cpp{ char ch, s[80];

cout


29/40

int contador(char ch, char s[])

{

if (s[0]=='\0')

return 0; //caso base

elseif (ch==s[0]) //posicion actual

return 1+contador(ch,&s[1]); //incrementar en 1

else

return contador(ch,&s[1]);

}



30/40



31/40

#include

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


32/40

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


33/40

Supngase que se deposita un monto mpara lo cualse recibe i% de inters anual. Se pide determinarmediante la recursividad el capital que se tendr alcabo de naos.

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

Co = 4000 //capital inicialC1 = Co + Co*10% //capital al finalizar el 1 aoC2 = C1 + C1*10% //capital al finalizar el 2 aoC2 = C2 + C2*10% //capital al finalizar el 3 ao


(Tomado de la referencia nmero 1)


34/40

De lo anterior puede ahora plantearse la siguiente

relacin recursiva


0si);1(*)1(

0si;

)( nnCapitalreci

nm

nCapitalrec


35/40

capitalRec(n,m,i)

if n = 0 then

capitalRec = melse

capitalRec = (1+i)*capitalRec(n-1,m,i)



36/40

Paso n Pila CapitalRec0 4

1 4 1.10

2 3 1.10,1.103 2 1.10,1.10,1.104 1 1.10,1.10,1.10,1.10

5 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.10

9 4 5856=5324*1.10



37/40


Capital Rec.(4)

1.10*Capital Rec.(3)




4000

5856.4 (Valor final devuelto)

Capital Rec.(4)

1.10*5324=5856.4 es devuelto


1.10*4840=5324 es devuelto


1.10*4400=4840 es devuelto


1.10*4000=4400 es devuelto


4000 es devuelto

4000

(a) Secuencia de llamadas

recursivas

(b) Valores

devueltos en cada

llamada recursiva


38/40

#include #include

// capital recursivofloat CapitalRec(int n,float m, float x);using namespace std;int main() //capitrec.cpp{

int n;float m, i;

coutm;coutn;couti;

cout


39/40

float CapitalRec(int n,float m,float i)

{

if (n==0)

return m;

else

return (1.0+i)*CapitalRec(n-1,m,i);

}



40/40

ERL/2011

7 recursividad c++

Documents