7/21/2019 3. Recursividad.docx

1/12

CURSO : Algoritmo y Estructura de Datos II

DOCENTE : ERCE

Tema: Recursividad

Un ejemplo paradigmtico seria el del tringulo de Sierpinski en el que cadatriangulo est compuesto de otro ms pequeos, compuestos a su vez de lamisma estructura recursiva (de

Hecho en este caso se trata de una estructura fractal)

1. Definicin:

Consiste en la definicin de algo (una propiedad, una operacin, un procedimiento o unafuncin) en trminos de s mismo

2. Algoritmos Recursivos!n algoritmo se dice "ue es recursivo cuando tiene la capacidad de llamarse o in#ocarse

a s mismo o de llamar a otro algoritmo desde el cual se puede #ol#er a in#ocar al primero

Caractersticas:

- El n$mero de llamadas recursi#as "ue se reali%an es finito (es decir, en alg$nmomento DE&E finali%ar la e'ecucin del algoritmo)

Facultad de Ingeniera y Arquitectura Seminario

7/21/2019 3. Recursividad.docx

2/12

- Cada llamada recursi#a resuel#e un prolema de menor tamao, uno tras otro,*asta llegar a un prolema cuya resolucin sea directa o conocida

Tcnic !lic":

+a tcnica "ue se aplica para definir la solucin recursi#a de prolemas se conoce comodivide y vencersy se trata de resol#er un prolema mediante su descomposicin en#arios suprolemas similares al original (o del mismo tipo) pero con datos mspe"ueos

Si un !ro#lem !ue"e su#"ivi"irse en su#!ro#lems similres$ entonces el mismo!roceso !ue"e ser !lic"o c" uno "e los su#!ro#lems %st &ue se !ue"

encontrr un solucin "irect o conoci". 'inlmente se com#inn ls soluciones"e los su#!ro#lems !r !ro"ucir l solucin finl "el !ro#lem originl.

(. An)lisis "e los lgoritmos * !rogrms:

+os !rogrms recursivos ten"r)n csi siem!re l siguiente estructur:

- Avnce- Con"icin "e !r"-

,rocesmiento

+a organi%acin de un programa de funcin recursi#a sera:

func!(")#

"func!(")$"

%

E'm: Anali%a los siguientes casos:

a) Deducir la definicin recursi#a del producto de n$meros naturales:

7/21/2019 3. Recursividad.docx

3/12

solucin iterati#a

a - . a / a / a / a/ 0 a

#eces

solucin recursi#a

a - . a si: .1

a - . a - (21)/a si: 31

E'm:

4ultiplicar 5 - 6 de forma recursi#a

7olucin:

5 - 6. 5 - 8 / 5 . 5 - 1 / 5 / 5 . 5 / 5 / 5 . 89

E'ercicios:

4ultiplicar los siguientes n$meros de forma recursi#a:

a) - 9) 1; - 5c) < - =d) 8 - e) > - 6f) 18 -