Estructura De Datos

INSTITUTO TECNOLOGICO SUPERIOR DE ALVARADO
CAMPUS LERDO DE TEJADA

INGENIERIA: SISTEMAS COMPUTACIONALES
MATERIA
ESTRUCTURA DE DATOS
TEMA
RECURSIVIDAD
SEMESTRE- GRUPO
3A
PRESENTA
REYNA DEL R. GOMEZ ESPINOSA
RAUL CARVALLO ORTIZ
Avelino ruiz guatemalaDOCENTE
ALFONSO ROJAS ESCOBEDO

H. Y G. ALVARADO, VER. AGOSTO–DICIEMBRE 2012

INDICE

Unidad 2

2 . -Recursividad
2.1 -Definición
2.2 -Procedimientos recursivos
2.3 -Ejemplos de casos recursivos

INTRODUCCION

El área de la programación es muy amplia y con muchos detalles. Los programadores necesitan ser capaces de resolver todos los problemas que se les presentea través del computador aun cuando en el lenguaje que utilizan no haya una manera directa de resolver los problemas. En el lenguaje de programación C, así como en otros lenguajes de programación, se puede aplicar una técnica que se le dio el nombre de recursividad por su funcionalidad. Esta técnica es utilizada en la programación estructurada para resolver problemas que tengan que ver con elfactorial de un número,o juegos de lógica. Las asignaciones de memoria pueden ser dinámicas o estáticas y hay diferencias entre estas dos y se pueden aplicar las dos en un programa cualquiera.

2.-Recursividad:
La recursividad es una técnica de programación importante. Se utiliza para realizar una llamada a una función desde la misma función. Como ejemplo útil se puede presentar el cálculo denúmeros factoriales. Él factorial de 0 es, por definición, 1. Los factoriales de números mayores se calculan mediante la multiplicación de 1 * 2 * ..., incrementando el número de 1 en 1 hasta llegar al número para el que se está calculando el factorial.
El siguiente párrafo muestra una función, expresada con palabras, que calcula un factorial.
"Si el número es menor que cero, se rechaza. Si no es unentero, se redondea al siguiente entero. Si el número es cero, su factorial es uno. Si el número es mayor que cero, se multiplica por él factorial del número menor inmediato."
Para calcular el factorial de cualquier número mayor que cero hay que calcular como mínimo el factorial de otro número. La función que se utiliza es la función en la que se encuentra en estos momentos, esta función debellamarse a sí misma para el número menor inmediato, para poder ejecutarse en el número actual. Esto es un ejemplo de recursividad.
La recursividad y la iteración (ejecución en bucle) están muy relacionadas, cualquier acción que pueda realizarse con la recursividad puede realizarse con iteración y viceversa. Normalmente, un cálculo determinado se prestará a una técnica u otra, sólo necesita elegir elenfoque más natural o con el que se sienta más cómodo.
Claramente, esta técnica puede constituir un modo de meterse en problemas. Es fácil crear una función recursiva que no llegue a devolver nunca un resultado definitivo y no pueda llegar a un punto de finalización. Este tipo de recursividad hace que el sistema ejecute lo que se conoce como bucle "infinito".
Para entender mejor lo que enrealidad es el concepto de recursión veamos un poco lo referente a la secuencia de Fibonacci.
Principalmente habría que aclarar que es un ejemplo menos familiar que el del factorial, que consiste en la secuencia de enteros.
0,1,1,2,3,5,8,13,21,34,...,
Cada elemento en esta secuencia es la suma de los precedentes (por ejemplo 0 + 1 = 0, 1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, ...) sean fib(0) = 0, fib (1) = 1y así sucesivamente, entonces puede definirse la secuencia de Fibonacci mediante la definición recursiva (define un objeto en términos de un caso mas simple de si mismo):
fib (n) = n if n = = 0 or n = = 1
fib (n) = fib (n - 2) + fib (n - 1) if n >= 2
Por ejemplo, para calcular fib (6), puede aplicarse la definición de manera recursiva para obtener:
Fib (6) = fib (4) + fib (5) = fib (2)...