Estructura de Datos II
Lsi. Tanya Ruano A., MBA
Recursividad
Facilitador:
Lsi. Tanya Ruano Almeida, MBA
Introduccin
Se debe aclarar decir que la recursividad no es una estructura
de datos, sino que es una tcnica de programacin que nos
permite que un bloque de instrucciones se ejecute n veces.
Remplaza en ocasiones a estructuras repetitivas.
Este concepto ser de gran utilidad para el captulo de la
estructura de datos tipo rbol.
La recursividad es un concepto difcil de entender en principio,
pero luego de analizar diferentes problemas aparecen puntos
comunes.
En Java los mtodos pueden llamarse a s mismos. Si dentro
de un mtodo existe la llamada a s mismo decimos que el
mtodo es recursivo.
Lsi. Tanya Ruano A., MBA
Introduccin
Cuando un mtodo se llama a s mismo, se asigna espacio en
la pila para las nuevas variables locales y parmetros.
Al volver de una llamada recursiva, se recuperan de la pila las
variables locales y los parmetros antiguos y la ejecucin se
reanuda en el punto de la llamada al mtodo.
Lsi. Tanya Ruano A., MBA
Introduccin
La funcin repetir es recursiva porque dentro de la funcin se
llama a s misma. Cuando ejecuta este programa se
bloquear y generar una excepcin: "Exception in thread
"main" java.lang.StackOverflowError.
Funciona: Primero se ejecuta la funcin main, luego de crear
un
objeto
llamamos
a
la
funcin
repetir.
Hay que tener en cuenta que cada vez que se llama a una
funcin se reservan 4 bytes de la memoria que se liberarn
cuando finalice su ejecucin.
La primera lnea de la funcin llama a la funcin repetir, es
decir que se reservan 4 bytes nuevamente. Se ejecuta
nuevamente una instancia de la funcin repetir y as
sucesivamente hasta que la pila esttica se colme y se
cuelgue el programa.
Lsi. Tanya Ruano A., MBA
Taller
Problema 2: Implementacin de un mtodo recursivo que
reciba un parmetro de tipo entero y luego llame en forma
recursiva con el valor del parmetro menos 1.
Lsi. Tanya Ruano A., MBA
Taller
Problema 3: Implementar un mtodo recursivo que imprima en
forma descendente de 5 a 1 de uno en uno.
Lsi. Tanya Ruano A., MBA
Taller
Problema 4: Imprimir los nmeros de 1 a 5 en pantalla
utilizando recursividad.
Lsi. Tanya Ruano A., MBA
Taller
Por qu? Problema 4:
En la primera llamada desde la funcin main el parmetro x
recibe el valor 5.
Cuando llamamos desde la misma funcin le enviamos el
valor de x menos 1 y la memoria queda de la siguiente forma:
Lsi. Tanya Ruano A., MBA
Taller
Problema 5: Otro problema tpico que se presenta para
analizar la recursividad es el obtener el factorial de un
nmero.
El factorial de un nmero es el resultado que se obtiene de
multiplicar dicho nmero por el anterior y as sucesivamente
hasta llegar a uno.
Ej. el factorial de 4 es 4 * 3 * 2 * 1 es decir 24.
Lsi. Tanya Ruano A., MBA
Taller
Solucin al Problema 5:
Lsi. Tanya Ruano A., MBA
Deberes
Problema 6: Programar un algoritmo recursivo que calcule un
nmero de la serie Fibonacci.
Problema 7: Programar un algoritmo recursivo que permita
hacer la divisin por restas sucesivas.
Problema 8: Programar un algoritmo recursivo que permita
invertir un nmero. Ejemplo: Entrada: 123 Salida: 321
Problema 9: Programar un algoritmo recursivo que permita
sumar los dgitos de un nmero. Ejemplo: Entrada: 123
Resultado:6
Problema 10: . Programar un algoritmo recursivo que permita
sumar los elementos de un vector.
Problema 11: Programar un algoritmo recursivo que permita
hacer una multiplicacin, utilizando el mtodo Ruso.
Lsi. Tanya Ruano A., MBA
Tipos de Recursividad
Recursividad simple: aquella en cuya definicin slo aparece
una llamada recursiva. Se puede transformar con facilidad en
algoritmos iterativos.
Recursividad mltiple: Se da cuando hay ms de una llamada
a s misma dentro del cuerpo de la funcin, resultando ms
difcil de hacer de forma iterativa. Un ejemplo tpico es la
funcin de Fibonacci.
Recursividad anidada: En algunos de los argumentos de la
llamada recursiva hay una nueva llamada a s misma.
Recursividad cruzada o indirecta: Son algoritmos donde una
funcin provoca una llamada a s misma de forma indirecta, a
travs de otras funciones.
Lsi. Tanya Ruano A., MBA
Preguntas
Lsi. Tanya Ruano A., MBA
