recursividad c++

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.


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.


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


4

3

3. EL FACTORIAL DE UN ENTERO NONEGATIVO


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





120 es el valor final devuelto

( 1 )

( 2 )

( 3 )

( 4 )

( 5 )

( 6 )

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


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

}


7

3. LA SUCESIÓN DE FIBONACCI


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


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

}


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.


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.


13

4. ALGORITMO RECURSIVO PARA LAMULTIPLICACIÓN


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


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

}


16

9

5. FUNCIÓN POTENCIA RECURSIVA XN


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


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

}


19

6. SUMAR RECURSIVAMENTE LOSELEMENTOS DE UN ARRAY


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


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

}


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


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

}


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;

}


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

}


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;

}


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

}


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;

}


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

}


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


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


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


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


36

19


37

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

}


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

}


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


40

recursividad c++

Documents