“Tecnología en desarrollo
De Sistemas de información y de software”
INTEGRANTES:
Oscar David Fonseca Pérez
CC: 1041971066 - CEL: 3046413008
Juan Camilo Castellanos Vega
CC: 1043295018 - CEL: 3207389394
Camilo Andrés Contreras Martínez
CC: 1007975567 - CEL: No registra
DOCENTE:
Cesar Gómez ---------------------- Estructura de Daros
CORPORACION UNIVERSITARIA RAFAEL NUÑEZ
Cartagena de Indias, D. T. y C.
Conceptos
• Recursividad
• Ventajas y desventajas
Ejemplos teóricos
----------------------- El Triángulo de Sierpinski
----------------------- Problema de Fibonacci.
• Métodos recursivos
• Tipos de recursividad
----------------------- Recursividad directa
----------------------- Recursividad indirecta
• Resolución de problemas usando recursividad
• Ejemplos
Recursividad
Es una forma de especificar un proceso basado en su propia
definición. Un algoritmo recursivo es un algoritmo que expresa la
solución de un problema en
términos de una llamada a sí mismo. La llamada a sí mismo se
conoce como llamada recursiva. También llamada Recurrencia o
Recursión.
La recursividad es un concepto fundamental en matemáticas y en
computación.
Es una alternativa diferente para implementar estructuras de
repetición (ciclos). Los módulos se hacen llamadas recursivas.
Se puede usar en toda situación en la cual la solución pueda ser
expresada como una secuencia de movimientos, pasos o
transformaciones gobernadas por un conjunto de reglas no
ambiguas.
La recursividad se debe usar cuando sea realmente necesaria, es
decir, cuando no exista una solución iterativa simple. subproblemas
más pequeños, generalmente del mismo tamaño, resolver los
subproblemas y entonces combinar sus soluciones para obtener la
solución del problema original.
Ventajas
La recursividad es una técnica de programación elemental
que permite que una función pueda llamarse asimismo desde
la misma función. La llamada a sí mismo se conoce como
llamada recursiva o recurrente.
Se puede utilizar la recursividad como una alternativa a la
iteración.
Mayor simplicidad del código en problemas recursivos.
Posibilidad de “marcha atrás”: back tracking.
Desventajas
El valor de la recursividad reside en el hecho de que se puede
usar para resolver problemas sin fácil solución iterativa.
La ineficiencia inherente de algunos algoritmos recursivos.
Mayor uso de la pila de memoria
Mayor tiempo en las llamadas.
Estos dos inconvenientes se pueden agravar si se pasan
estructuras de datos muy grandes por valor, ya que implica
copiar estos datos en la pila de procedimientos.
Recursividad Ejemplo teóricos
El Triángulo de Sierpinski
Un ejemplo matemático de recursividad es el estudio de
fractales, por ejemplo, el Triángulo de Sierpinski, el cual es un
objeto geométrico en el que se repite el mismo patrón a diferentes
escalas y con diferente orientación.
La expresión fractal viene del latín fractus, que significa fracturado,
roto, irregular.
Problema de Fibonacci.
Otro ejemplo típico de una función recursiva es la serie Fibonacci.
Esta serie fue concebida originalmente como modelo para el
crecimiento de una granja de conejos (multiplicación de conejos)
por el matemático italiano del siglo XVI, Fibonacci.
La serie es la siguiente:
1,1,2,3, .5.8. 13. 21. 34 ...
Esta serie crece muy rápidamente; como ejemplo. el término 15 es
610.Si divides cualquier número en la secuencia de Fibonacci por el
anterior, por ejemplo, 55/34, o 21/13, y la respuesta siempre es
cercana a 1.61803. Y es por eso que la secuencia de Fibonacci
también es conocida como la secuencia dorada, pues ese 1,61803
es lo que se conoce como el número áureo.
Métodos Recursivos
Un método (función o procedimiento) que puede
llamarse a sí mismo se llama método recursivo.
La escritura de un método recursivo es similar a la
escritura de su homónimo no recursivo.
El único requisito en un método recursivo es la
especificación de una condición de terminación
(caso base), la cual permita acabar con la
recursividad.
La recursión puede ser utilizada como una alternativa
a la repetición o estructura repetitiva.
La utilización de métodos recursivos es una
herramienta muy potente en algunas aplicaciones,
sobre todo científicas y matemáticas.
El uso de recursión es particularmente idóneo para la
solución de aquellos problemas que pueden definirse
de modo natural en términos recursivos.
Tipos de Recursividad
Directa:
Es la más común, se da cuando una función se
llama a sí misma una o varias veces.
A llamar_a A
Indirecta:
Se da cuando una función es llamada de
manera indirecta, es decir, por medio de otra función.
A llamar_a B, в llamar_a A
Ejemplos de la recursividad
Java.
1. Búsqueda binaria recursiva.
● Caso base: Si el elemento central es el buscado, el elemento
está en la posición central.
● Caso base: si el elemento central no es el buscado y la lista tiene
sólo un elemento, el elemento no está.
● Caso general: si el elemento central el mayor que el buscado, se
Universidad Pontificia de Salamanca (Campus Madrid) Luis
Rodríguez Baena, Escuela Superior de Ingeniería y Arquitectura,
2012 47
● Caso general: si el elemento central el mayor que el buscado, se
realiza una búsqueda binaria en la parte izquierda de la lista.
● Caso general: si el elemento central es menor que el buscado se
realiza una búsqueda binaria en la parte derecha de la lista.
2. Realizar la suma de los elementos de un
vector.
Caso base: si el número de elementos del vector es 1, entonces la
suma es el elemento 1.
● Si el número de elementos es mayor que uno, la suma es el
elemento n + la suma de todos los elementos menos el último.
