recursividad

Recursividad

Mariacutea Luisa Velasco Ramiacuterez

Definicioacuten

bull Cualquier proceso puede ser definido de forma iterativa y de forma recursiva ndash 1048790 Un proceso iterativo es aqueacutel que requiere

de la repeticioacuten expliacutecita de cierta accioacuten ndash 1048790 Un proceso es recursivo si estaacute definido

total o parcialmente en teacuterminos de siacute mismo

3

Ejemplo Matrushka

bull La Matrushka es una artesaniacutea tradicional rusa Es una muntildeeca de madera que contiene otra muntildeeca maacutes pequentildea dentro de siacute Esta muntildeeca tambieacuten contiene otra muntildeeca dentro Y asiacute una dentro de otra

bull Para calcular 4 por ejemplo se puede utilizar un proceso iterativo o uno recursivo

bull De manera iterativa

bull 4 = 1 2 3 4 = 24

bull Para definir 4 de manera recursiva se tiene que definirlo en teacuterminos de factorial es decir en la definicioacuten (parte derecha de la igualdad) tiene que aparecer el factorial

bull De manera recursiva

raquo4 = 4 3

bull Se observa que en el caacutelculo de 4 fue muy importante el hecho de que 0 es igual a 1 iquestQueacute hubiera pasado si 0 se calcularaacute como se calculoacute los demaacutes factoriales Nunca se hubiera terminado el proceso o sea tendriacuteamos un proceso infinito

bull Entonces toda definicioacuten recursiva debe tener al menos una definicioacuten base Esta definicioacuten base proporciona la solucioacuten de salida de la recursividad

bull Para calcular 4 3 2 y 1 Se uso una definicioacuten recursiva por lo que se estuvo entrando en recursioacuten y cuando se alcanzoacute la definicioacuten base se comenzoacute a salir de recursioacuten

10

bull Conclusiones ndash Un proceso es recursivo si estaacute definido total

o parcialmente es teacuterminos de siacute mismo ndash Todo proceso recursivo debe tener al

menos una definicioacuten base y una definicioacuten recursiva

Disentildeo e implementacioacuten de algoritmos recursivos

bull La solucioacuten recursiva a un problema de repeticioacuten se obtiene respondiendo dos preguntas ndash 1 iquestCoacutemo se resuelve el caso maacutes pequentildeo

del problema

ndash La respuesta a esta pregunta debe ser no-recursiva y plantear una condicioacuten de salida es decir proporcionar la definicioacuten base

bull En el caacutelculo de factorial la pregunta seriacutea iquestcuaacutel es el nuacutemero maacutes pequentildeo para el que se puede obtener factorial

bull 2 iquestCoacutemo se resuelve un caso general del problema sabiendo que ya se tiene el caso anterior maacutes pequentildeo

bull De tal forma que la definicioacuten recursiva de n es ndash a) n = 1 si n = 0 1048790 Definicioacuten base ndash b) n = n (n ndash 1) si n gt 0 1048790 Definicioacuten

recursiva

bull Dependiendo del problema que implemente el moacutedulo eacuteste diagrama se puede ver modificado

bull Por ejemplo si tiene maacutes de una definicioacuten base si tiene maacutes de una definicioacuten recursiva o si en la solucioacuten recursiva tiene que realizar alguna operacioacuten antes de volverse a ejecutar o no

Implementacioacuten de la funcioacuten recursiva

La importancia del return en una funcioacuten

bull 1o Hace que la funcioacuten tome el valor de lo que se estaacute regresando En factorial si n == 0 factorial = 1 sino factorial= n factorial(n ndash 1)

bull 2o Termina la ejecucioacuten de la funcioacuten regresando el control de la ejecucioacuten al moacutedulo en que fue llamada (a la instruccioacuten que se debe ejecutar despueacutes de que la funcioacuten fue llamada)

Conclusiones

bull La solucioacuten recursiva de un problema se obtiene respondiendo dos preguntas iquestcoacutemo se resuelve el caso maacutes pequentildeo y iquestcoacutemo se resuelve un caso general sabiendo que ya se tiene el caso anterior maacutes pequentildeo

bull Para implementar soluciones recursivas se utilizan los moacutedulos las funciones (int float double etc)

bull El return de una funcioacuten realiza dos operaciones asigna a la funcioacuten el valor que regresa y termina la ejecucioacuten de la misma regresando el control a la siguiente instruccioacuten que se tiene que realizar despueacutes de la llamada a la funcioacuten

Otro ejemplo

bull public static void imprimeNaturales(int n) bull bull if (n == 1) bull Systemoutprintln(ldquo1rdquo) bull else bull bull Systemoutprintln(n) bull imprimeNaturales(n ndash 1) bull _________________________________

2 bull bull public static void main(String args[]) bull bull hellip bull imprimeNaturales(5) bull Systemoutprintln(ldquoFin del procesordquo)

______ 1 bull

bull Considerar un ejemplo maacutes la serie de los nuacutemeros de Fibonacci cuya definicioacuten ya se nos da de manera recursiva Vamos a escribir su implementacioacuten y posteriormente haremos la representacioacuten de la pila ndash F0 = 1 ndash F1 = 1 ndash Fn = Fn -1 + Fn ndash 2 si n gt 1

27

iquestCuaacutendo usar recursividad

bull Para simplificar el coacutedigobull Cuando la estructura de datos es recursiva

ejemplo aacuterboles

bull Cuando los meacutetodos usen arreglos largosbull Cuando el meacutetodo cambia de manera

impredecible de camposbull Cuando las iteraciones sean la mejor opcioacuten

iquestCuaacutendo no usar recursividad

28

Algunas Definiciones

bull Cuando un procedimiento incluye una llamada a siacute mismo se conoce como recursioacuten directa

29


bull Cuando un procedimiento llama a otro procedimiento y eacuteste causa que el procedimiento original sea invocado se conoce como recursioacuten indirecta

NOTANOTA Cuando un procedimiento recursivo se llama recursivamente a si mismo varias veces para cada llamada se crean copias independientes de las variables declaradas en el procedimiento

Slide 1

Slide 2

Slide 3

Slide 4

Slide 5

Slide 6

Slide 7

Slide 8

Slide 9

Slide 10

Slide 11

Slide 12

Slide 13

Slide 14

Slide 15

Slide 16

Slide 17

Slide 18

Slide 19

Slide 20

Slide 21

Slide 22

Slide 23

Slide 24

Slide 25

Slide 26

Slide 27

Slide 28

Slide 29

Definicioacuten

bull Cualquier proceso puede ser definido de forma iterativa y de forma recursiva ndash 1048790 Un proceso iterativo es aqueacutel que requiere

de la repeticioacuten expliacutecita de cierta accioacuten ndash 1048790 Un proceso es recursivo si estaacute definido

total o parcialmente en teacuterminos de siacute mismo

3

Ejemplo Matrushka




bull 4 = 1 2 3 4 = 24



raquo4 = 4 3




10






del problema





recursiva







Conclusiones




Otro ejemplo



______ 1 bull


27







28



29




Slide 1

Slide 2

Slide 3

Slide 4

Slide 5

Slide 6

Slide 7

Slide 8

Slide 9

Slide 10

Slide 11

Slide 12

Slide 13

Slide 14

Slide 15

Slide 16

Slide 17

Slide 18

Slide 19

Slide 20

Slide 21

Slide 22

Slide 23

Slide 24

Slide 25

Slide 26

Slide 27

Slide 28

Slide 29

3

Ejemplo Matrushka




bull 4 = 1 2 3 4 = 24



raquo4 = 4 3




10






del problema





recursiva







Conclusiones




Otro ejemplo



______ 1 bull


27







28



29




Slide 1

Slide 2

Slide 3

Slide 4

Slide 5

Slide 6

Slide 7

Slide 8

Slide 9

Slide 10

Slide 11

Slide 12

Slide 13

Slide 14

Slide 15

Slide 16

Slide 17

Slide 18

Slide 19

Slide 20

Slide 21

Slide 22

Slide 23

Slide 24

Slide 25

Slide 26

Slide 27

Slide 28

Slide 29



bull 4 = 1 2 3 4 = 24



raquo4 = 4 3




10






del problema





recursiva







Conclusiones




Otro ejemplo



______ 1 bull


27







28



29




Slide 1

Slide 2

Slide 3

Slide 4

Slide 5

Slide 6

Slide 7

Slide 8

Slide 9

Slide 10

Slide 11

Slide 12

Slide 13

Slide 14

Slide 15

Slide 16

Slide 17

Slide 18

Slide 19

Slide 20

Slide 21

Slide 22

Slide 23

Slide 24

Slide 25

Slide 26

Slide 27

Slide 28

Slide 29



raquo4 = 4 3




10






del problema





recursiva







Conclusiones




Otro ejemplo



______ 1 bull


27







28



29




Slide 1

Slide 2

Slide 3

Slide 4

Slide 5

Slide 6

Slide 7

Slide 8

Slide 9

Slide 10

Slide 11

Slide 12

Slide 13

Slide 14

Slide 15

Slide 16

Slide 17

Slide 18

Slide 19

Slide 20

Slide 21

Slide 22

Slide 23

Slide 24

Slide 25

Slide 26

Slide 27

Slide 28

Slide 29




10






del problema





recursiva







Conclusiones




Otro ejemplo



______ 1 bull


27







28



29




Slide 1

Slide 2

Slide 3

Slide 4

Slide 5

Slide 6

Slide 7

Slide 8

Slide 9

Slide 10

Slide 11

Slide 12

Slide 13

Slide 14

Slide 15

Slide 16

Slide 17

Slide 18

Slide 19

Slide 20

Slide 21

Slide 22

Slide 23

Slide 24

Slide 25

Slide 26

Slide 27

Slide 28

Slide 29






del problema





recursiva







Conclusiones




Otro ejemplo



______ 1 bull


27







28



29




Slide 1

Slide 2

Slide 3

Slide 4

Slide 5

Slide 6

Slide 7

Slide 8

Slide 9

Slide 10

Slide 11

Slide 12

Slide 13

Slide 14

Slide 15

Slide 16

Slide 17

Slide 18

Slide 19

Slide 20

Slide 21

Slide 22

Slide 23

Slide 24

Slide 25

Slide 26

Slide 27

Slide 28

Slide 29




recursiva







Conclusiones




Otro ejemplo



______ 1 bull


27







28



29




Slide 1

Slide 2

Slide 3

Slide 4

Slide 5

Slide 6

Slide 7

Slide 8

Slide 9

Slide 10

Slide 11

Slide 12

Slide 13

Slide 14

Slide 15

Slide 16

Slide 17

Slide 18

Slide 19

Slide 20

Slide 21

Slide 22

Slide 23

Slide 24

Slide 25

Slide 26

Slide 27

Slide 28

Slide 29







Conclusiones




Otro ejemplo



______ 1 bull


27







28



29




Slide 1

Slide 2

Slide 3

Slide 4

Slide 5

Slide 6

Slide 7

Slide 8

Slide 9

Slide 10

Slide 11

Slide 12

Slide 13

Slide 14

Slide 15

Slide 16

Slide 17

Slide 18

Slide 19

Slide 20

Slide 21

Slide 22

Slide 23

Slide 24

Slide 25

Slide 26

Slide 27

Slide 28

Slide 29


Otro ejemplo



______ 1 bull


27







28



29




Slide 1

Slide 2

Slide 3

Slide 4

Slide 5

Slide 6

Slide 7

Slide 8

Slide 9

Slide 10

Slide 11

Slide 12

Slide 13

Slide 14

Slide 15

Slide 16

Slide 17

Slide 18

Slide 19

Slide 20

Slide 21

Slide 22

Slide 23

Slide 24

Slide 25

Slide 26

Slide 27

Slide 28

Slide 29


27







28



29




Slide 1

Slide 2

Slide 3

Slide 4

Slide 5

Slide 6

Slide 7

Slide 8

Slide 9

Slide 10

Slide 11

Slide 12

Slide 13

Slide 14

Slide 15

Slide 16

Slide 17

Slide 18

Slide 19

Slide 20

Slide 21

Slide 22

Slide 23

Slide 24

Slide 25

Slide 26

Slide 27

Slide 28

Slide 29

28



29




Slide 1

Slide 2

Slide 3

Slide 4

Slide 5

Slide 6

Slide 7

Slide 8

Slide 9

Slide 10

Slide 11

Slide 12

Slide 13

Slide 14

Slide 15

Slide 16

Slide 17

Slide 18

Slide 19

Slide 20

Slide 21

Slide 22

Slide 23

Slide 24

Slide 25

Slide 26

Slide 27

Slide 28

Slide 29

29




Slide 1

Slide 2

Slide 3

Slide 4

Slide 5

Slide 6

Slide 7

Slide 8

Slide 9

Slide 10

Slide 11

Slide 12

Slide 13

Slide 14

Slide 15

Slide 16

Slide 17

Slide 18

Slide 19

Slide 20

Slide 21

Slide 22

Slide 23

Slide 24

Slide 25

Slide 26

Slide 27

Slide 28

Slide 29

recursividad

Documents