Coceptos importantes

Materia: Estructura de Datos

Trabajo:
Investigación de Estructura de Datos Conceptos Importantes

Ingeniería en Sistemas Computacionales

INTRODUCCION

Esta investigación fue realizada de las unidades 4, 5, 6, 7, y 8 que llevan por nombre, Recursividad, Estructuras no lineales estáticas y dinámicas, Algoritmos Ordenamiento por Intercambio, Algoritmos Ordenación Externa y Métodos debúsqueda, también englobamos sus respectivos subtemas.
Presentamos conceptos importantes dentro de la estructura de datos, también ejemplos teóricos y gráficos de algunos temas para facilitar el entendimiento y razonamiento de los mismos.

UNIDAD IV RECURSIVIDAD.

Definición de Recursividad.

* La recursividad es una técnica de programación importante. Se utiliza para realizar unallamada a una función desde la misma función. Como ejemplo útil se puede presentar el cálculo de nú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.

* Se dice que una función es recursiva cuando sedefine en función de si misma. No todas la funciones pueden llamarse a si mismas, deben estar diseñadas especialmente para que sean recursivas, de otro modo podrían conducir a bucles infinitos, o a que el programa termine inadecuadamente.

Ejemplos.

* En los programas de televisión en los cuales un periodista transfiere el control a otro periodista que se encuentra en otraciudad, y este hace lo propio de un tercero.

* La Matrushka es una artesanía tradicional rusa. Es una muñeca de madera que contiene otra muñeca más pequeña dentro de sí. Esta muñeca, también contiene otra muñeca dentro. Y así, una dentro de otra.

Nos encontramos en un gran apartamento y estamos buscando a una persona. Para encontrarla realizamos una acción (abrir la puerta de unahabitación) para comprobar si está dentro esa persona. Ocurre que dentro de esa misma habitación pueden haber varias habitaciones más (baño y cocina por ejemplo) y a su vez, dentro de la cocina un trastero. Así pues, una vez entrado en la primera habitación mencionada y no encontrar a la persona que buscamos, nos meteremos en la cocina y si no está, buscaremos en el trastero.
Aprovechando ya este ejemplodesarrollado, en el caso de que tampoco encontraremos a la persona en el trastero, deberíamos retroceder hasta encontrar una habitación anterior que posea una habitación -valga la «redundancia»- en la que aún no hayamos mirado, y así sucesivamente. A esto último se le denomina Backtracking (Volver atrás).
CLASIFICACION DE LA RECURSIVIDAD.
Un subprograma que se llama así misma se dice quees recursivo. La recursión en los subprogramas puede darse de dos maneras diferentes:
1. DIRECTA: el subprograma se llama directamente así mismo. Por ejemplo, observe el lector que en la figura 4.1p es un subprograma y en alguna parte de el aparece una llamada así mismo.
2. INDIRECTA: el subprograma llama a otro subprograma, y este a su vez llama al primero . Porejemplo, en la figura 4.2ª el subprograma p llama al subprograma Q y este a su vez invoca al primero ; es decir el control regresa a p. También se da la recursión indirecta cuando subprograma llama a otro y este a un tercero. Una vez ejecutado, el control regresa al subprograma lo llamo ; lo mismo sucede en todos los niveles. Por ejemplo, en la figura 4.2b el subprograma pllama al subprograma Q, y este llama al subprograma b. cuando b concluye, el control regresa a Q, y al terminar este, el control se transfiere a p.
Llamada a P
Subprograma p

Llamada a P
Subprograma p

PROCEDIMIENTO RECURSIVO.
* 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...