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 -