recursividad (1).pdf

8192019 Recursividad (1)pdf

httpslidepdfcomreaderfullrecursividad-1pdf 124

Objetivos

Entender el concepto de recursividad

Conocer los fundamentos del diseno de algoritmosrecursivos

Comprender la ejecucion de algoritmos recursivos

Aprender a realizar trazas de algoritmos recursi-vos

Comprender las ventajas e inconvenientes de larecursividad

Recursividad 2

31 Concepto de Recursividad

La recursividad constituye una de las herramien-tas mas potentes en programacion Es un concepto

matematico conocido Por ejemplo

Definicion recursiva

n =

1 si n = 0n middot (n minus 1) si n gt 0

Demostracion por induccion demostrar para uncaso base y despues para un tamano n conside-rando que esta demostrado para valores menoresque n

1048573

1114109

917501Una funcion que se llama a sı misma se

denomina recursiva

Podemos usar recursividad si la solucion de unproblema esta expresada en funcion de si mismaaunque de menor tamano y conocemos la solucionno-recursiva para un determinado caso

Recursividad 3



Ventajas No es necesario definir la secuencia de

pasos exacta para resolver el problema

Desventajas Podrıa ser menos eficiente

Para que una definicion recursiva este completa-mente identificada es necesario tener un caso base

que no se calcule utilizando casos anteriores y que ladivision del problema converja a ese caso base

0 = 1

Ejemplo

xn =

1 si n = 0x middot xnminus1 si n gt 0

Recursividad 4

Ejemplo Calculo del factorial con n=3

3 = 3 2 3 = 3 2

2 = 2 1

(1) (2)

3 = 3 2

2 = 2 1

1 = 1 0

3 = 3 2

2 = 2 1

1 = 1 0

0 = 1(caso base)

(3) (4)

3 = 3 2

2 = 2 1

1 = 1 1

1

3 = 3 2

2 = 2 1

1 = 1 1 = 1

(5) (6)

3 = 3 2

2 = 2 1 = 2

3 = 3 2 = 6

(7) (8)

Recursividad 5



32 Diseno de algoritmos recursivos

Para resolver un problema el primer paso sera laidentificacion de un algoritmo recursivo es decir

descomponer el problema de forma que su solucionquede definida en funcion de ella misma pero paraun tamano menor y la tarea a realizar para un casosimple

Tendremos que disenar casos base casos gene-rales y la solucion en terminos de ellos

Casos base Son los casos del problema que seresuelve con un segmento de codigo sin recursivi-dad

Siempre debe existir al menos un caso base

El numero y forma de los casos base son hastacierto punto arbitrarios La solucion sera mejorcuanto mas simple y eficiente resulte el conjuntode casos seleccionados

Recursividad 6

Casos generales Si el problema es suficientemente

complejo la solucion se expresa de forma recur-siva como la union de

1 La solucion de uno o mas subproblemas (deigual naturaleza pero menor tamano)

2 Un conjunto de pasos adicionales Estos pasos junto con las soluciones a los subproblemascomponen la solucion al problema general quequeremos resolver

Los casos generales siempre deben avanzarhacia un caso base Es decir la llamadarecursiva se hace a un subproblema maspequeno y en ultima instancia los casosgenerales alcanzaran un caso base

Recursividad 7



Ejemplo

Solucion no estructurada

int factorial (int n)

if (n==0) Caso base

return 1

else Caso general

return nfactorial(n-1)

Solucion estructurada


int resultado

if (n==0) Caso base

resultado = 1else Caso general

resultado = nfactorial(n-1)

return resultado

Recursividad 8

33 Ejecucion de un modulo recursivoEn general en la pila se almacena el entorno aso-

ciado a las distintas funciones que se van activando

En particular en un modulo recursivo cada lla-mada recursiva genera una nueva zona de memoria

en la pila independiente del resto de llamadas

Ejemplo Ejecucion del factorial con n=3

1 Dentro de factorial cada llamadareturn nfactorial(n-1)

genera una nueva zona de memoria en la pila

siendo n-1 el correspondiente parametro actualpara esta zona de memoria y queda pendientela evaluacion de la expresion y la ejecucion delreturn

2 El proceso anterior se repite hasta que la condicion

del caso base se hace ciertaSe ejecuta la sentencia return 1

Empieza la vuelta atras de la recursion seevaluan las expresiones y se ejecutan los return

que estaban pendientes

Recursividad 9



Llamada x = factorial(3)

factorial

n = 3

x=factorial(3) x=factorial(3)

factorial

n = 3

factorial

n = 2

(1) (2)

x=factorial(3)

factorial

n = 3

factorial

n = 1

factorial

n = 2

factorial

n = 1

x=factorial(3)

factorial

n = 3

factorial

n = 2

factorial

n = 0

(3) (4)

Recursividad 10

factorial

n = 1

x=factorial(3)

factorial

n = 3

factorial

n = 2

1

x=factorial(3)

factorial

n = 3

factorial

n = 2

1

(5) (6)

x=factorial 3

factorial

n = 3

2

x=factorial 3 6

(7) (8)

Recursividad 11



34 Traza de algoritmos recursivos

Se representan en cascada cada una de las lla-madas al modulo recursivo ası como sus respectivaszonas de memoria y los valores que devuelven

Llamada factorial(3)

n 2

n 3

factorial(3)

n

factorial(1)

1

factorial(2)

Tiempo

devuelve 1factorial(0) =

devuelve

3factorial(2) =devuelve

n

factorial(0)

0

devuelve 1

1

6

2factorial(1) = 2

Recursividad 12

Ejemplo Averigua que hace este algoritmo

int Recursivo (int V int i1 int i2)

int aux1 aux2

if (i1==i2) Caso base

return V[i1]

else Caso general

aux1 = Recursivo(V i1 (i1+i2)2)

aux2 = Recursivo(V ((i1+i2)2)+1 i2)

if (aux1gtaux2)

return aux1

else

return aux2

Recursividad 13



llamada Recursivo(V03) con V es [3701]

0

1

2

3

9

Recursivo(v03)

i1=0i2=(0+3)2=1

Recursivo(v01)

3

i1=0i2=(0+1)2=0

0 1

aux1

1 1

7

i1=((0+1)2)+1=1i2=1

devuelve Recursivo (v 0 1) =

Recursivo(v00)

0

devuelve

0

3

Recursivo(v11)

v

3

7

0

1

(i1=i2)

(i1=i2)

(i1=i2)

(i1=i2)

3

devuelve

aux2 7

7

aux1 7

0i1 i2

i2 i1v

v

v i1 i2

i2 i1v

Recursividad 14

devuelve

i1=((0+3)2)+1=2i2=3

Recursivo(v23)

2 3

i1=2i2=(2+3)2=2

devuelve

Recursivo(v22)

2 2

0

i1=((2+3)2)+1=3i2=3

Recursivo(v33)

3 3

1



(i1=i2)

(i1=i2)

0

1

2

3

9

v

aux1 0

aux2 1

aux2

1

1

7

3

7

0

1

(i1=i2)

i1 i2 v

v i1 i2

i2 i1v

Recursividad 15



35 Ejemplos de funciones recursivas

1 Calculo de la potencia

xn =


int potencia(int base int expo)

if (expo==0)

return 1

else

return base potencia(baseexpo-1)

2 La suma de forma recursiva

suma(a b) =

a si b = 01 + suma(a b minus 1) si b gt 0

int suma(int a int b)

if (b==0)return a

else

return 1+suma(ab-1)

Recursividad 16

3 El producto de forma recursiva

producto(a b) =

0 si b = 0

a + producto(a b minus 1) si b gt 0

int producto(int a int b)

if (b==0)

return 0

elsereturn a+producto(ab-1)

4 Suma recursiva de los elementos de un vector

sumaV (V n) = V [0] si n = 0

V [n] + sumaV (V n minus 1) si n gt 0

int SumaV (int V int n)

if (n==0)

return V[0]

else

return V[n]+sumaV(Vn-1)

Recursividad 17



5 Buscar el maximo de un vector (I)

Mayor1(V n) =

V [0] si n = 0

V [n] o Mayor1(V n minus 1) si n gt 0

int Mayor1 (int V int n)int aux

if (n==0)

return V[0]

else

aux = Mayor1 (V n-1)if (V[n]gt aux)

return V[n]

else

return aux

Recursividad 18

6 Buscar el maximo entre dos posiciones de un

vector

Mayor2(V i d) =

=

V [i] si i = d

Mayor2(Vi (i + d)2 o

Mayor2(V ((i + d)2) + 1 d) si i lt d

int Mayor2 (int V int izq int der)

int m_izq m_der

if (izq==der)

return V[izq]

else

m_izq = Mayor2(V izq (izq+der)2)

m_der = Mayor2(V ((izq+der)2)+1 der)

if (m_izqgt m_der)

return m_izqelse

return m_der

Recursividad 19



7 Busqueda lineal recursiva (con dos casos base)

BusquedaLineal(V n b) =

=

Verdad si V [n] = b

Falso si V [0] = b

(V [n] == b) o

(b isin V [0] V [n minus 1]) en otro caso

int BusquedaLineal(int V int n int b)

if (nlt0)

return 0

else

if (V[n]==b)return 1

else

return BusquedaLineal(Vn-1b)

Recursividad 20

Ejemplo Llamada BusquedaLineal(notas 4 5)

notas

0

1

2

3

9

bl (v35)

bl (v25)

v n b 3

devuelve 1

devuelve 1

devuelve 1

bl (v45)

4

v n b 3

n=0 y v[nminus1]=b

n=0 y v[nminus1]=b

n=0 pero v[nminus1]=b

6

5

7

4

b n v 5

5

5

Recursividad 21




v n 2

v n 0

v n 1

notas

6

5

7

4

0

1

2

3

9

v n 4 b

v n b 3

bl (v48)

bl (v38)

bl (v28)

bl (v18)

bl (v08)

n=0

n=0 y v[nminus1]=b

n=0 y v[nminus1]=b

n=0 y v[nminus1]=b

n=0 y v[nminus1]=b

b

b

b

8

8

8

8

8

devuelve 0

devuelve 0

devuelve 0

devuelve 0

devuelve 0

Recursividad 22

36 Ejemplos mas complejos

361 Busqueda binaria recursiva

Motivacion La busqueda entre dos posiciones deun vector ordenado se puede realizar comparandoel valor buscado con el elemento central

bull Si es igual la busqueda termina con exitobull Si es menor la busqueda debe continuar en el

subvector izquierdobull Si es mayor la busqueda debe continuar en el

subvector derecho

Cabecera de una funcion de busqueda

int BUSCA (int v[] int i int d int x)

Devuelve la posicion en v donde se encuentra xLa busqueda se realiza entre las posiciones i y dSi x no esta en el vector la funcion devuelve -1

Recursividad 23



Lıneas basicas (BUSCA (v t+1 d x))

1 Seleccionar una casilla cualquiera t entre lascasillas i y j (i le t le j) Sea c = v[t] Pet = (i + j)2

2 Comparar c con xa) Si c = x el elemento buscado esta en la

posicion t (Exito)b ) Si c lt x el elemento buscado de-

be estar en una posicion mayor que tBUSCA (v t+1 d x)

c ) Si c gt x el elemento buscado de-be estar en una posicion menor que t

BUSCA (v i t-1 x)

d ) Al modificar los extremos puede darse el casode que i gt d =rArr terminar (Fracaso)

Recursividad 24

int BBR (int v[] int i int d int x)

int centro

if (ilt=d)

centro = (i+d)2

if (v[centro]==x) Caso base 1

return centro

else

if (v[centro]gtx) Buscar izda

return BBR (vicentro-1x)

else Buscar dcha

return BBR (vcentro+1dx)

else i gt d

return -1 Caso base 2

Recursividad 25



Ejemplo Busqueda con exito

Recursividad 26

Ejemplo Busqueda con fracaso

Recursividad 27



Si queremos utilizar la solucion recursiva anterior

para buscar sobre un vector completo solo tendremosque hacer lo siguiente

int busqueda_binaria (int v[] int n int x)

return BBR(v 0 n-1 x)

Recursividad 28

362 Paso de parametros

Paso por valorcada ejecucion trabaja con unacopia

Paso por referencia existe una misma variablepara ese parametro formal eso quiere decir que sesi cambia en una llamada queda cambiado paratodas

Recursividad 29



string invertir(string cad)

if (cadlength()lt=1)

return cad

else

return cad[cadlength()-1] + invertir(cadsubstr(1cadlength()-2)) +cad[0]

void invertir2(string cad string ampres)


res = cad

else

string aux auxcad

Todos menos primer y ultimo car

auxcad = cadsubstr(1cadlength()-2)

invertir2(auxcad aux)

res = cad[cadlength()-1] + aux +cad[0]

Recursividad 30

363 Ordenacion rapida

Lıneas basicas

1 Se toma un elemento arbitrario del vector al

que denominaremos pivote Sea p su valor2 Se recorre el vector de izquierda a derecha

hasta encontrar un elemento situado en unaposicion i tal que v[i] gt p

3 Se recorre el vector de derecha a izquierdahasta encontrar otro elemento situado en una

posicion j tal que v[ j] lt p4 Una vez localizados se intercambian los ele-

mentos situados en las casillas i y j (ahorav[i] lt p lt v[ j])

5 Repetir hasta que los dos procesos de recorridose encuentren

6 Si ahora colocamos el pivote en el sitio que lecorresponde el vector esta particionado en doszonas delimitadas por el pivote

Recursividad 31



Ejemplo

Recursividad 32

Funcion de particion

int partir (int v int primero int ultimo)

void OR (int v int izda int dcha)

int pos_pivote Pos del pivote tras particion

if (izda lt dcha)

Particionar v

pos_pivote = partir (v izda dcha)

Ordenar la primera mitad

OR (v izda pos_pivote-1)

Ordenar la segunda mitad

OR (v pos_pivote+1 dcha)


void intercambia_int (int ampa int ampb)

int izda dcha Indices para recorrer v

int val_pivote Valor del pivote

El pivote es el primer elemento

val_pivote = v[primero]

Recursividad 33



izda = primero + 1 izda va a la dchadcha = ultimo dcha va a la izda

do Buscar e intercambiar elementos

Buscar un elemento mayor que el pivote

avanzando desde la izquierda

while ((izdalt=dcha) ampamp (v[izda]lt=val_pivote))

izda++

Buscar un elemento menor o igual que el pivote

avanzando desde la derecha

while ((izdalt=dcha) ampamp (v[dcha]gtval_pivote))

dcha--

if (izda lt dcha) Intercambiar

intercambia_int (v[izda] v[dcha])

dcha--

izda++

while (izda lt= dcha) Terminar cuando se

cruzan izda y dcha

Colocar el pivote en su sitio correctointercambia_int (v[primero] v[dcha])

return dcha Devolver la pos del pivote

Recursividad 34

Ejemplo

Recursividad 35



Recursividad 36

37 iquestRecursividad o iteracion

Cuestiones a tener en cuenta

1 La carga computacional (tiempo-espacio) aso-ciada a una llamada a una funcion y el retornoa la funcion que hace la llamada

2 Algunas soluciones recursivas pueden hacer quela solucion para un determinado tamano del

problema se calcule varias veces3 Muchos problemas recursivos tienen como caso

base la resolucion del problema para un tamanomuy reducido En ocasiones resulta excesiva-

mente pequeno

4 La solucion iterativa (igual de eficiente) puedeser muy compleja de encontrar

5 La solucion recursiva es muy concisa legible yelegante

Recursividad 37



371 Sucesion de Fibonacci

F ib(0) = F ib(1) = 1F ib(n) = F ib(n minus 1) + F ib(n minus 2)

int fibonacci (int n)

if (n == 0 || n == 1) return 1

else return fibonacci(n-1) + fibonacci(n-2)

int fibonacci_nr (int n)

int ant1 = 1 ant2 = 1 anterior y anteanterior

int actual valor actual

if (n == 0 || n == 1) actual = 1

else

for (i=2 ilt=n i++)

actual = ant1 + ant2 suma los anteriores

ant2 = ant1 actualiza ant2

ant1 = actual y ant1

return actual

Recursividad 38

Ejemplo Calculo de fibonacci (5)

Recursividad 39



372 Busqueda binaria recursiva (2)

int BLineal (int v[] int i int d int x)

bool pequenio_BBR (int)

int BBR2 (int v[] int i int d int x)

if (pequenio_BBR (d-i+1)) usar un

return BLineal (vidx) algoritmo simple

else

int centro = (i+d)2

if (v[centro]==x) Exito

return centroelse Seguir buscando



else Buscar dcha


Recursividad 40


return n lt= BBR_UMBRAL


bool encontrado=false

for (int p=i (iltd) ampamp encontrado i++)

if (v[i] == x) encontrado = true

if (encontrado)

return 1

return -1

Notas

1 El caso base 2 (Fracaso) de la funcion BBR()

ya no es necesario porque no se debe dar el

caso de que i gt d2 Es obligatorio que la funcion que resuelve el pro-blema para un tamano pequeno (BLineal())devuelva un valor coherente con el que devuelveBBR2()

Recursividad 41



373 Ordenacion rapida (2)

void seleccion (int v int izda int dcha)


int pequenio_OR (int n)

void OR2 (int v int izda int dcha)

if (pequenio_OR (dcha-izda+1)) usar un

seleccion (v izda dcha) algoritmo simple

else

if (izda lt dcha)

int pos_pivote Pos pivote tras partir

Particionar v



OR2 (v izda pos_pivote-1)


OR2 (v pos_pivote+1 dcha)

Recursividad 42

bool pequenio_OR (int)

return n lt= OR_UMBRAL


int i j pos_menor

int menor

for (i = izda i lt dcha i++)

pos_menor = i

menor = v[i]

for (j = i+1 j lt= dcha j++)

if (v[j] lt menor)

pos_menor = j

menor = v[j]

v[pos_menor] = v[i]

v[i] = menor

Recursividad 43



Ejemplo OR2 (v 0 299) y OR_UMBRAL=100

Recursividad 44 Recursividad 45



374 Torres de Hanoi

include ltiostreamgt

using namespace std

int main (void)

void hanoi (int n int inic int tmp int final)

int n Numero de discos a mover

cout ltlt Numero de discos

cin gtgt n

hanoi (n 1 2 3) mover n discos del 1 al 3

usando el 2 como temporal

return 0

Recursividad 46


if (n gt 0)

Mover n-1 discos de inic a tmp

El temporal es final

hanoi (n-1 inic final tmp)

Mover el que queda en inica final

cout ltltDel poste ltltinicltlt al ltltfinalltltn

Mover n-1 discos de tmp a final

El temporal es inic

hanoi (n-1 tmp inic final)

hanoi

Numero de discos 3

Del poste 1 al 3

Del poste 1 al 2

Del poste 3 al 2

Del poste 1 al 3Del poste 2 al 1

Del poste 2 al 3

Del poste 1 al 3

Recursividad 47



Recursividad 48



Ventajas No es necesario definir la secuencia de

pasos exacta para resolver el problema

Desventajas Podrıa ser menos eficiente

Para que una definicion recursiva este completa-mente identificada es necesario tener un caso base

que no se calcule utilizando casos anteriores y que ladivision del problema converja a ese caso base

0 = 1

Ejemplo

xn =


Recursividad 4

Ejemplo Calculo del factorial con n=3

3 = 3 2 3 = 3 2

2 = 2 1

(1) (2)

3 = 3 2

2 = 2 1

1 = 1 0

3 = 3 2

2 = 2 1

1 = 1 0

0 = 1(caso base)

(3) (4)

3 = 3 2

2 = 2 1

1 = 1 1

1

3 = 3 2

2 = 2 1

1 = 1 1 = 1

(5) (6)

3 = 3 2

2 = 2 1 = 2

3 = 3 2 = 6

(7) (8)

Recursividad 5










Recursividad 6






Recursividad 7



Ejemplo



if (n==0) Caso base

return 1

else Caso general




int resultado

if (n==0) Caso base



return resultado

Recursividad 8













Recursividad 9




factorial

n = 3


factorial

n = 3

factorial

n = 2

(1) (2)

x=factorial(3)

factorial

n = 3

factorial

n = 1

factorial

n = 2

factorial

n = 1

x=factorial(3)

factorial

n = 3

factorial

n = 2

factorial

n = 0

(3) (4)

Recursividad 10

factorial

n = 1

x=factorial(3)

factorial

n = 3

factorial

n = 2

1

x=factorial(3)

factorial

n = 3

factorial

n = 2

1

(5) (6)

x=factorial 3

factorial

n = 3

2

x=factorial 3 6

(7) (8)

Recursividad 11






n 2

n 3

factorial(3)

n

factorial(1)

1

factorial(2)

Tiempo


devuelve


n

factorial(0)

0

devuelve 1

1

6

2factorial(1) = 2

Recursividad 12



int aux1 aux2


return V[i1]

else Caso general



if (aux1gtaux2)

return aux1

else

return aux2

Recursividad 13




0

1

2

3

9

Recursivo(v03)

i1=0i2=(0+3)2=1

Recursivo(v01)

3

i1=0i2=(0+1)2=0

0 1

aux1

1 1

7

i1=((0+1)2)+1=1i2=1


Recursivo(v00)

0

devuelve

0

3

Recursivo(v11)

v

3

7

0

1

(i1=i2)

(i1=i2)

(i1=i2)

(i1=i2)

3

devuelve

aux2 7

7

aux1 7

0i1 i2

i2 i1v

v

v i1 i2

i2 i1v

Recursividad 14

devuelve

i1=((0+3)2)+1=2i2=3

Recursivo(v23)

2 3

i1=2i2=(2+3)2=2

devuelve

Recursivo(v22)

2 2

0

i1=((2+3)2)+1=3i2=3

Recursivo(v33)

3 3

1



(i1=i2)

(i1=i2)

0

1

2

3

9

v

aux1 0

aux2 1

aux2

1

1

7

3

7

0

1

(i1=i2)

i1 i2 v

v i1 i2

i2 i1v

Recursividad 15





xn =



if (expo==0)

return 1

else



suma(a b) =



if (b==0)return a

else

return 1+suma(ab-1)

Recursividad 16


producto(a b) =

0 si b = 0



if (b==0)

return 0



sumaV (V n) = V [0] si n = 0



if (n==0)

return V[0]

else


Recursividad 17




Mayor1(V n) =

V [0] si n = 0



if (n==0)

return V[0]

else


return V[n]

else

return aux

Recursividad 18


vector

Mayor2(V i d) =

=

V [i] si i = d




int m_izq m_der

if (izq==der)

return V[izq]

else



if (m_izqgt m_der)

return m_izqelse

return m_der

Recursividad 19





=

Verdad si V [n] = b

Falso si V [0] = b

(V [n] == b) o



if (nlt0)

return 0

else


else


Recursividad 20


notas

0

1

2

3

9

bl (v35)

bl (v25)

v n b 3

devuelve 1

devuelve 1

devuelve 1

bl (v45)

4

v n b 3

n=0 y v[nminus1]=b

n=0 y v[nminus1]=b


6

5

7

4

b n v 5

5

5

Recursividad 21




v n 2

v n 0

v n 1

notas

6

5

7

4

0

1

2

3

9

v n 4 b

v n b 3

bl (v48)

bl (v38)

bl (v28)

bl (v18)

bl (v08)

n=0

n=0 y v[nminus1]=b

n=0 y v[nminus1]=b

n=0 y v[nminus1]=b

n=0 y v[nminus1]=b

b

b

b

8

8

8

8

8

devuelve 0

devuelve 0

devuelve 0

devuelve 0

devuelve 0

Recursividad 22






subvector derecho




Recursividad 23









BUSCA (v i t-1 x)


Recursividad 24


int centro

if (ilt=d)

centro = (i+d)2


return centro

else



else Buscar dcha


else i gt d


Recursividad 25




Recursividad 26


Recursividad 27







Recursividad 28




Recursividad 29





return cad

else




res = cad

else

string aux auxcad





Recursividad 30


Lıneas basicas









Recursividad 31



Ejemplo

Recursividad 32





if (izda lt dcha)

Particionar v












Recursividad 33








izda++




dcha--



dcha--

izda++


cruzan izda y dcha



Recursividad 34

Ejemplo

Recursividad 35



Recursividad 36







mente pequeno



Recursividad 37






if (n == 0 || n == 1) return 1





if (n == 0 || n == 1) actual = 1

else

for (i=2 ilt=n i++)




return actual

Recursividad 38


Recursividad 39









else

int centro = (i+d)2





else Buscar dcha


Recursividad 40







if (encontrado)

return 1

return -1

Notas




Recursividad 41










else

if (izda lt dcha)


Particionar v






Recursividad 42




int i j pos_menor

int menor


pos_menor = i

menor = v[i]


if (v[j] lt menor)

pos_menor = j

menor = v[j]

v[pos_menor] = v[i]

v[i] = menor

Recursividad 43







374 Torres de Hanoi


using namespace std

int main (void)




cin gtgt n



return 0

Recursividad 46


if (n gt 0)







El temporal es inic


hanoi

Numero de discos 3

Del poste 1 al 3

Del poste 1 al 2

Del poste 3 al 2


Del poste 2 al 3

Del poste 1 al 3

Recursividad 47



Recursividad 48










Recursividad 6






Recursividad 7



Ejemplo



if (n==0) Caso base

return 1

else Caso general




int resultado

if (n==0) Caso base



return resultado

Recursividad 8













Recursividad 9




factorial

n = 3


factorial

n = 3

factorial

n = 2

(1) (2)

x=factorial(3)

factorial

n = 3

factorial

n = 1

factorial

n = 2

factorial

n = 1

x=factorial(3)

factorial

n = 3

factorial

n = 2

factorial

n = 0

(3) (4)

Recursividad 10

factorial

n = 1

x=factorial(3)

factorial

n = 3

factorial

n = 2

1

x=factorial(3)

factorial

n = 3

factorial

n = 2

1

(5) (6)

x=factorial 3

factorial

n = 3

2

x=factorial 3 6

(7) (8)

Recursividad 11






n 2

n 3

factorial(3)

n

factorial(1)

1

factorial(2)

Tiempo


devuelve


n

factorial(0)

0

devuelve 1

1

6

2factorial(1) = 2

Recursividad 12



int aux1 aux2


return V[i1]

else Caso general



if (aux1gtaux2)

return aux1

else

return aux2

Recursividad 13




0

1

2

3

9

Recursivo(v03)

i1=0i2=(0+3)2=1

Recursivo(v01)

3

i1=0i2=(0+1)2=0

0 1

aux1

1 1

7

i1=((0+1)2)+1=1i2=1


Recursivo(v00)

0

devuelve

0

3

Recursivo(v11)

v

3

7

0

1

(i1=i2)

(i1=i2)

(i1=i2)

(i1=i2)

3

devuelve

aux2 7

7

aux1 7

0i1 i2

i2 i1v

v

v i1 i2

i2 i1v

Recursividad 14

devuelve

i1=((0+3)2)+1=2i2=3

Recursivo(v23)

2 3

i1=2i2=(2+3)2=2

devuelve

Recursivo(v22)

2 2

0

i1=((2+3)2)+1=3i2=3

Recursivo(v33)

3 3

1



(i1=i2)

(i1=i2)

0

1

2

3

9

v

aux1 0

aux2 1

aux2

1

1

7

3

7

0

1

(i1=i2)

i1 i2 v

v i1 i2

i2 i1v

Recursividad 15





xn =



if (expo==0)

return 1

else



suma(a b) =



if (b==0)return a

else

return 1+suma(ab-1)

Recursividad 16


producto(a b) =

0 si b = 0



if (b==0)

return 0



sumaV (V n) = V [0] si n = 0



if (n==0)

return V[0]

else


Recursividad 17




Mayor1(V n) =

V [0] si n = 0



if (n==0)

return V[0]

else


return V[n]

else

return aux

Recursividad 18


vector

Mayor2(V i d) =

=

V [i] si i = d




int m_izq m_der

if (izq==der)

return V[izq]

else



if (m_izqgt m_der)

return m_izqelse

return m_der

Recursividad 19





=

Verdad si V [n] = b

Falso si V [0] = b

(V [n] == b) o



if (nlt0)

return 0

else


else


Recursividad 20


notas

0

1

2

3

9

bl (v35)

bl (v25)

v n b 3

devuelve 1

devuelve 1

devuelve 1

bl (v45)

4

v n b 3

n=0 y v[nminus1]=b

n=0 y v[nminus1]=b


6

5

7

4

b n v 5

5

5

Recursividad 21




v n 2

v n 0

v n 1

notas

6

5

7

4

0

1

2

3

9

v n 4 b

v n b 3

bl (v48)

bl (v38)

bl (v28)

bl (v18)

bl (v08)

n=0

n=0 y v[nminus1]=b

n=0 y v[nminus1]=b

n=0 y v[nminus1]=b

n=0 y v[nminus1]=b

b

b

b

8

8

8

8

8

devuelve 0

devuelve 0

devuelve 0

devuelve 0

devuelve 0

Recursividad 22






subvector derecho




Recursividad 23









BUSCA (v i t-1 x)


Recursividad 24


int centro

if (ilt=d)

centro = (i+d)2


return centro

else



else Buscar dcha


else i gt d


Recursividad 25




Recursividad 26


Recursividad 27







Recursividad 28




Recursividad 29





return cad

else




res = cad

else

string aux auxcad





Recursividad 30


Lıneas basicas









Recursividad 31



Ejemplo

Recursividad 32





if (izda lt dcha)

Particionar v












Recursividad 33








izda++




dcha--



dcha--

izda++


cruzan izda y dcha



Recursividad 34

Ejemplo

Recursividad 35



Recursividad 36







mente pequeno



Recursividad 37






if (n == 0 || n == 1) return 1





if (n == 0 || n == 1) actual = 1

else

for (i=2 ilt=n i++)




return actual

Recursividad 38


Recursividad 39









else

int centro = (i+d)2





else Buscar dcha


Recursividad 40







if (encontrado)

return 1

return -1

Notas




Recursividad 41










else

if (izda lt dcha)


Particionar v






Recursividad 42




int i j pos_menor

int menor


pos_menor = i

menor = v[i]


if (v[j] lt menor)

pos_menor = j

menor = v[j]

v[pos_menor] = v[i]

v[i] = menor

Recursividad 43







374 Torres de Hanoi


using namespace std

int main (void)




cin gtgt n



return 0

Recursividad 46


if (n gt 0)







El temporal es inic


hanoi

Numero de discos 3

Del poste 1 al 3

Del poste 1 al 2

Del poste 3 al 2


Del poste 2 al 3

Del poste 1 al 3

Recursividad 47



Recursividad 48



Ejemplo



if (n==0) Caso base

return 1

else Caso general




int resultado

if (n==0) Caso base



return resultado

Recursividad 8













Recursividad 9




factorial

n = 3


factorial

n = 3

factorial

n = 2

(1) (2)

x=factorial(3)

factorial

n = 3

factorial

n = 1

factorial

n = 2

factorial

n = 1

x=factorial(3)

factorial

n = 3

factorial

n = 2

factorial

n = 0

(3) (4)

Recursividad 10

factorial

n = 1

x=factorial(3)

factorial

n = 3

factorial

n = 2

1

x=factorial(3)

factorial

n = 3

factorial

n = 2

1

(5) (6)

x=factorial 3

factorial

n = 3

2

x=factorial 3 6

(7) (8)

Recursividad 11






n 2

n 3

factorial(3)

n

factorial(1)

1

factorial(2)

Tiempo


devuelve


n

factorial(0)

0

devuelve 1

1

6

2factorial(1) = 2

Recursividad 12



int aux1 aux2


return V[i1]

else Caso general



if (aux1gtaux2)

return aux1

else

return aux2

Recursividad 13




0

1

2

3

9

Recursivo(v03)

i1=0i2=(0+3)2=1

Recursivo(v01)

3

i1=0i2=(0+1)2=0

0 1

aux1

1 1

7

i1=((0+1)2)+1=1i2=1


Recursivo(v00)

0

devuelve

0

3

Recursivo(v11)

v

3

7

0

1

(i1=i2)

(i1=i2)

(i1=i2)

(i1=i2)

3

devuelve

aux2 7

7

aux1 7

0i1 i2

i2 i1v

v

v i1 i2

i2 i1v

Recursividad 14

devuelve

i1=((0+3)2)+1=2i2=3

Recursivo(v23)

2 3

i1=2i2=(2+3)2=2

devuelve

Recursivo(v22)

2 2

0

i1=((2+3)2)+1=3i2=3

Recursivo(v33)

3 3

1



(i1=i2)

(i1=i2)

0

1

2

3

9

v

aux1 0

aux2 1

aux2

1

1

7

3

7

0

1

(i1=i2)

i1 i2 v

v i1 i2

i2 i1v

Recursividad 15





xn =



if (expo==0)

return 1

else



suma(a b) =



if (b==0)return a

else

return 1+suma(ab-1)

Recursividad 16


producto(a b) =

0 si b = 0



if (b==0)

return 0



sumaV (V n) = V [0] si n = 0



if (n==0)

return V[0]

else


Recursividad 17




Mayor1(V n) =

V [0] si n = 0



if (n==0)

return V[0]

else


return V[n]

else

return aux

Recursividad 18


vector

Mayor2(V i d) =

=

V [i] si i = d




int m_izq m_der

if (izq==der)

return V[izq]

else



if (m_izqgt m_der)

return m_izqelse

return m_der

Recursividad 19





=

Verdad si V [n] = b

Falso si V [0] = b

(V [n] == b) o



if (nlt0)

return 0

else


else


Recursividad 20


notas

0

1

2

3

9

bl (v35)

bl (v25)

v n b 3

devuelve 1

devuelve 1

devuelve 1

bl (v45)

4

v n b 3

n=0 y v[nminus1]=b

n=0 y v[nminus1]=b


6

5

7

4

b n v 5

5

5

Recursividad 21




v n 2

v n 0

v n 1

notas

6

5

7

4

0

1

2

3

9

v n 4 b

v n b 3

bl (v48)

bl (v38)

bl (v28)

bl (v18)

bl (v08)

n=0

n=0 y v[nminus1]=b

n=0 y v[nminus1]=b

n=0 y v[nminus1]=b

n=0 y v[nminus1]=b

b

b

b

8

8

8

8

8

devuelve 0

devuelve 0

devuelve 0

devuelve 0

devuelve 0

Recursividad 22






subvector derecho




Recursividad 23









BUSCA (v i t-1 x)


Recursividad 24


int centro

if (ilt=d)

centro = (i+d)2


return centro

else



else Buscar dcha


else i gt d


Recursividad 25




Recursividad 26


Recursividad 27







Recursividad 28




Recursividad 29





return cad

else




res = cad

else

string aux auxcad





Recursividad 30


Lıneas basicas









Recursividad 31



Ejemplo

Recursividad 32





if (izda lt dcha)

Particionar v












Recursividad 33








izda++




dcha--



dcha--

izda++


cruzan izda y dcha



Recursividad 34

Ejemplo

Recursividad 35



Recursividad 36







mente pequeno



Recursividad 37






if (n == 0 || n == 1) return 1





if (n == 0 || n == 1) actual = 1

else

for (i=2 ilt=n i++)




return actual

Recursividad 38


Recursividad 39









else

int centro = (i+d)2





else Buscar dcha


Recursividad 40







if (encontrado)

return 1

return -1

Notas




Recursividad 41










else

if (izda lt dcha)


Particionar v






Recursividad 42




int i j pos_menor

int menor


pos_menor = i

menor = v[i]


if (v[j] lt menor)

pos_menor = j

menor = v[j]

v[pos_menor] = v[i]

v[i] = menor

Recursividad 43







374 Torres de Hanoi


using namespace std

int main (void)




cin gtgt n



return 0

Recursividad 46


if (n gt 0)







El temporal es inic


hanoi

Numero de discos 3

Del poste 1 al 3

Del poste 1 al 2

Del poste 3 al 2


Del poste 2 al 3

Del poste 1 al 3

Recursividad 47



Recursividad 48




factorial

n = 3


factorial

n = 3

factorial

n = 2

(1) (2)

x=factorial(3)

factorial

n = 3

factorial

n = 1

factorial

n = 2

factorial

n = 1

x=factorial(3)

factorial

n = 3

factorial

n = 2

factorial

n = 0

(3) (4)

Recursividad 10

factorial

n = 1

x=factorial(3)

factorial

n = 3

factorial

n = 2

1

x=factorial(3)

factorial

n = 3

factorial

n = 2

1

(5) (6)

x=factorial 3

factorial

n = 3

2

x=factorial 3 6

(7) (8)

Recursividad 11






n 2

n 3

factorial(3)

n

factorial(1)

1

factorial(2)

Tiempo


devuelve


n

factorial(0)

0

devuelve 1

1

6

2factorial(1) = 2

Recursividad 12



int aux1 aux2


return V[i1]

else Caso general



if (aux1gtaux2)

return aux1

else

return aux2

Recursividad 13




0

1

2

3

9

Recursivo(v03)

i1=0i2=(0+3)2=1

Recursivo(v01)

3

i1=0i2=(0+1)2=0

0 1

aux1

1 1

7

i1=((0+1)2)+1=1i2=1


Recursivo(v00)

0

devuelve

0

3

Recursivo(v11)

v

3

7

0

1

(i1=i2)

(i1=i2)

(i1=i2)

(i1=i2)

3

devuelve

aux2 7

7

aux1 7

0i1 i2

i2 i1v

v

v i1 i2

i2 i1v

Recursividad 14

devuelve

i1=((0+3)2)+1=2i2=3

Recursivo(v23)

2 3

i1=2i2=(2+3)2=2

devuelve

Recursivo(v22)

2 2

0

i1=((2+3)2)+1=3i2=3

Recursivo(v33)

3 3

1



(i1=i2)

(i1=i2)

0

1

2

3

9

v

aux1 0

aux2 1

aux2

1

1

7

3

7

0

1

(i1=i2)

i1 i2 v

v i1 i2

i2 i1v

Recursividad 15





xn =



if (expo==0)

return 1

else



suma(a b) =



if (b==0)return a

else

return 1+suma(ab-1)

Recursividad 16


producto(a b) =

0 si b = 0



if (b==0)

return 0



sumaV (V n) = V [0] si n = 0



if (n==0)

return V[0]

else


Recursividad 17




Mayor1(V n) =

V [0] si n = 0



if (n==0)

return V[0]

else


return V[n]

else

return aux

Recursividad 18


vector

Mayor2(V i d) =

=

V [i] si i = d




int m_izq m_der

if (izq==der)

return V[izq]

else



if (m_izqgt m_der)

return m_izqelse

return m_der

Recursividad 19





=

Verdad si V [n] = b

Falso si V [0] = b

(V [n] == b) o



if (nlt0)

return 0

else


else


Recursividad 20


notas

0

1

2

3

9

bl (v35)

bl (v25)

v n b 3

devuelve 1

devuelve 1

devuelve 1

bl (v45)

4

v n b 3

n=0 y v[nminus1]=b

n=0 y v[nminus1]=b


6

5

7

4

b n v 5

5

5

Recursividad 21




v n 2

v n 0

v n 1

notas

6

5

7

4

0

1

2

3

9

v n 4 b

v n b 3

bl (v48)

bl (v38)

bl (v28)

bl (v18)

bl (v08)

n=0

n=0 y v[nminus1]=b

n=0 y v[nminus1]=b

n=0 y v[nminus1]=b

n=0 y v[nminus1]=b

b

b

b

8

8

8

8

8

devuelve 0

devuelve 0

devuelve 0

devuelve 0

devuelve 0

Recursividad 22






subvector derecho




Recursividad 23









BUSCA (v i t-1 x)


Recursividad 24


int centro

if (ilt=d)

centro = (i+d)2


return centro

else



else Buscar dcha


else i gt d


Recursividad 25




Recursividad 26


Recursividad 27







Recursividad 28




Recursividad 29





return cad

else




res = cad

else

string aux auxcad





Recursividad 30


Lıneas basicas









Recursividad 31



Ejemplo

Recursividad 32





if (izda lt dcha)

Particionar v












Recursividad 33








izda++




dcha--



dcha--

izda++


cruzan izda y dcha



Recursividad 34

Ejemplo

Recursividad 35



Recursividad 36







mente pequeno



Recursividad 37






if (n == 0 || n == 1) return 1





if (n == 0 || n == 1) actual = 1

else

for (i=2 ilt=n i++)




return actual

Recursividad 38


Recursividad 39









else

int centro = (i+d)2





else Buscar dcha


Recursividad 40







if (encontrado)

return 1

return -1

Notas




Recursividad 41










else

if (izda lt dcha)


Particionar v






Recursividad 42




int i j pos_menor

int menor


pos_menor = i

menor = v[i]


if (v[j] lt menor)

pos_menor = j

menor = v[j]

v[pos_menor] = v[i]

v[i] = menor

Recursividad 43







374 Torres de Hanoi


using namespace std

int main (void)




cin gtgt n



return 0

Recursividad 46


if (n gt 0)







El temporal es inic


hanoi

Numero de discos 3

Del poste 1 al 3

Del poste 1 al 2

Del poste 3 al 2


Del poste 2 al 3

Del poste 1 al 3

Recursividad 47



Recursividad 48






n 2

n 3

factorial(3)

n

factorial(1)

1

factorial(2)

Tiempo


devuelve


n

factorial(0)

0

devuelve 1

1

6

2factorial(1) = 2

Recursividad 12



int aux1 aux2


return V[i1]

else Caso general



if (aux1gtaux2)

return aux1

else

return aux2

Recursividad 13




0

1

2

3

9

Recursivo(v03)

i1=0i2=(0+3)2=1

Recursivo(v01)

3

i1=0i2=(0+1)2=0

0 1

aux1

1 1

7

i1=((0+1)2)+1=1i2=1


Recursivo(v00)

0

devuelve

0

3

Recursivo(v11)

v

3

7

0

1

(i1=i2)

(i1=i2)

(i1=i2)

(i1=i2)

3

devuelve

aux2 7

7

aux1 7

0i1 i2

i2 i1v

v

v i1 i2

i2 i1v

Recursividad 14

devuelve

i1=((0+3)2)+1=2i2=3

Recursivo(v23)

2 3

i1=2i2=(2+3)2=2

devuelve

Recursivo(v22)

2 2

0

i1=((2+3)2)+1=3i2=3

Recursivo(v33)

3 3

1



(i1=i2)

(i1=i2)

0

1

2

3

9

v

aux1 0

aux2 1

aux2

1

1

7

3

7

0

1

(i1=i2)

i1 i2 v

v i1 i2

i2 i1v

Recursividad 15





xn =



if (expo==0)

return 1

else



suma(a b) =



if (b==0)return a

else

return 1+suma(ab-1)

Recursividad 16


producto(a b) =

0 si b = 0



if (b==0)

return 0



sumaV (V n) = V [0] si n = 0



if (n==0)

return V[0]

else


Recursividad 17




Mayor1(V n) =

V [0] si n = 0



if (n==0)

return V[0]

else


return V[n]

else

return aux

Recursividad 18


vector

Mayor2(V i d) =

=

V [i] si i = d




int m_izq m_der

if (izq==der)

return V[izq]

else



if (m_izqgt m_der)

return m_izqelse

return m_der

Recursividad 19





=

Verdad si V [n] = b

Falso si V [0] = b

(V [n] == b) o



if (nlt0)

return 0

else


else


Recursividad 20


notas

0

1

2

3

9

bl (v35)

bl (v25)

v n b 3

devuelve 1

devuelve 1

devuelve 1

bl (v45)

4

v n b 3

n=0 y v[nminus1]=b

n=0 y v[nminus1]=b


6

5

7

4

b n v 5

5

5

Recursividad 21




v n 2

v n 0

v n 1

notas

6

5

7

4

0

1

2

3

9

v n 4 b

v n b 3

bl (v48)

bl (v38)

bl (v28)

bl (v18)

bl (v08)

n=0

n=0 y v[nminus1]=b

n=0 y v[nminus1]=b

n=0 y v[nminus1]=b

n=0 y v[nminus1]=b

b

b

b

8

8

8

8

8

devuelve 0

devuelve 0

devuelve 0

devuelve 0

devuelve 0

Recursividad 22






subvector derecho




Recursividad 23









BUSCA (v i t-1 x)


Recursividad 24


int centro

if (ilt=d)

centro = (i+d)2


return centro

else



else Buscar dcha


else i gt d


Recursividad 25




Recursividad 26


Recursividad 27







Recursividad 28




Recursividad 29





return cad

else




res = cad

else

string aux auxcad





Recursividad 30


Lıneas basicas









Recursividad 31



Ejemplo

Recursividad 32





if (izda lt dcha)

Particionar v












Recursividad 33








izda++




dcha--



dcha--

izda++


cruzan izda y dcha



Recursividad 34

Ejemplo

Recursividad 35



Recursividad 36







mente pequeno



Recursividad 37






if (n == 0 || n == 1) return 1





if (n == 0 || n == 1) actual = 1

else

for (i=2 ilt=n i++)




return actual

Recursividad 38


Recursividad 39









else

int centro = (i+d)2





else Buscar dcha


Recursividad 40







if (encontrado)

return 1

return -1

Notas




Recursividad 41










else

if (izda lt dcha)


Particionar v






Recursividad 42




int i j pos_menor

int menor


pos_menor = i

menor = v[i]


if (v[j] lt menor)

pos_menor = j

menor = v[j]

v[pos_menor] = v[i]

v[i] = menor

Recursividad 43







374 Torres de Hanoi


using namespace std

int main (void)




cin gtgt n



return 0

Recursividad 46


if (n gt 0)







El temporal es inic


hanoi

Numero de discos 3

Del poste 1 al 3

Del poste 1 al 2

Del poste 3 al 2


Del poste 2 al 3

Del poste 1 al 3

Recursividad 47



Recursividad 48




0

1

2

3

9

Recursivo(v03)

i1=0i2=(0+3)2=1

Recursivo(v01)

3

i1=0i2=(0+1)2=0

0 1

aux1

1 1

7

i1=((0+1)2)+1=1i2=1


Recursivo(v00)

0

devuelve

0

3

Recursivo(v11)

v

3

7

0

1

(i1=i2)

(i1=i2)

(i1=i2)

(i1=i2)

3

devuelve

aux2 7

7

aux1 7

0i1 i2

i2 i1v

v

v i1 i2

i2 i1v

Recursividad 14

devuelve

i1=((0+3)2)+1=2i2=3

Recursivo(v23)

2 3

i1=2i2=(2+3)2=2

devuelve

Recursivo(v22)

2 2

0

i1=((2+3)2)+1=3i2=3

Recursivo(v33)

3 3

1



(i1=i2)

(i1=i2)

0

1

2

3

9

v

aux1 0

aux2 1

aux2

1

1

7

3

7

0

1

(i1=i2)

i1 i2 v

v i1 i2

i2 i1v

Recursividad 15





xn =



if (expo==0)

return 1

else



suma(a b) =



if (b==0)return a

else

return 1+suma(ab-1)

Recursividad 16


producto(a b) =

0 si b = 0



if (b==0)

return 0



sumaV (V n) = V [0] si n = 0



if (n==0)

return V[0]

else


Recursividad 17




Mayor1(V n) =

V [0] si n = 0



if (n==0)

return V[0]

else


return V[n]

else

return aux

Recursividad 18


vector

Mayor2(V i d) =

=

V [i] si i = d




int m_izq m_der

if (izq==der)

return V[izq]

else



if (m_izqgt m_der)

return m_izqelse

return m_der

Recursividad 19





=

Verdad si V [n] = b

Falso si V [0] = b

(V [n] == b) o



if (nlt0)

return 0

else


else


Recursividad 20


notas

0

1

2

3

9

bl (v35)

bl (v25)

v n b 3

devuelve 1

devuelve 1

devuelve 1

bl (v45)

4

v n b 3

n=0 y v[nminus1]=b

n=0 y v[nminus1]=b


6

5

7

4

b n v 5

5

5

Recursividad 21




v n 2

v n 0

v n 1

notas

6

5

7

4

0

1

2

3

9

v n 4 b

v n b 3

bl (v48)

bl (v38)

bl (v28)

bl (v18)

bl (v08)

n=0

n=0 y v[nminus1]=b

n=0 y v[nminus1]=b

n=0 y v[nminus1]=b

n=0 y v[nminus1]=b

b

b

b

8

8

8

8

8

devuelve 0

devuelve 0

devuelve 0

devuelve 0

devuelve 0

Recursividad 22






subvector derecho




Recursividad 23









BUSCA (v i t-1 x)


Recursividad 24


int centro

if (ilt=d)

centro = (i+d)2


return centro

else



else Buscar dcha


else i gt d


Recursividad 25




Recursividad 26


Recursividad 27







Recursividad 28




Recursividad 29





return cad

else




res = cad

else

string aux auxcad





Recursividad 30


Lıneas basicas









Recursividad 31



Ejemplo

Recursividad 32





if (izda lt dcha)

Particionar v












Recursividad 33








izda++




dcha--



dcha--

izda++


cruzan izda y dcha



Recursividad 34

Ejemplo

Recursividad 35



Recursividad 36







mente pequeno



Recursividad 37






if (n == 0 || n == 1) return 1





if (n == 0 || n == 1) actual = 1

else

for (i=2 ilt=n i++)




return actual

Recursividad 38


Recursividad 39









else

int centro = (i+d)2





else Buscar dcha


Recursividad 40







if (encontrado)

return 1

return -1

Notas




Recursividad 41










else

if (izda lt dcha)


Particionar v






Recursividad 42




int i j pos_menor

int menor


pos_menor = i

menor = v[i]


if (v[j] lt menor)

pos_menor = j

menor = v[j]

v[pos_menor] = v[i]

v[i] = menor

Recursividad 43







374 Torres de Hanoi


using namespace std

int main (void)




cin gtgt n



return 0

Recursividad 46


if (n gt 0)







El temporal es inic


hanoi

Numero de discos 3

Del poste 1 al 3

Del poste 1 al 2

Del poste 3 al 2


Del poste 2 al 3

Del poste 1 al 3

Recursividad 47



Recursividad 48





xn =



if (expo==0)

return 1

else



suma(a b) =



if (b==0)return a

else

return 1+suma(ab-1)

Recursividad 16


producto(a b) =

0 si b = 0



if (b==0)

return 0



sumaV (V n) = V [0] si n = 0



if (n==0)

return V[0]

else


Recursividad 17




Mayor1(V n) =

V [0] si n = 0



if (n==0)

return V[0]

else


return V[n]

else

return aux

Recursividad 18


vector

Mayor2(V i d) =

=

V [i] si i = d




int m_izq m_der

if (izq==der)

return V[izq]

else



if (m_izqgt m_der)

return m_izqelse

return m_der

Recursividad 19





=

Verdad si V [n] = b

Falso si V [0] = b

(V [n] == b) o



if (nlt0)

return 0

else


else


Recursividad 20


notas

0

1

2

3

9

bl (v35)

bl (v25)

v n b 3

devuelve 1

devuelve 1

devuelve 1

bl (v45)

4

v n b 3

n=0 y v[nminus1]=b

n=0 y v[nminus1]=b


6

5

7

4

b n v 5

5

5

Recursividad 21




v n 2

v n 0

v n 1

notas

6

5

7

4

0

1

2

3

9

v n 4 b

v n b 3

bl (v48)

bl (v38)

bl (v28)

bl (v18)

bl (v08)

n=0

n=0 y v[nminus1]=b

n=0 y v[nminus1]=b

n=0 y v[nminus1]=b

n=0 y v[nminus1]=b

b

b

b

8

8

8

8

8

devuelve 0

devuelve 0

devuelve 0

devuelve 0

devuelve 0

Recursividad 22






subvector derecho




Recursividad 23









BUSCA (v i t-1 x)


Recursividad 24


int centro

if (ilt=d)

centro = (i+d)2


return centro

else



else Buscar dcha


else i gt d


Recursividad 25




Recursividad 26


Recursividad 27







Recursividad 28




Recursividad 29





return cad

else




res = cad

else

string aux auxcad





Recursividad 30


Lıneas basicas









Recursividad 31



Ejemplo

Recursividad 32





if (izda lt dcha)

Particionar v












Recursividad 33








izda++




dcha--



dcha--

izda++


cruzan izda y dcha



Recursividad 34

Ejemplo

Recursividad 35



Recursividad 36







mente pequeno



Recursividad 37






if (n == 0 || n == 1) return 1





if (n == 0 || n == 1) actual = 1

else

for (i=2 ilt=n i++)




return actual

Recursividad 38


Recursividad 39









else

int centro = (i+d)2





else Buscar dcha


Recursividad 40







if (encontrado)

return 1

return -1

Notas




Recursividad 41










else

if (izda lt dcha)


Particionar v






Recursividad 42




int i j pos_menor

int menor


pos_menor = i

menor = v[i]


if (v[j] lt menor)

pos_menor = j

menor = v[j]

v[pos_menor] = v[i]

v[i] = menor

Recursividad 43







374 Torres de Hanoi


using namespace std

int main (void)




cin gtgt n



return 0

Recursividad 46


if (n gt 0)







El temporal es inic


hanoi

Numero de discos 3

Del poste 1 al 3

Del poste 1 al 2

Del poste 3 al 2


Del poste 2 al 3

Del poste 1 al 3

Recursividad 47



Recursividad 48




Mayor1(V n) =

V [0] si n = 0



if (n==0)

return V[0]

else


return V[n]

else

return aux

Recursividad 18


vector

Mayor2(V i d) =

=

V [i] si i = d




int m_izq m_der

if (izq==der)

return V[izq]

else



if (m_izqgt m_der)

return m_izqelse

return m_der

Recursividad 19





=

Verdad si V [n] = b

Falso si V [0] = b

(V [n] == b) o



if (nlt0)

return 0

else


else


Recursividad 20


notas

0

1

2

3

9

bl (v35)

bl (v25)

v n b 3

devuelve 1

devuelve 1

devuelve 1

bl (v45)

4

v n b 3

n=0 y v[nminus1]=b

n=0 y v[nminus1]=b


6

5

7

4

b n v 5

5

5

Recursividad 21




v n 2

v n 0

v n 1

notas

6

5

7

4

0

1

2

3

9

v n 4 b

v n b 3

bl (v48)

bl (v38)

bl (v28)

bl (v18)

bl (v08)

n=0

n=0 y v[nminus1]=b

n=0 y v[nminus1]=b

n=0 y v[nminus1]=b

n=0 y v[nminus1]=b

b

b

b

8

8

8

8

8

devuelve 0

devuelve 0

devuelve 0

devuelve 0

devuelve 0

Recursividad 22






subvector derecho




Recursividad 23









BUSCA (v i t-1 x)


Recursividad 24


int centro

if (ilt=d)

centro = (i+d)2


return centro

else



else Buscar dcha


else i gt d


Recursividad 25




Recursividad 26


Recursividad 27







Recursividad 28




Recursividad 29





return cad

else




res = cad

else

string aux auxcad





Recursividad 30


Lıneas basicas









Recursividad 31



Ejemplo

Recursividad 32





if (izda lt dcha)

Particionar v












Recursividad 33








izda++




dcha--



dcha--

izda++


cruzan izda y dcha



Recursividad 34

Ejemplo

Recursividad 35



Recursividad 36







mente pequeno



Recursividad 37






if (n == 0 || n == 1) return 1





if (n == 0 || n == 1) actual = 1

else

for (i=2 ilt=n i++)




return actual

Recursividad 38


Recursividad 39









else

int centro = (i+d)2





else Buscar dcha


Recursividad 40







if (encontrado)

return 1

return -1

Notas




Recursividad 41










else

if (izda lt dcha)


Particionar v






Recursividad 42




int i j pos_menor

int menor


pos_menor = i

menor = v[i]


if (v[j] lt menor)

pos_menor = j

menor = v[j]

v[pos_menor] = v[i]

v[i] = menor

Recursividad 43







374 Torres de Hanoi


using namespace std

int main (void)




cin gtgt n



return 0

Recursividad 46


if (n gt 0)







El temporal es inic


hanoi

Numero de discos 3

Del poste 1 al 3

Del poste 1 al 2

Del poste 3 al 2


Del poste 2 al 3

Del poste 1 al 3

Recursividad 47



Recursividad 48





=

Verdad si V [n] = b

Falso si V [0] = b

(V [n] == b) o



if (nlt0)

return 0

else


else


Recursividad 20


notas

0

1

2

3

9

bl (v35)

bl (v25)

v n b 3

devuelve 1

devuelve 1

devuelve 1

bl (v45)

4

v n b 3

n=0 y v[nminus1]=b

n=0 y v[nminus1]=b


6

5

7

4

b n v 5

5

5

Recursividad 21




v n 2

v n 0

v n 1

notas

6

5

7

4

0

1

2

3

9

v n 4 b

v n b 3

bl (v48)

bl (v38)

bl (v28)

bl (v18)

bl (v08)

n=0

n=0 y v[nminus1]=b

n=0 y v[nminus1]=b

n=0 y v[nminus1]=b

n=0 y v[nminus1]=b

b

b

b

8

8

8

8

8

devuelve 0

devuelve 0

devuelve 0

devuelve 0

devuelve 0

Recursividad 22






subvector derecho




Recursividad 23









BUSCA (v i t-1 x)


Recursividad 24


int centro

if (ilt=d)

centro = (i+d)2


return centro

else



else Buscar dcha


else i gt d


Recursividad 25




Recursividad 26


Recursividad 27







Recursividad 28




Recursividad 29





return cad

else




res = cad

else

string aux auxcad





Recursividad 30


Lıneas basicas









Recursividad 31



Ejemplo

Recursividad 32





if (izda lt dcha)

Particionar v












Recursividad 33








izda++




dcha--



dcha--

izda++


cruzan izda y dcha



Recursividad 34

Ejemplo

Recursividad 35



Recursividad 36







mente pequeno



Recursividad 37






if (n == 0 || n == 1) return 1





if (n == 0 || n == 1) actual = 1

else

for (i=2 ilt=n i++)




return actual

Recursividad 38


Recursividad 39









else

int centro = (i+d)2





else Buscar dcha


Recursividad 40







if (encontrado)

return 1

return -1

Notas




Recursividad 41










else

if (izda lt dcha)


Particionar v






Recursividad 42




int i j pos_menor

int menor


pos_menor = i

menor = v[i]


if (v[j] lt menor)

pos_menor = j

menor = v[j]

v[pos_menor] = v[i]

v[i] = menor

Recursividad 43







374 Torres de Hanoi


using namespace std

int main (void)




cin gtgt n



return 0

Recursividad 46


if (n gt 0)







El temporal es inic


hanoi

Numero de discos 3

Del poste 1 al 3

Del poste 1 al 2

Del poste 3 al 2


Del poste 2 al 3

Del poste 1 al 3

Recursividad 47



Recursividad 48




v n 2

v n 0

v n 1

notas

6

5

7

4

0

1

2

3

9

v n 4 b

v n b 3

bl (v48)

bl (v38)

bl (v28)

bl (v18)

bl (v08)

n=0

n=0 y v[nminus1]=b

n=0 y v[nminus1]=b

n=0 y v[nminus1]=b

n=0 y v[nminus1]=b

b

b

b

8

8

8

8

8

devuelve 0

devuelve 0

devuelve 0

devuelve 0

devuelve 0

Recursividad 22






subvector derecho




Recursividad 23









BUSCA (v i t-1 x)


Recursividad 24


int centro

if (ilt=d)

centro = (i+d)2


return centro

else



else Buscar dcha


else i gt d


Recursividad 25




Recursividad 26


Recursividad 27







Recursividad 28




Recursividad 29





return cad

else




res = cad

else

string aux auxcad





Recursividad 30


Lıneas basicas









Recursividad 31



Ejemplo

Recursividad 32





if (izda lt dcha)

Particionar v












Recursividad 33








izda++




dcha--



dcha--

izda++


cruzan izda y dcha



Recursividad 34

Ejemplo

Recursividad 35



Recursividad 36







mente pequeno



Recursividad 37






if (n == 0 || n == 1) return 1





if (n == 0 || n == 1) actual = 1

else

for (i=2 ilt=n i++)




return actual

Recursividad 38


Recursividad 39









else

int centro = (i+d)2





else Buscar dcha


Recursividad 40







if (encontrado)

return 1

return -1

Notas




Recursividad 41










else

if (izda lt dcha)


Particionar v






Recursividad 42




int i j pos_menor

int menor


pos_menor = i

menor = v[i]


if (v[j] lt menor)

pos_menor = j

menor = v[j]

v[pos_menor] = v[i]

v[i] = menor

Recursividad 43







374 Torres de Hanoi


using namespace std

int main (void)




cin gtgt n



return 0

Recursividad 46


if (n gt 0)







El temporal es inic


hanoi

Numero de discos 3

Del poste 1 al 3

Del poste 1 al 2

Del poste 3 al 2


Del poste 2 al 3

Del poste 1 al 3

Recursividad 47



Recursividad 48









BUSCA (v i t-1 x)


Recursividad 24


int centro

if (ilt=d)

centro = (i+d)2


return centro

else



else Buscar dcha


else i gt d


Recursividad 25




Recursividad 26


Recursividad 27







Recursividad 28




Recursividad 29





return cad

else




res = cad

else

string aux auxcad





Recursividad 30


Lıneas basicas









Recursividad 31



Ejemplo

Recursividad 32





if (izda lt dcha)

Particionar v












Recursividad 33








izda++




dcha--



dcha--

izda++


cruzan izda y dcha



Recursividad 34

Ejemplo

Recursividad 35



Recursividad 36







mente pequeno



Recursividad 37






if (n == 0 || n == 1) return 1





if (n == 0 || n == 1) actual = 1

else

for (i=2 ilt=n i++)




return actual

Recursividad 38


Recursividad 39









else

int centro = (i+d)2





else Buscar dcha


Recursividad 40







if (encontrado)

return 1

return -1

Notas




Recursividad 41










else

if (izda lt dcha)


Particionar v






Recursividad 42




int i j pos_menor

int menor


pos_menor = i

menor = v[i]


if (v[j] lt menor)

pos_menor = j

menor = v[j]

v[pos_menor] = v[i]

v[i] = menor

Recursividad 43







374 Torres de Hanoi


using namespace std

int main (void)




cin gtgt n



return 0

Recursividad 46


if (n gt 0)







El temporal es inic


hanoi

Numero de discos 3

Del poste 1 al 3

Del poste 1 al 2

Del poste 3 al 2


Del poste 2 al 3

Del poste 1 al 3

Recursividad 47



Recursividad 48




Recursividad 26


Recursividad 27







Recursividad 28




Recursividad 29





return cad

else




res = cad

else

string aux auxcad





Recursividad 30


Lıneas basicas









Recursividad 31



Ejemplo

Recursividad 32





if (izda lt dcha)

Particionar v












Recursividad 33








izda++




dcha--



dcha--

izda++


cruzan izda y dcha



Recursividad 34

Ejemplo

Recursividad 35



Recursividad 36







mente pequeno



Recursividad 37






if (n == 0 || n == 1) return 1





if (n == 0 || n == 1) actual = 1

else

for (i=2 ilt=n i++)




return actual

Recursividad 38


Recursividad 39









else

int centro = (i+d)2





else Buscar dcha


Recursividad 40







if (encontrado)

return 1

return -1

Notas




Recursividad 41










else

if (izda lt dcha)


Particionar v






Recursividad 42




int i j pos_menor

int menor


pos_menor = i

menor = v[i]


if (v[j] lt menor)

pos_menor = j

menor = v[j]

v[pos_menor] = v[i]

v[i] = menor

Recursividad 43







374 Torres de Hanoi


using namespace std

int main (void)




cin gtgt n



return 0

Recursividad 46


if (n gt 0)







El temporal es inic


hanoi

Numero de discos 3

Del poste 1 al 3

Del poste 1 al 2

Del poste 3 al 2


Del poste 2 al 3

Del poste 1 al 3

Recursividad 47



Recursividad 48







Recursividad 28




Recursividad 29





return cad

else




res = cad

else

string aux auxcad





Recursividad 30


Lıneas basicas









Recursividad 31



Ejemplo

Recursividad 32





if (izda lt dcha)

Particionar v












Recursividad 33








izda++




dcha--



dcha--

izda++


cruzan izda y dcha



Recursividad 34

Ejemplo

Recursividad 35



Recursividad 36







mente pequeno



Recursividad 37






if (n == 0 || n == 1) return 1





if (n == 0 || n == 1) actual = 1

else

for (i=2 ilt=n i++)




return actual

Recursividad 38


Recursividad 39









else

int centro = (i+d)2





else Buscar dcha


Recursividad 40







if (encontrado)

return 1

return -1

Notas




Recursividad 41










else

if (izda lt dcha)


Particionar v






Recursividad 42




int i j pos_menor

int menor


pos_menor = i

menor = v[i]


if (v[j] lt menor)

pos_menor = j

menor = v[j]

v[pos_menor] = v[i]

v[i] = menor

Recursividad 43







374 Torres de Hanoi


using namespace std

int main (void)




cin gtgt n



return 0

Recursividad 46


if (n gt 0)







El temporal es inic


hanoi

Numero de discos 3

Del poste 1 al 3

Del poste 1 al 2

Del poste 3 al 2


Del poste 2 al 3

Del poste 1 al 3

Recursividad 47



Recursividad 48





return cad

else




res = cad

else

string aux auxcad





Recursividad 30


Lıneas basicas









Recursividad 31



Ejemplo

Recursividad 32





if (izda lt dcha)

Particionar v












Recursividad 33








izda++




dcha--



dcha--

izda++


cruzan izda y dcha



Recursividad 34

Ejemplo

Recursividad 35



Recursividad 36







mente pequeno



Recursividad 37






if (n == 0 || n == 1) return 1





if (n == 0 || n == 1) actual = 1

else

for (i=2 ilt=n i++)




return actual

Recursividad 38


Recursividad 39









else

int centro = (i+d)2





else Buscar dcha


Recursividad 40







if (encontrado)

return 1

return -1

Notas




Recursividad 41










else

if (izda lt dcha)


Particionar v






Recursividad 42




int i j pos_menor

int menor


pos_menor = i

menor = v[i]


if (v[j] lt menor)

pos_menor = j

menor = v[j]

v[pos_menor] = v[i]

v[i] = menor

Recursividad 43







374 Torres de Hanoi


using namespace std

int main (void)




cin gtgt n



return 0

Recursividad 46


if (n gt 0)







El temporal es inic


hanoi

Numero de discos 3

Del poste 1 al 3

Del poste 1 al 2

Del poste 3 al 2


Del poste 2 al 3

Del poste 1 al 3

Recursividad 47



Recursividad 48



Ejemplo

Recursividad 32





if (izda lt dcha)

Particionar v












Recursividad 33








izda++




dcha--



dcha--

izda++


cruzan izda y dcha



Recursividad 34

Ejemplo

Recursividad 35



Recursividad 36







mente pequeno



Recursividad 37






if (n == 0 || n == 1) return 1





if (n == 0 || n == 1) actual = 1

else

for (i=2 ilt=n i++)




return actual

Recursividad 38


Recursividad 39









else

int centro = (i+d)2





else Buscar dcha


Recursividad 40







if (encontrado)

return 1

return -1

Notas




Recursividad 41










else

if (izda lt dcha)


Particionar v






Recursividad 42




int i j pos_menor

int menor


pos_menor = i

menor = v[i]


if (v[j] lt menor)

pos_menor = j

menor = v[j]

v[pos_menor] = v[i]

v[i] = menor

Recursividad 43







374 Torres de Hanoi


using namespace std

int main (void)




cin gtgt n



return 0

Recursividad 46


if (n gt 0)







El temporal es inic


hanoi

Numero de discos 3

Del poste 1 al 3

Del poste 1 al 2

Del poste 3 al 2


Del poste 2 al 3

Del poste 1 al 3

Recursividad 47



Recursividad 48








izda++




dcha--



dcha--

izda++


cruzan izda y dcha



Recursividad 34

Ejemplo

Recursividad 35



Recursividad 36







mente pequeno



Recursividad 37






if (n == 0 || n == 1) return 1





if (n == 0 || n == 1) actual = 1

else

for (i=2 ilt=n i++)




return actual

Recursividad 38


Recursividad 39









else

int centro = (i+d)2





else Buscar dcha


Recursividad 40







if (encontrado)

return 1

return -1

Notas




Recursividad 41










else

if (izda lt dcha)


Particionar v






Recursividad 42




int i j pos_menor

int menor


pos_menor = i

menor = v[i]


if (v[j] lt menor)

pos_menor = j

menor = v[j]

v[pos_menor] = v[i]

v[i] = menor

Recursividad 43







374 Torres de Hanoi


using namespace std

int main (void)




cin gtgt n



return 0

Recursividad 46


if (n gt 0)







El temporal es inic


hanoi

Numero de discos 3

Del poste 1 al 3

Del poste 1 al 2

Del poste 3 al 2


Del poste 2 al 3

Del poste 1 al 3

Recursividad 47



Recursividad 48



Recursividad 36







mente pequeno



Recursividad 37






if (n == 0 || n == 1) return 1





if (n == 0 || n == 1) actual = 1

else

for (i=2 ilt=n i++)




return actual

Recursividad 38


Recursividad 39









else

int centro = (i+d)2





else Buscar dcha


Recursividad 40







if (encontrado)

return 1

return -1

Notas




Recursividad 41










else

if (izda lt dcha)


Particionar v






Recursividad 42




int i j pos_menor

int menor


pos_menor = i

menor = v[i]


if (v[j] lt menor)

pos_menor = j

menor = v[j]

v[pos_menor] = v[i]

v[i] = menor

Recursividad 43







374 Torres de Hanoi


using namespace std

int main (void)




cin gtgt n



return 0

Recursividad 46


if (n gt 0)







El temporal es inic


hanoi

Numero de discos 3

Del poste 1 al 3

Del poste 1 al 2

Del poste 3 al 2


Del poste 2 al 3

Del poste 1 al 3

Recursividad 47



Recursividad 48






if (n == 0 || n == 1) return 1





if (n == 0 || n == 1) actual = 1

else

for (i=2 ilt=n i++)




return actual

Recursividad 38


Recursividad 39









else

int centro = (i+d)2





else Buscar dcha


Recursividad 40







if (encontrado)

return 1

return -1

Notas




Recursividad 41










else

if (izda lt dcha)


Particionar v






Recursividad 42




int i j pos_menor

int menor


pos_menor = i

menor = v[i]


if (v[j] lt menor)

pos_menor = j

menor = v[j]

v[pos_menor] = v[i]

v[i] = menor

Recursividad 43







374 Torres de Hanoi


using namespace std

int main (void)




cin gtgt n



return 0

Recursividad 46


if (n gt 0)







El temporal es inic


hanoi

Numero de discos 3

Del poste 1 al 3

Del poste 1 al 2

Del poste 3 al 2


Del poste 2 al 3

Del poste 1 al 3

Recursividad 47



Recursividad 48









else

int centro = (i+d)2





else Buscar dcha


Recursividad 40







if (encontrado)

return 1

return -1

Notas




Recursividad 41










else

if (izda lt dcha)


Particionar v






Recursividad 42




int i j pos_menor

int menor


pos_menor = i

menor = v[i]


if (v[j] lt menor)

pos_menor = j

menor = v[j]

v[pos_menor] = v[i]

v[i] = menor

Recursividad 43







374 Torres de Hanoi


using namespace std

int main (void)




cin gtgt n



return 0

Recursividad 46


if (n gt 0)







El temporal es inic


hanoi

Numero de discos 3

Del poste 1 al 3

Del poste 1 al 2

Del poste 3 al 2


Del poste 2 al 3

Del poste 1 al 3

Recursividad 47



Recursividad 48










else

if (izda lt dcha)


Particionar v






Recursividad 42




int i j pos_menor

int menor


pos_menor = i

menor = v[i]


if (v[j] lt menor)

pos_menor = j

menor = v[j]

v[pos_menor] = v[i]

v[i] = menor

Recursividad 43







374 Torres de Hanoi


using namespace std

int main (void)




cin gtgt n



return 0

Recursividad 46


if (n gt 0)







El temporal es inic


hanoi

Numero de discos 3

Del poste 1 al 3

Del poste 1 al 2

Del poste 3 al 2


Del poste 2 al 3

Del poste 1 al 3

Recursividad 47



Recursividad 48







374 Torres de Hanoi


using namespace std

int main (void)




cin gtgt n



return 0

Recursividad 46


if (n gt 0)







El temporal es inic


hanoi

Numero de discos 3

Del poste 1 al 3

Del poste 1 al 2

Del poste 3 al 2


Del poste 2 al 3

Del poste 1 al 3

Recursividad 47



Recursividad 48



Recursividad 48

recursividad (1).pdf

Documents