recursividad

5/9/2018 recursividad

1/20

CAPITULO~

La r O CU f s; vi ds d 621La comprension del concepto de recursividad, como se ve, es diflcil; rrataremos deexplicar con ejempJos sencillos definiciones recursivas,

LA RECURSIVIDADUn ramo de rosas

"Es 0 bien una rosa (I) 0 una rosa junto con un pequeno ramo de rosas (1)."

CONTENlDO, 6,1. La naturaleza de la racursividad, 6.2. Elsaguimiento de la recursividad16.3. Pilas16.4. Subprogramas recursivos con parsrnetros t ipa 8rray16.5. Laefi ciencia ( fterac i6n versus recursividad}16,6. Racursividad indirecta: declaraci6n Forward, 6.7'. Busqueda binarie recursiva, 6.S. Ordenaci6n rapida (quicksort), 6 . 91 . Ordenacl6n por mezc!a (ordenaclon external16,10, EIproblema de las Torres de Hanoi16.11 _ Recursi6n mutua16.12. La recursividad, pros y centres tstntesls)'6.13. Puesta a pumo de pregramasRESUMENEJERCICIOSPROBLEMAS

Un descendiente (par ejernplo. del Sr. Mortimer)Una persona es descendiente del Sr . Mortimer si( I ) esta persona es un hijo del Sr . Mort imer , 0(2) esta persona es un hijo de un descendiente del Sf . Mortimer.Observese que las palabras ra mo de rosas y deseendiente se uti lizan para defini rse a s imismas. La caraeterfst ica irnportante de Larecursividad es que siempre existe un mediode salir de L a definicion, En los ejemplos a n te ri or es , l a condition L se denomina Sal idade la definicion (en su case algoritrno recursive), Y l a condicion 2 parte recur s tva pro-piamente dieha 'I que garantiza que siempre.evenrualmente se alcance la Salida: cuandoel ramo este cornpuesto por una rosa 0 el descendieme es hijo del Sr. Mortimer, se ter-mina el proceso recursive.En Pascal los procedimientos y funciones pueden ser defiaidos de modo recursive, esdecir , pueden llamarse a si mismos, EI procedimlento recursive mas s imple es:

Un subprograma (procedimiento 0 fund6n) recurslvo es aquel qua sel lama a sl misrno, En Pascal los procedlmientos y las fur-clones pue-den ser definidos de mode recursive. La recursividad es una eherna-tiva a lalteracion 0repeticlon, y aunque ell tlernpo de computadora yen ocupacl6n en memoria es la so luci6n recurstva menos efi cian leque la soluci6n rterauva, exlsten numerosas srtuaclones enlas que 18recursivldad es una solucion simple y natural a un problema que encase contra rio ser;~diffcll de resolver. Por esta razon se pue


2/20

622 Programac i6n en Tur lx ljBo rland Pasca l 7 La recursivuied 623

51- 5 (5 - J) (5 - 2,. (5 - 3)" (5 - 4) (5 - 5) = 5 .. 4 .. 3 + 2 I 120Ejemplo 16.2D is en a r la fu nc io n q ue r ep re se nta a fa s er ie d e F ib on a cc i: 1,},2,3.5,8,13,21,34 .....

asi, para el caso de n =5.

que se puede expresar tarnbien como5! - 5 .. 4 !

La sene de Fibonacci se representa asl:

1 /1n. - n" (11- 1)! xix i n = 0n> 0

Fib (L) >= IF ib (2) = IFib (3) - Fib (2) + Fib (I)Fib (4) =Fib (3) + Fib (2)

y generalizando

que es una defin icion recursiva, ya que contiene las dos condiciones 0 partes menciona-das anteriormente:I . Condicion de sal ida: n = O.2 . P arte recursive: n! ~ n .. (n - 1)1

Sabre la base de esta descripcion se puede declarar una funcion recursive,

Esta funcion se define recursivamente del siguiente modo:

Fib en ) = I = .w (n - I) "I" Fib (n - 2) sisi n = 0, II~1n>1La deelaraeion de la funeion recursive es:

function Factoria.l (n' integer) 1 intl!geri{ ca lo ul o d el f ac to ri al d e n (nl).I 'r e , n e et a d ef in id a y n>~OP oe t , f ac to ri al (n) = nl}beginif n=Othen factorial :=1else factorial , = n " factorial (n-l)end;

f un ct io n F ib on ac ci ( in te g~ r) : i nc eg er{ da do u n n um er o n c om o p a. ra me tr o d e e nt ra da e et ,a f u nc io n c al c, -\ la daa1 n -e ei mo d ~ F ib on ac ci }beginif Cn=I) or (n=2) = 2

then Fibonacci := 1elae Fibonacci ,= Fibona.cci (n-2) + F ib on ac ci ( n- 1)end; {Fibonacci}

La funcion esta declarada s610 para enteros positivos, ya que n! noexiste para II < O.Observese, s in embargo, 'que Ja funcion factorial no esta bien declarada ya que cuando11 = 10, to! ~ 24320, y en el caso de 11 - I I , se superana ampl iamente el rango de losenteros (32767). Por esta razon serfa mejor def in ir la funcion factorial, bien de t ipo word(range 0...216 - J). bien de tipo longint (rango _231 ... 231) 0 de tipo real.

La version iterauva de 1a func ion fac tori a l es:

end..

Problema 16.1U n p ro gra ma qu e ha ce u so d e F ib on ac ci e s:

function Factorial Cn: i nt eg er ) , r ea l;varFact, J : integer;beqin

p ro gr am v er F~ na cc i ( in pu t, ou tp ut );varI,oJ : integer;

Fact := 11functioD Fibonacci IN : integer): integer Ibegini (N=l) or (Ha2)t.hIlnF ib on ac ci , ~ 1elseFibonacci := Fibonaccl,(N-l) + Fibonacci. (N'-2)

fo r J ;= 2 to N doFact ,~ Fact * J;Fa ct ori al , _ Fa ctend)

Observese que Ia version ite rativa contiene un buck for como su estructura de con-t ro l importante , mientras que la versi6n recursiva contiene una sentencia if. Tambiennecesita una variable loca l Fact en la ver sion ite rativa para contener el producto acu-mulado.beginw~iteLn ('Introdu.zcanumero de t er ro in os d e l a e ue es i o n' )1 ;ReadLn (J);


3/20

624 Progrllmllc idn en Turbo/BonanrJ Pascal 7Wri'te ('los primaroB '. J,l,' nurner'os"iWriteLn C'de la sucesion de Fibonacci son: 'I;fo r I . = 1 to J doW.rite (Fibonacci(I) :1 ' ');Wri'teLn

end.

Ejempto 16.3E I a lg ar itm o d e E ud id es pam encomrar el mcd (maximo CQmli ll divisor) de dos mimerosen/eros posiuvos (M y N) SI! p u ed e d e ft nt r r ec u rs iv am ent e:A/godlmo de Buclides: el mcd de dos enteros es el emero mayor oue divide aambos .

M INqJ q2 q3 r I ql_codenteM N rl r2 T es t 0rl r2 r3 N Irl

r2 q2rl I r2r3 q 3

Cuando el tdtima resto es cera (par ejemplo, r3=0), el mcd es el Iillima divisor (en esecaso. r2).

El algori tmo recursive se puede defin ir con los s iguientes pasos: mcd (m, n) =n si /I Pi !thenWriteLn (lieD (M,NIIelaeW l : " i t e L n ( MC D ( N, M) )end.

16.1.2. ProcedimientosrecursivosLos ejemplos presentados has ta ahara son funciones recursivas, Son pos ibles tambienprocedimientos recursivos,Ejempto 16.4Obtener el mimero inverse de uno dado .

254: su in verse es 5i12


4/20

626 Programad6n en Turbo/8or1and Pasca l 7 L 8 rBCUf'Sfvidad 627

d3 ~ 2

procedure InversoTol:.al/va>::

X : inte_ger;beginif not eof tben

bginRead (X);InversoTotal;Write (Xl

end

Se genera invirtiendo las cifrasQ - 254 254 m od 10 - 42 5 4 d i v 1 0 ~ 2 525 mod 10 g 525 div 10 ~ 2

2 mod 10 ~ 2

dl ~ IId2 ~ 5

Se genera 452; asi pues, el procedimiento es: end;procedure Inverso (n : intege.r);{pre , n >.= 0post : 109 digit09 de n se situan en orden inverso en la salida}beginWrite (n mod 10)1if'n >= 10 then Inverso (0 div 10)

en d

Ejempto 16.6Leer una palabra (una cadena) y generar su pal indrome: EI palindromo de Venezuela esaleuzene V.Consideremos la obtencicn del pal indromo de una palabra leida por teclado (numero decaracteres y palabra).

Problema 16.3Apficaciol l del procedimienlo Invettir: Leer 1m numero entero por teclado y proporckmarSII mimfI/"o inver/ida.

p.rocedur'e Invertir. (N iotege.r I;beginWrite ( 1 ' 1 mod 10 '1);

if N>~ 10then Invertir IN div 10 )

procedure Pal indrorno In ; l.nt"ger);varSi g ,char; {siguiente data caracter}beginif n


5/20

62B Progrsmac ion en Turbo/Bor/and Pasca l 7 La recurs/v/dad 629procedure Palind.r'omo (var P : Cad2SS; Nbegin

integer) I Ejemp/o 16.6 (Palfndromo)

thenWeHu (PI1Ilele ..

beginW.ci te (PI Nj);Palindromo (P,R - 1 )end

U am ad a r ec ur si va cond icion de sal id a P a1 ; ndromo (n-1)n < 1

end;16.1.4. Tipos de recursividadLa recursividad puede ser de des t ipos:

W:dtaLn ('i nt ro d:uzca u na p alabr a');(P.a_labra.)(Palab.c a,L en gth (Palabra;

recurstvldad dlreaa (simple)un subprograma se llama a sf mismo una 0 mas veces directamente,

r ec ur siv id a d i nd ir ec ta ( mu tu a }un subprograms A llama a orro subprog rarna B y esta a su vez llama at subp ro-grarna A.

beginReildLnpalindernnoWeiteLnand.

, 6.1.3. Sintesis de la recursividad Los subprograrnas reeursivos estudi ados hast a ahora son recursivos direc tos, en l aseccion 16.6 analizarernos L a recursividad indirecta mediante la declaracion fDrward.Los subprogramas recu rsivos deben contener siernpre las dos panes 0 sentencias si-guientes;

I . Una l lamada a si ,"!sma (reeursiva); normalmente con el valor de los pammel:ros q 1 Wc am bian en eada Hamada .2. U!):acondition de lerrninacion 0salida, que cS la ClJlldicion que no produce ningunaautol lamada,

16.2. ELSEGUIMIENTODELA RECUASIVIDADEI seguimiemo (traza) de un a l go r it m o es el meier metoda para entender y comprobar suf un ci on am ie nt o. L o s algodtmos re cu rs iv os n o so n u na e xc ep cio n, y po r ello realizare-mos el seguirniento de a lgunos e jemplos ya tratados,

Recardemos los ejernplos citados anteriormente. Funci6n FactorialEjemplo 76. 1 (Factorial) 1lamada recursive condicion de sal ida

r ac to ri al ; - n" f a c t o r i a l (n-l)nB Of un ct io n F ac to ri al ( N integer)begin1 N ~ 0then Factor i al ,~ 1e lse Fact or ial := N * Factorial (N - 1)

word;

Ejemplo 16.2 (Fibonacci) H a ma da r ec ur si va condicicn de sal ida

end;Fibonacci; = Fibonacci (n-l ) -y mm od n

Ejemplo 76.4 (Inverso) Hamada recursiva c on dic io n d ie s a lid a Inverse (n div 10)n < 10

n ~3 L la ma da a F ac t o ri a l ( 3)n ~ 0 : n oF a c t o r i a l : - 3 * F ac to ri al ( 2)

rp.2 L1amildil a far;torial (2)n = 0: IUlF a c t or i a l : - 3 * F ac to ri a l ( I)


6/20

630 ProgramiJci6n en Turbo/Bor land Pasca l 7

n..l Llilmada a Factori ill (1)n - 0: noFactorial ;- 3" Z .. 1 .. Factorial (0)

0-0 Lldllli.! da a Factorial (0)n - 0: sfFactorial ;- 3 * 2 1Factori a J - 6

La recurswiaed 631Funcion FibonacciColculo del termino qutmo de Fibonacci: Fibonacci (5).

Fibonacci (5 ) -Fibenaccl (3 )Fibonacci (1)Fit!onacci (2)

La represeutacion graf ica del proceso recursive se indica en la F igura 16. J.n= 3 1Factorial :=3 Factorial (2)Retorno

In" 2Factorial ;=2 Factorial (1)R:elomo

In= 1Faetortat ;~ 1 Factorial (0)A:etomo

I,,0F ac to r; a! : '" ' 1Relor'no (Return)

~ 1- 1~T

Fibonacci (4 )Fibonacci (2) = 1,ibonacc i (3)fibonacci (1) = 1!Fibonacci (2 ) = I

= 2=-3-F ib on acc i ( 5) = 2 3 = 5actorial" 6

16.3. PILAS*3

= 2

i.C6mo realiza tecnicamente Turbo Pascal la operaclon de recursiv idad? La implemen-raciol l de la recursividad se haee can el lJ5I) de una estructura denominada pila (stack).Una pila es un espacio 0 ZOn!! de la memoria a la que se accede de Ull modo especial: elprim er ele men to en en tra r es el Ii/rimo e le me nto e n sa lir (tambien se Ie denomina LIFO" l a s t- i n . f i rs t -ou t ' : ultimo en entrar 0 llegar-primero en salir, 0 tam bien proceso llegado-ult imo servido), Su analogia m a s clara en la vida ordinaria esta en la pila de plates deuna cocina, 0 en una piia de folios para una impresora, etc,Turbo Pascal gest icna la memoria necesar ia para la recursividad mediante zonas dememoria tipo pi la , La pila esta l imitada en espacio por unas direceiones de memoria fi-jus. Los conceptos fundarnentales en una pila (Fig, 16.2) sou: puntero de pi1i1 (Slack poin-ter), operaci6n de meter datos en Ia pi la (pop), operacion de 1impi ar la pila 0 deja]' la pilavaeia (sin elementos) y tamai'ill 0 lon91tud de la pila (capacidad),

Factorial = 2

2

Factor te t ~ 1 meter -

puntaropila (pJ

t pilaano vaclaH a lp _,,*_..L..--I

tamp

,-saca[fa .1-----1+- PFigura 16.2. Conceptos bbslcos de una plla.F lI cto ria l ~ 1

Pascal trtiliza a J menos una pi la durante la ejecucion de cualquier programa para al-macenar valores de variables. constantes, parametres y direcciones de retorno (Figu-ra 16.3.),Figura 16.1. Seguimiento del algoritmo recursivo Factorial. En el Capitulo 17 s e ampliara este ccnc epto de bido n su importancia en el mundo de III pmgrllllUl.ci6n.


7/20

632 ProgromacJ6n en Turbo/Bar/and Pascal 7

AsigrlBCl6n de especiapara una /lamadade funci6nA stgnac i6n de esoecspar .. uflll Ramadade procedimiesno

vlliore nc oru ra c 0de III funcl6n fir\ill

vanabIas locales vana blesl n c a t e sp __ "-- Jdireccl6n de retorno dlrecci6nde retornoCuando se l Iega al calculo de Factor ial (0)parametro,s valor pan!metros valor

Figura 16.3. AsignaciOn de sspaclo en l Iamadas reeursfves.

piiavactap-+------I

p----'II4------lp-+r-------l

633

beqinil n > 0

J

2

J

then Factorial : ~ n ~Factorial (n~l )eLse Fa,ctoria1 .~ 1;

2

end;

3

Ejemplo 16.7AplicarirJn de lafuncion Factorial.

como n =0, se obuene direc tarnente Factorial - I; y al encontrar el final de la funcirinfactarial se saca de la pita el ultim o elem ento, I , y el puntero d e p ita desciende: en 1:0segunda l Iamada a Factorial se 5IIca el siguienre elemento de la piia, 1, '! el puutero depila, y as-isucesivameute.

program f",c;functio'!l factorial (n integer) real; p--I-----Ibegin.if n > 0than Factorial r= ractori a l (n~l J * nel~e Factorial ,~ 1

end;begin {programa princip",J}Write'Ln ('31 ~. Factorial (31,1,0}end. {llamada a Factorial}

Jp---+-------l

2p-+--------1

2

p-......----16.4. SUBPROGRAMAS RECURSIVOSCON PARAMETROS TIIPOARRAYTras la s llarnadas sucesivas se van almaeenando Ias dir ecciones de re torno :y losparametres valor 3, 2 I). En la primera l 1 amada se a lmaesna en la pila el valor 3 y la

direecion de retorno. En la segunda Hamada SI: almacena 2 y la segunda direccion deretorno, y asi sucesivamente,Los subp rog ramas analizados a n te r io rr n en te i nc o rp o ra b an p a ram e tr e s de t ipo s imple; es~osi.bh:l lItiliza: tipos c om pu esto s c om o arrays, y aunque la f llosofta de disei\o es rnuySimi lar , exarmnaremos diferentes problemas co n arrays como parametres,Ejemplo 16.8Imprimir los elementos de un vector en arden inverse can un procedimienlo recursive.

Factorial (3)1 . . 1 - - - - 1 3. Fllclorial(2)1 . . 1 " '2 . Factorial ('1. . . . , 1 Fi""lor;,,1 (0)

a retomo ,-11

, !torno 3-+

JAnalisis

retorno2__

6 rewmo1'_Sea el vector A; array [I . n] of integerLo s elementos del vector ASOil: A[I], A[l] , A[3], ... , S [n )Los elementos de A . en orden inverso S O il : A [ n) , . 1 \ [ n~ I] ; .... A.[2], A [1)Condir:i6n de salida n "" ICondi ci a r e cu r si va imprirnir A [n ] u l t i rno elememc A

irnprimir vector A [1 . . n ~ I)


8/20

634 ProgUJmaci()n 9n Turbo/Bor land Pasca l 7 La rflfi:ursMdad 635Algorirmo C6digo

si n = 1e nt on te s e sc ri bi r A ( 1)s i n oescribir '" e n )escribir e1 subvectcr 1\ [1..n-l] [Inver-so (1\, n-Lj ]fln...si

typevector ~ array [1.. 100] of integer1varLlsta , vectoJ:;

proq,rrun SumaRecu"s iva;typeVector = arra.y [1.. 100] of integer;

warLiata , VectOJ:iN , integer;

function Suma (var A , vector; N : ~ntege~) ; integer;{Pre : array A y /I sstan definidos y n > OJ{post: devuelve la suma de los N elementos de A}beqin {Suma}if N = 1thenSuma :=11.[1]

els6Suma:= lI.[NJ + Suma (A, n - . 1 - )

end; {Suma}beqLn {programa principal}

N r= 4;Lista[l] se= 5; List.a{2J r= 25; Liata[3] :'" 0; Liata(4) ;= 301WriteLn ['La Burnaaai ", Suma(Lista, 4end. {programa principal}

Programs

procedure Inverao (var A: vector {entxadah n:integer {entrada}):{pre , El vector A y n eeta.n definidos y n " O}{post: s.alida A[n), 11[0 -'1]. '" , A[l)}beginif n" 1t he n W ri te Ln ( Al l) )else

begin {paso recursivo)WriteLn I I ' . [n Jl ;Inverso (A, n - 1)end

Ejecuci6nend; La suma es 60

Ejemplo 16.9lmprimir la suma de elementos de 1 1 1 1 vectorA de subindices 1..n con unafuncion re-cursiva. 16.5. LA EFICtENCIA (ITERACION VERSUS RECURSIVIDAD)

EntradaVector AS a l id aSumaSuma

(vector A. nJA [ l ] . A [ 2 ] , A [ 3 ] , , A [ n ](Suma)

- A [ 1 1 + A [ 2 ] 1" 1\(3] + ... + A[n]- "'[n) + Suma (A[l), "'[2], . .. ,A[n-l))

Una vez vista como funciona la recursion, analicemos la eficiencia 0 eficacia de lamisma. La recursividad parece un metoda simple para resolver problemas medianterelaciones recursivas; s in embargo en ocasiones se puede volver un metoda ineficienteya que se realizan m a s calculus que suequivalente solucion repctit iva,Como ejernplo, y para medida de laeficiencia de los algoritmos reeursivos, conside-remos de nuevo la serie de Fibonacci 'jel algoritrno ya examinado (fl, termino ;-esimode la serie),

Analisis

2 3 5 8 II 1 9 ...Aigoritmo /2=2 fi ~(fi - J) + (fi - 2) parai>=2

sf n = 1entonces Suma _A[I]s ino Sumar A [ n ] a l a suma A[I] + A{2] + ... + A[n-I]fin-s1

Mediante una solucion repetitiva se necesltarian aproximadamente n Iteraciones. Enel caso de la solut ion recursive, si considerarnos Af el numero de veces que se llama lafuncion Fibonacci para calcular fl. se tiene:


9/20

636 P''09fBmse,6n en Turbo:/Borland Pascal 7 La fl!Cursillidad 637

A. - 1 + A._. + A'_2 para i> =2por induccion si se desea calcular f. . se tiene

A~ = 2 / '. _ 1 - 1Es te Dwn er o de llamadas para ealcular f. . es considerable mente mayor qu e el numero

de ieraeiones de la 501 ucian i terati va, Por ejemplo, para catcular 1; 1 se necesitan aproxl-madamente once iteraciones, mientras que una solueion reeursiva necesita 27&lIamadasa Lafuncion. Na turalrnente, Laserie de Fibonacci no es conveniente generarla por unmetoda recursive.La eflcacia de un algoritmo recursive viene medida par una sene de facto res. entreotros se destacan:

tie mp o d e e ie cu cio n, espa cio e n m em oria o cu pa do po r e l a lgo ritm o, legibilidad y facilidad de comprension.Desde el punto de vista del tiempo de ejecucion, los algcr itmos recursivos son maslentos y ocupan mayor espacio en memoria, con el inconveniente que puede suponer enel caso de poca memoria disponibJe. Si n embargo, en ciertos problemas, la recursiv idadconduce a soluciones que son mucho mas Iaciles de leer y comprender que su corres-pondiente solucion i terative; en estes casos laganancia en claridad puede compensar cancreces el cos te en t iernpo y en memoria de In ejecucion de programas recursivos, La sdefiniciones recursivas se caracterizan por su elegancia y simplicidad en contraste con Iadlficultad y falta de claridad de las definiciones repeiit ivas.La s o iu c ie u r ec u rs iv a e s e s te ti eam ent e m a s agradabLe, y una ve l acosrumbrado, laforma recursiva es normalrnente mas facil de leer y cornprender que Is forma iterativa.Algunos programadores ut il izan la reeursiv idad como una herramienta conceptual : unavez Qu e ban escri to Laforma recursiva, buscan Laforma de converr ir la en una versioniterative y asl ganar en eficiencia , en t iempo de ejecuci6n y ocepacien en memoria.De cualquier forma, como se vera en este mismo capitulo, numerosos problemas son

dificiles de resolver con soluciones iterativas, y s610 Lasolucion recursive conduce a Isresolucion del problema. No obstante, no abuse del metoda recursive m a s que cuando seden las circunstancias explicadas en esta seccion.

En ella se ve que Laeficieneia es de tipo exponencial y claramente -como ya Sf hacomentadc-> no se recornienda su usa. ya que para In=31 se necesitan 2.178.309calculos.Estes resultados confirman las tesisarueriores relauvas a la leruitud de los algoritrnosrecursivos. Recuerde, no obstante. las ventajas posit ivas de la recursividad tanto si deci-de aplicarlo a su problema como si no le queda otro remedio por 13 n aturaleza delmismo.16.6. RECURSIVIDAD INDIR'ECTA: DECLARACION FORWARDCuando un procedirniento 0 funcion se l lama a s l mismo. eS\3 propiedad se denominarecursividad direaa. Se tiene recursividad tndlreaa 0 mutua ruanda dos (0 mas) proce-dirnientos se lIaman mutuamerne,Supongarnos que el procedimiento P llama al procedirniento Q y viceversa, se podriaescribir:

p ro ce du r e P ( . .. ) ;. . . Q ( . ) . . . ;preceders Q( ' .' . ) ;. . . Q ( ... ); .. ;,

Sin embargo. este codigo no es valido ya que en el procedirniento P se llama aJprocedimiento Q Queailn no ha sido defin ido; es decir , Q debena estar antes de P; peroclaro, si esio se realiza no se podria invocar desde Q bas ta el procedimiento P. Ellengua-je Pascal permite resolver este problema can la declaracion fOno"ard. La sintaxis de losprocedirnientos recursivos escabece.rll tiel:primer subpro(,Tramll;forward;cabecera del segundo procedimiento;{bloque del segundo procedimieneoj

nombs:e del primer proc6ri:i.m:l.ento;{bloque del p:dmer procedimiento}

Ejemp/o

16.5.1. Anidisis de Ia eficienciapr ocedure P (pI, p2 ... ); f orward;p r o c e d u r e Q(~]. q 2 .. ) ; f u n c t i o n B ( x : i n t e g e r l ; c h a r ; f o r w ar ~ ;p r o c e d u r e A(var y:char];

b e g i nSi se censidera !a se rie Fibonacci desde el punto de vista matematico, se obtiene la Fun-cion de eficiencia 0 recursiva siguiente: l cu e r po d e Q I

y :m B(i};Fibonacci (n) "" 0 (162") n,numero de elementos

e n d ;


10/20

638 Programac/(m en Turbo/Borland Pascal 7 La re~ur-sividBd 639

pNlcedure P; f u n ~ t ' o n B ( x ; i n t e g e r ) ; c h a r ;'beginA{e)

P or u ltim o. la s c ad en as d e r eto rn o p ro du ee n

en d

P~r (1) ;~ f a l s eend ;!mpar (2 ) t = fa 151'E n dPar (3) ;- fal see n d ;[mpar (4) ;~ fal seen dP ar (5) r= falseen d

I p a r lI m p a . r II p a r l

I c u e r p o de P I

Ejemplo 16.10Sedesea escribir {as funciones par e impar que loman lin eniero Jo ! devueiven un valor!Ogieodependiendo de la paridad de est!entero. Disenar 1 1 1 1 programa que incluya recur-sividad mutua (n.QllIralmenle. el a/gari/rna es muclu: mds sencillo sin recursividad},

l i m p a r lI s ol u t i on e s p e ra d alI p o r l

16.7. 8USQUEDA BINARIA RECURSIVAfuncti,on Par (Nurnero : integ-e,r): boolean; forward;fun,etian Impar (Numero , integer) , boolean,begin {Impar}if No.unero '" 1

tllen Imp.. := true..lse limpar :'" Par [pIed (Numero))'el1d; Impar

En el Capitulo 13 se examine el diseno de un subprograms para rea lizar la biisqueda enuna l ista (array) ordenado par el metoda de bti:squeda binaria, Reconslderernos esteejernplo y reescribamos el subprograma de busqucda urilizando recursividad, y recu-rriendo ados e st ru ct ur as m uy l re cu en te s: a l array de enteros; b) a rra v de regis tro s, y comogenerallzacion del metoda en un caso utilizarerncs una funcion yen otro ua procedi-miento,

funetion par,;begin

if Nurnero =1 16.7.1. Funci6n busquedatb.en par ,- faleeelse Par := Impar (pred (Numero)) Datos de entrada: Array erdenado AP ri me ro , U lt im o ( i! 1.d ic es e x tr em e s d e A )Clave (elemento buseado)

CentralDasos de salida: Cent ral (emero) , posicion de la clave veroadero, fal so(existe/no existe la clave buseada)

end;

Segulmiento del programsLlamar a Par (5).

Programa 5 I,. se ejecuta l a sen ten c ia Par ;~ lmpar (4),[p red (5) es 41. el control pasa ahara .1 1 Ja funci6n Impa r . 4 1, s e e je cu t a la seateccja else ! .m pa r : - P ar (3),e! control pasa ahara al a funcion Par.

function Busquad" ( .. .ar A,Lista I Max, Min: integer.1 Claveinteg-er), boolean I

va.-

Par (5)I m p a r ( < 1 - )Par (3)I m p ar ( 2)Par (1)

:- Im pa.r (4); ~ P ~ r (3);- Im par (2 );~ Par (1).~ false

Cent.ral : integer; {aleman,to central del array}beginif Mn" Maxthen Buagueda ,'" falseelsabeqinCentral p (Ha.l( .. Hi.n.) di ... 2,if A[Central] Clave

thenBusCf\'led.a :" tru'e

Las sucesivas seutencias de asignacion p ar la s que s e p as a s on :


11/20

La recursiv,dad 641640 PtC9rarn .aclon en TuIbo/Borland P a "r ;a l 7eleebeginif Clave> A (Cent~allthenMin ;= Central + 1

elseMax ,~ central - I;Busqueda ;= Buaqueda (A, Max,Min, Clave)

16.7.2. ProcedimientoBusquedaBinCons iderernos ahora un array de regisr ros,

typeInoEmp recordNombreNumSS string [30];integer; {numero de 1a Segu,"idadsocial}enell s aiarLo

EdadendArraY..Emp ..array 11. ..lOOJ of Infusquedabegj_n { pr oq ra ma p ri nc ip alRandomi'2.e;for I ,.. 1 t o M ax im o doNumeros [I] , = Random(Maximo)

varListd ; ArraY_Emp;

Parametros de emradaend. l i s t a

C l a v ePrim ero, U l rim a

(1II1I11t'roi e l l ' / a . \ 'I ! . f( l fr i dad ~o l . 'i { /I buscado )(ttmne lit,! array - tndices-]rogramal'cocec". L ista(Ce nt ral)thenPrimero := Cantral + 1eleeUltimo ,; Central - 1:ausqueda.llin(Lista, Indice, Primero, U~timo,Clave)

I nd ice (po sicio n q ue o cup e e l num ero de 1a 5S buscado , N um SS jPrograma

p ro ce du re Bu sq ue daBin (var L ista:Ar ray-Emp ; var I"dice: inte9ar/I!rime .ro.,ltimo: integer r clave:integer) ;

end!

va rCentral: integer,beginif Primer.o > 01t im o t he nIndice :~ 0elsebegin

Central :; (Primero + Ultimo) div 2;li C~ave = List" ICB.ntral).NumSS thenIndice := Cen'tralelse

~ clave < Lista [Centrall.NumSSt.henbeg!.n {buequeda an la primera mi tad}Ultimo := Central-I;BusquedaBin {Lista, I nd ic e, Pri me ro , Ulti mo ,Clave )en d

endend; (busquedabegin {programa prinCipalRandomize,fo r r := 1 to Maximo doNumero.. [I) := Random (Maximo) else

begin {busqueda en la segunda rnitad}end.


12/20

642 Programac/6n en Turbo/Bar /Md Pascal 7

Primaro :~ Cent~al + 1;BusquedaBln (Lista, Indica, Prime~o, Ultimo, Cla~e)nd

end {else}end fBusquedaain}

16.8. ORDENACIONRAPIOA (QUICKSORT)Uno d. I", m,,_ m., nlpid", Ymas " " " " " " m " , , , ,til",",o" o"'''''''iOn d. """"esel con""ido como " " 0 " " 0 "pld, (Q,,;,*SO,,). F" in"",,,,,o por C. H. " , 0 , , , .y'""n'idod d. '''''igo """"no" "',preod"""",,",, " " " ' ' ' ' 0


13/20

644 Pragramac;,(m en Turbo/Borland Pascal 7Sintact icamente hablando. s i el array original es a Programs ordenaci6n rapida

fOT k ~ 1., - I(k-I ..5)rOIr k ~ 1 + J..N 10(k =6..9)

Si se utiliza J como indice final de la primera sublista, se tiene:Sublista izquierda 1..1 (9 IS 13 17 19)Sublista dereeha 1.N ([llJ 31 23 26)

a [k ] -c= 20a [kJ > 20

p ro gram Te st Rap id o ;typeE nteros ~ a rr ay [ 1..1 00 1 of integer;

vazLista B nteroslK integer;

p ro ce du re R a pi .d o ( va r . ..Ent,aroal N integer) ;7. La ordenacion de las sublistas implica el mismo proceso que antes, excepto que losindices en el caso de Lasublista son (1.. 5) Y(6 . .9). los paws en el caso de la sublistaizquierda son:

p ro c ed ur e Part ir (l'ri mer o ,Ulti mo integer) ;varI, JCentral integer;integer;

Subltsu: izquierda I9 15 @ ] 17 19t fI J9 15 qJ 1 7 19tI J9 [ J 15 17 19tJ I

Algorirmo de ordenaci6n rapids

Sublista izquierda 119@ ] Subtlsta lzquierda 121 9 procedure Intercambiar (vax M, NvaxAulIC , integer; integer) ;1 5 17begin { IntercambLarSublista '12ublista 111 "UK := 1 ' 1 ;

M := III;9 13 N ;= Au xend; I nt er ca m bi ar }Sub/isla izquierda I ordenada1 7 19 begin { PartirI , = l'rimero;

.J ; = Ultimo;{ encontrar Elemento pivote (central) }Central := A [(Primero + U lt im o) d iv 2);repeat

w hi le A [I ) < C en tr al d or :=I + 1;w hi le A [J ] > C en tr al d oJ :~J - 11'if r .1;if Primero < J

then partir (Primero" J);if I < Ultimothen partir (I, Ultimo)

and; { Partir }

13 15

I. Initial izar I a Prirnero (primer indice del ol/"r-ur)2 . Ini ci al iz ar J a Ultimo ( ultimo indice del ",-raY)3. Seleccionar e1 e lemento p ivo te (tenvino Central)C e n t r a l +- A (Prim~ro + Ultimo) d i v 2 ]4 . r e p e t 1 r

4.1. 1I1entr as A[ I ] < Central hacer1_1+14.2. lIJientrss A(I I > Central heeerJ _ J-1

4.3. $1 I Pr inern , l l amar al procedimiento Part ir , para dividtr [a subl+staizquierda (Primero .. Jj6. sf I < Ultimo, llmnara al procedimiento P~r tir. para diyidir la sublist a derecha[J .. U1 tima]begin {Rapido}Partir (1, N )end; (Rapido}

La recursMdad 645


14/20

646 Programsclon en Tu,bofBoriand Pascsl 7 La recursillidad 647{ programa princip ..l }begin{ lectura de 10 0 anteros aleatorios }for K , = 1 to 100 dobegin

List..(KJ := Random (1000);Wri-ce (Lista [K] :8)end;

W r l . t e L n ;{ 11...mada a1 procedimiento Rapido }Rapido (LLst a" 100);{ esc::rltura de 1 .. 1ista o rC ie na d . . }for K :~ 1 to 100 doWrite (List .. [K] : BII

3. Ordenar l a subli st a derecha,4. Mezclar las dos sublistas juntas.Ejemplo 16.11O rd en ar p or m ez clo la lis ta .

9 3 5 10 4 6E[ p r oce so consi st e en dividir la l is ta en dos mi tades y cada una de las rn itades en o trasmit ades. Est e proceso se repit e hasta que cada subl ist a conriene, cada una , una entrada,s eg un s e a pr ec ia e n e l g r af lc o,

l ' I r i t e L ne n d .

16.8.1. Analisis de la ordenaci6n raoldaEI metoda de o rden acion rapids es el m as v elo z d e [ as c on oc id os , E I tinieo inconvenien-te de este metoda es la cantidad de memoria Que se requiere en la pila, Caso de tenerproblemas de memoria , debera rea li zar pruebas para evirar e rrores en e jecucion, En estecaso Ie recomendamos uti lizar el metodo de Shell.

S i se supone que [a li st a se divide si ernpre en dos par tesigual es, entonces, despues dela d-esima division de la I ista , se t endran 2 '/ par tes. E1numero de lt eraciones del proce-dimiento partlclon (partir) es a (n) para t adas l as panes . Como habra l ag!i1divisiones . e la lg or it m o r eq ue ri ra 0 (n IOg2n) .

9 3 5 10 4 6

16.9, ORDENACION POR MEZC1A (ORDENACION EXTERNA)Todos los a lgor itmos de ordenac ion en este y en e J Cap itu lo 13 son metodos de ordena-cion intema; es dec ir , e l conjunto comple te de e lementos a ordenar se deben a lmacenaren memoria principal. En numerosos problemas de tratamiento de datos, e l conjunto dedatos es demasiado grande para almacenarse en memoria principal (no caben) y debenalmacenarse ell memoria exte rna, Para ordenar estas colecc iones de datos ( los archives)se requie ren algoritmos de ordenac ioa exte rna, Un metoda muy papillar y eficiente esetconocido como ordenaci6n por mezcla (mergesort).

Como su nombre sug iere, la idea basica de la ordenacion es 13meseta de archives yaordenados, La f iJ os of fa d e l a m e zc la ya 13 c on oc e e J l ector del Capitulo 13, la d i Ierenciareside en que en este caso los archivos est aran ordenados por un campo clave dete rrni -nado. Como la mezcla de arcb ivos es analoga a 1a mezcla de listas, considerernos perfac ili dad de compresion e l a lgor itmo de ordenaei en por mezcla de li stas,

La mezela comienza can las subli st as de un solo et ernento, que sernezcl an en sublis -tas mas grandes cuyos elementos estan ya ordenados, y et proceso continua basta que seconstruye una unica l ls ta ordenada.

L2 LlAlgor;tmol.Dividir laIista 'ell dos rnitsdes.2. Ordenar la sublista izquierda. L


15/20

648 Programacidn en Turbo/Borland PasGl iI 7 La reaufSNldad 649EI diagrams de mezcla se ilu stra ast:

thenbegin

A.Il" [Z I :- List", [X] ;'X c X ,._ 1

en de~..ebegin

Au " [Z I:~ Lista !'ll;3 4 5 6 9 y :~ Y + 1and;

Z : : : : : : ; Z + 1Primero Ultimo endii

vat:AUK ListaEnteroslZ : integer I{ Mezc:la }

x , s ,beginX :~ Ida;

y :~ puntoCen + 1;Z :: X;{ buele para mezclar las sublistas }while C Jo t < ' " FuntoCen) and ( Y (= Deha) do

be':[in1f Lista [XI (= Lista(Y]

El procedirniento de o rd en ac t 6 n p or lIIezcla se disena can ayuda de la recursividad paradividir las l is tas y ordenar l as suhlis ras; post erior mente se l lama a un procedimientoMezcla s imi la r a l estudiado en el Capitulo 13.

{ buels para eopiar elementos restantes, si existen }while X < puntoCen dobegin

1. s f P ri ~r o


16/20

650 Programacl6n en TurbolBariand Pascal 7 La recursrVldad 651

16.10. EL PROBLEMA DE LAS TORRES DE HANOI lambien famoso problema del tiernpo necesario para llenar un tablero de ajedrez enprogresion geometrical es practicamente inimaginable 'i casi imposible, sin soluci6n re-cursiva.Veamos una solucion con Ires discos y luego decidiremos por induecion la solucionpara /I discos (Fig. 16,5).

Un case tipieo de resolucion de un problema con un metodo recursive es el juego denines conocido como Torres de Hanoi (segun leyendas inventado en Laaot igua eiv il iza-cion tibetana).

Definicion del problemaSe dispone de t res pastes (1, 2 , 3) con soportes de madera (varil las de alambre 0similar)y un juego de discos de diferentes tamanos (el numero de ellos se lee ra en el program aprincipal) que se sinlan en el primer pes te . EJ disco de mayor tamai 'lo (diametro) sesituaen el fonda y e l mas pequeno en la parte superior. EI j uego consiste en mover los discosde l peste I aJ peste 3 de acuerdo a las siguientes reglas:

Algoritmo (3 discos)'. Mover dos (3 - I) discos desde el paste I basta el paste 2. Mover el disco m a s grande desde e1paste) hasta el peste 3. Mover los des discos desde el peste 2 hasta el paste 3 utilizando el paste I.

l. Solo un disco se puede mover a 1av ez.2, Un disco nunca puede estar encirna de otro disco con un diametro mas pe-queno.3. Un disco siempre debe estar en uno de los pastes (excepto cuando se este mo-viendo).

Algoritmo (n discos) Mover /1-I discos desde 1 basta el 2 utilizando el paste 3. Mover el disco restante desde Lhasta el 3. Mover La terre de n - I d iscos desde el peste 2 has ta elpaste 3 uti li zando el poste 1.Este modele de solucion es recursive.

AnalisisEl problema a prirnera vista parece s imple, perc su solucion esfrancamente di fic il y solola solucion recursiva facili ta la resolucion. Tres, euatro discos son imaginables , 64 ( lasleyendas citan esta cifra como la propuesta de un rey tibetano a sus subdi tos , al esti lo del

p ro gr am H an oi ;typePoste 1 .3;

Pos 1 ..Maxint;varN um Di scoB : P os ;

I~ ~Siluaci6nfnicial

I II II II I

procedure MoverTorre (N , pos; Uno, Dos, Treep ro ce du z; e H ov ar D i s< :: oIe ed e, H a, et .a ;P os te ) ;beginwrite ('mover 'un disco deede e1 poste

WritaLn (' hast .. el poste ',basta :1)end;

p os tel ;

desde :1);

Posle 1 Posts 2 PosIs3

( Sil:lJaci6nfinslI I1 I1 Ir I

PO. Sle , Posre2 Posre 3Figura 16.4 . Torres de Hanoi .

begini.fNolthen MoverOieco (Uno. Tres)

elsebegin!1overTorre IN - 1, Uno, Tree, DDS);

M ov erO isc o (U no, T re s);MoverTorre (N - 1, Dos, uno, Tres)

en dend;{ progrAma principal }beqinWriteLn ('introduzca numero de discos en juego ')1

R ea dL n ( NU mD is co s, )IWt"ite C IPa._ra " N"um.Ciscoa ~.1, I discos');W r i t:e Ln (' lo s mo vim ie n tOB sucasl voa son: ');MoverTorre (NumDiSCOS, 1, 2, 3 )

end.


17/20

652 Progrsmi1ci6n fin Turbo/Bor land Pasca l 7

2

2

La rewrsividad 6533 Ejecuci6nMover dos d.scosalpaste 2 introdu:!;ca de discos en ju.egoumaro

4Para 4 discos l o s m o vi m ia n to s auces.ivos son;mover un disco desde e1 poste 1hasta a 1 p os te 23 r b mover un disco desde e1 p os ts 1 hasta a l p os te 3mover un disco deede e1 poate 2 hasta a1 poste 3mo. . .er un disco desde al poste 1hasta ..1 post" 2mover un disco dead" a1 poate 3 hasta e1 poste 1mover un disco desde e1 poste J hasta 91 poste :2mover un disco deade 81 poste 1 hasta a1 poste 2

3 r b mov ..r un di sco d as de . .1 p os ta 1 hasta e1 poete 3mover un disco deede e1 poste 2 basta 81 posta 3mover un d~sco desde a1 poste 2 hasta el p os t . . 1mover un disco desde a1 poste 3 hasta e 1 p os te 1mover un d is co desde 81 poste 2 hasta eL poste 3mover un d is co d ee de el poste 1hasta e1 posta 23 mover un disco deede el paste 1 I;asta e 1 p os te 3MOIIIJrdisco mover un d is co desae e1 poete 2 hast a e1 poste 3grande de! POSts, a/pnsle3

Anal isis de tss Torres de Hanoi3 E[ nurnero de movimien tos H(n) para una terre de n discos, se calcula asf:

2

Mover dos discosde/pasrs 28/ poste 3 H(l} 1Hln) 5 1 + 2 H ( n - l ) (n> 1)

2

2

2

con [0 que se puede deducir

2

3

Para una terre de 4 discos los movimientos son 15 y para una terre de 64 discoses 260 1 - I ee 1019 (lSituaciOn inirnaginablel).En este problema el g ran numero de mov imientos de disco se produce par el p rob le-ma en si y no POT la recu rsiv idad como sucedia en la version recursiva de Fibonacci.

H(n} - 2"-1 pare n>- 1

316.11. RECURSEONMUTUA

:3

La recursion mutua es aquel la propiedad en Ia Que un p ro gr am a c on ti en e dos procedi-mientos PI y P2 t ales que cada un o de CUDS incluye una Ilamada aJ otro, En eJ C'3S0 deTurbo Pascal serequiere que uno de los procedirnientos tenga una deelaracion f o rw a rd . .Una apl icacion pnict ica que contiene recursion mutua es TestRecMutua.p r og r am T e st ; Re c Mu t u . .;{Contiene 105 p ro ced imi en to s r acu rsi vo s L ee r y recnazar}va r

Rasp: char;igura 16.5. Movimientos sucesivos de las Torres de Hanoi In = 3).


18/20

654 ProgramBcion en TutDo/Borl~nd Pascal 7 Li I r!!Curslvidad 655procedure Recha-zar (v,!l .rResp , char); forward:[visualiza u.n mensaJE!de re spues ta no aceptahle y l.Lamadaa1procedimi'ento Leer)

l . Eo primer lugar , no utilice millen la recursividad, a menos que tenga un mediopara terminar las ll amadas recursivas, EIprogramador debe tener la seguridad deque en los datos uti lizados existe aI rnenos uno Que cumpla la condicion de termi-nacion.2. Si un proceso se puede definir en terminos mas simples en Iuncion del mismo,como es el caso de sumas, factoriales, etc ., se debe cons iderar la recursividad.3 . EI numero de pasos de un programa se puede reducir eonsiderablemente ut ili zan-do un proceso recursive, De igual modo, el disei'lo del program!'! se puede simplifi-car considerablemente. Exis ten problemas en los cuales la solucion recursiva es laidenea: por ejemplo. el problema de las Torres de Hanoi 0 el recorrido de arboles(Capitulo (7).4. Cada Ilamada recursiva requiere la asignacicn de espacio de memoria (en la pita )para todas las var iables locales, parametres valor y la direccion de retorno. Portanto, cada llarnada uti liza memoria, y siexisten limitaciones en memoria central ,esto puede suponer una seria lirnitacion,5. Si no existe una ventaja clara para uiiliza r recursividad, no la utilice , Por el con-trario, si la definicion del problema es inberentemente recursiva, entonces Lasolu-cion recursiva debe ser eonsiderada preferentemente,6. Si en un proceso las sucesivas llamadas a un procedirniento suponen guardarvaJores de variables en cada etapa, que poste riormenre deben ser procesados enorden inverse, es aplicable en eSi:OScases, normalmente, la recursividad, La razcnes la semejanza del probLema con Ja definicion de una pi la ,

procedure Leer (vax .Resp , char);(Fija 81 valor de Resp a'S' 0'N' dependieodo de 10 que elu5uario escribe. Repite el proceso hasta que ..1 usuarioteclea uno de Los dos caracteres. Es recursivo mutuamentecon Rechazar)beginWriteLn ( '5 para 5i 0 N para 'NIIReadLn (Resp),if not ( Res p i n ['S','N'I thenRectla"ar (Resp).

end,;procedure Rechazar (va.r ReS'p , char);beginWri teLn (rasp, 'no es una re spuesta acep table');Leer (ReSp);

end;be9i~ {programa}WriteLn ('Esto es una prueba);Leer (Resp);WriteLn ('1 valor de Resp es', Resp);WriteLn ('F in de 1a prusba ');

end. '6.13 PUESTA A PUNTO DE PROGR.AMASUna salida de Ja ejecucicn de este program a es

Esto eS una prueba5 para S1 0N para NoTecnicas de programaci6n

Las funciones y procedimientos reeursivos se pueden ut il izar cuando los datos delproblema estan organizados en una estructura de datos que se define recursive-mente. Si un algoritmo no recursive se puede obtener y es menos complejo que elrecursive, es normalmente mejor ut il izar Javersion no recursiva .. Cuando se escriben proeedimientos 0 f un c io ne s r e cu rs iv a s, s e deben verificar siem-pre para comprobar que el procedlmiento no produce recursion infin ita , El problema mas frecueme con un procedimiento/funcion recursiva es que puedeno te rm in ar a de cu ad am e nte , P or ejemplo , si 1acondicion de termination no escorreeta 0 incompleta, e n to nc e s e l p r oc e dim ie n to puede llamarse a sf mismo inde-finidamente 0bien basta que se gas te toda la memoria disponible. Un error en tiempo de ejecucion (Slack ove!jlow) indica que no se ha terminado elprocedimiento recursivo. Asegurarse de que cada posible ease de recursion tiene una condicion de termi-nacion.

sno e9 una respuesta aceptableS para Si 0N para NoVistoV no es una respuesta aceptable5 para ai o N para ,"0SEl valor de Resp es 5Fin de 1a prueba

'16.12. LA RECURSIVIDAD, PROS Y CONTRAS (SINTESIS)unque en Inseccion r 6.5 se han analizado va las ventajas e inconvenientes de IIIrecur-sividad frenre a Ia iteracion, sintetizamos en-este apartado los conceptos fundarnentales

'I describi rernos nuevamente los pros Y contras de esa potente herrarnienta l larnadarecursiv idad, jumo con pautas para la eleccion adeeuada del metodo recursive 0 reite-rarivo.


19/20

656 ProgramBclon en Turbo/Sorland Pascal 7 La ntCUrsividlld 657RESUMEN 6 . iC ual es III s al id a d e l s ig u ie rn e p ro g ra m a?La recursividad es una herrami enta de programacion muy potente qu e puede u ti li za r TurboPascal: es II I propiedad por 1 3 oual un subprcgrama puede llarnarse a si misrno para realizar unata re a, T u rb o P as ca l p er m ir e ~ I d is en o d e p ro ce dir ni en to s y f unci cne s r ec u rs ivo s .

La tecnica recursiva es de di ffel I conce]plUali .z8ci6n, Sin embargo, un alBorilmo recursi vo seesc ribe con un codigo mas simple y corte que so equiva l ent e r epe t it ivo, Por ejemplo, compare losa lg o ri tm o s d e ord'enaci6n rapida y b us qu ed a b in ar ia e n a m bo s meiodos.EI usa correcto de la recursividad debe ser considerado co n detenirniento, En c asode utilizar lar ec ur si on , e l programador d eb e te ne r sumo cuidado de ineluir, en su cod igo, condic iones determinacidn II fin de d e te n er l as l la m ad as r ee ur si va s, Si n o e s a st , f .i ci lm e m e s e c oe vi er te en unbucle infinito.

program Demox;p ro ce du re C ue nt a ( Nbeginif N ~ 1

thenWriteLn ('Hurtado')elsebegi.n

integer)

EJERCICIOS

W rI te ( 'v os ') ;Cuenta {N - 11en dend; {Cllenta}begin {Demol()C uenta ( 3)end1. D is eiia r u na f un cio n re cu rs iv a q ue p err nita rn ultip lic ar d os n urn er os :n 1er os m y n. 7 . E scrib ir u na funci6n recursive que calcu le la palencia de emeros:

2 . E nc on tr ar lo s e rro re s d e l a s ig uie nle d ef in ic io n de funcion recursive: x " (x ; real. n : emero)program Ejemplo_Recursividad;functi.on recur ,(a_,;X : integer);begin

if " = O}beginil n = 0t he n F lo r := n * F lor ( 0- 1)end;

3 . D esc rib e el algorilmo QuickSon para los ruimeros46 2 3 35 6 8 1 3 46 23 56 4 0

begin {EjercicioTeat}Write!,n (Flor (411e nd , { Ej er cl ci oT es t}4. Escribir Is s funciones, un a recursiva y otra no recursiva,.a J q u e d ado el enteropositive xdevuelva true ( ve rd ad er o) S I y $ 6 1 0 s i x es u na p oten cia d e 2 . 9. Disenar un programa que ealcule recursivamcnte la suma de /II numerus enteros.

5. ~Qul! haec la s iguiente funcion? 1 0. E serib ir u n p ro gra ma rec ursiv e q ue c alc ule L as um a d e lo s N p ri m er os n um er os n a tu ra le s.

function M d ( Num i, N um 2 , R ang oEnt){ RangoEnt as del tipo ~ ..Maxint }begi..uII Num1


20/20

658 PrograrmJcl6n en TurbojBor/and Pascal 7 La fecurSIVldad 659

m!C(m, 1 1) ~ On, n - ----n! (m -II)!

13, Escribi r un orocedimier no recurs ive que ef ecule Ia c las ifi cacion por inser cion de una l is ta denurner os enteros en ar den dec rec ie rue, E I a lgor itmc uti li zado es : buscar e l e le rnento mi ls pequeno y s iruarlo en primers posicion; c la si fi ca r e l r es to de la lista,

4, E s cr ib ir u n a f un c io n r ec ur si ve que calcule elm. II):el nurnero de comblnaciones de IIIelernen.ros tornados en n,

5. Escribir lin subprograma recursive que liste todos los pares de enteros posi tives que son lasuma de un numero dado, POT ejemplo:

I~, Situar echo r einas sobre un tab le ro de a jedrez de modo que ninguna pueda se t amenezada poratm.

7 g 6 + I, 5 + 2, 4 + 3(no se pueden repetir las parejas 6 + I y 1+ 6)

15. Esc ribi r un procedi rmento recursive que perrn it a invert ir una cadena de caracteres ('Moni mer ' _ 'remitron') .1 6, E scrib ir u n programa r ec ur si ve Q u e p er rn it a c on ta r l as p ala br as d e u na f ra se .

6 . Esc ribi r un proced ir nien to recursive que determine el cap ital Co obtenido , s ituando e l eap i-ta l C o a im e re s c om p ue st o durante /I ados a l i n te r es anual r (expresado en porcentaje],C1 = Co. (I + ,/100)C~ C (L +,/100) F or mu la d e.! itller2sCampUlJslO

Co =C v (I + r / I O O )PC"-C,,.,",(I +r/IOO)7, Realizar un subprograma recursive que perrnita el calculo de la funcion de AckermanA(m. II):

{

111 IA(m, nl A(m-I.l)A(m - I,A(m.lli - I)

parnparapara

111=0lI~Om > 0, n > 0 'f entero8. Escribir W pregrarna Que lIame a una funcion recursive para encontrar lasuma de los enteros

pares basta N.Suma pares = 2 + 4 + . .. + {N - 1) + N

9. Encontrar una formul a para el mimero de veces que un anillo se transfiere de un alambre alOtIO en In Torre de Hanoi con it ani flos . Calcu la r e l valor pam n = 5, 10 Y20.

JO. Escribir un subprograma que liste i edos los pares de subconjuntos de un conjunto dado deleiras. Por ejemplo:['M', 'P', 'R', 'r]- I'M', 'P']. I'M', 'R'],

['M', ' T ' J ,['P', 'R'), ['1", T].,['R','T']

I L Realizar una funcion que produzca la surna de los dfgilr;s de la repre sentacion dec ima l de unvalor entero no negativo,12. Construir una Iuncicn que produzca la imagen espejo de una cadena de caraeteres ('12345' se

transforma en '53,421') . Resolver este problema mediante las funciones de cadenas copy Ylength.

Date post:	08-Jul-2015
Category:	Documents
Upload:	pipo-garcia
View:	90 times
Download:	0 times

recursividad

Documents