abstraccion de datos

UNIVERSIDAD DE ORIENTE
NÚCLEO DE ANZOÁTEGUI
EXTENSIÓN REGIÓN CENTRO-SUR
ANACO-ESTADO ANZOÁTEGUI









PROFESORA:
BACHILLERES:
Dulmar Tovar
Báez Raquel
CI.18594653
Meneses,Guillermo
CI.24601631
Rojas Katherine
CI. 18909732INTRODUCCIÓN
Los programas que hemos visto hasta ahora están estructurados generalmente como métodos que se llaman entre sí, de una manera disciplinada y jerárquica. Sin embargo, para algunos problemas es conveniente hacer que un método se llame a sí mismo. Dicho método se conoce como método recursivo; este método se puede llamar en forma directa o indirecta a través de otro método. La recursividad esun tema importante, que puede tratarse de manera extensa en los cursos de ciencias computacionales de nivel superior. En este capítulo consideraremos la recursividad en forma conceptual, y después presentaremos varios programas que contienen métodos recursivos.
CONCEPTOS DE RECURSIVIDAD
Los métodos para solucionar problemas recursivos tienen varios elementos en común. Cuando se hace una llamadaa un método recursivo para resolver un problema, el método en realidad es capaz de resolver sólo el (los) caso(s) más simple(s), o caso(s) base. Si se hace la llamada al método con un caso base, el método devuelve un resultado. Si se hace la llamada al método con un problema más complejo, el método comúnmente divide el problema en dos piezas conceptuales: una pieza que el método sabe cómoresolver y otra pieza que no sabe cómo resolver. Para que la recursividad sea factible, esta última pieza debe ser similar al problema original, pero una versión ligeramente más sencilla o simple del mismo. Debido a que este nuevo problema se parece al problema original, el método llama a una nueva copia de sí mismo para trabajar en el problema más pequeño; a esto se le conoce como llamada recursiva, ytambién como paso recursivo. Por lo general, el paso recursivo incluye una instrucción return, ya que su resultado se combina con la parte del problema que el método supo cómo resolver, para formar un resultado que se pasará de vuelta al método original que hizo la llamada. Este concepto de separar el problema en dos porciones más pequeñas es una forma del método “divide y vencerás
El pasorecursivo se ejecuta mientras siga activa la llamada original al método (es decir, que no haya terminado su ejecución). Se pueden producir muchas llamadas recursivas más, a medida que el método divide cada nuevo subproblema en dos piezas conceptuales. Para que la recursividad termine en un momento dado, cada vez que el método se llama a sí mismo con una versión más simple del problema original, lasecuencia de problemas cada vez más pequeños debe converger en un caso base. En ese punto, el método reconoce el caso base y devuelve un resultado a la copia anterior del método. Después se origina una secuencia de retornos, hasta que la llamada al método original devuelve el resultado final al método que lo llamó.
Un método recursivo puede llamar a otro método, que a su vez puede hacer unallamada de vuelta al método recursivo. A dicho proceso se le conoce como llamada recursiva indirecta o recursividad indirecta. Por ejemplo, el método A llama al método B, que hace una llamada de vuelta al método A. Esto se sigue considerando como recursividad, debido a que la segunda llamada al método A se realiza mientras la primera sigue activa; es decir, la primera llamada al método A no haterminado todavía de ejecutarse (debido a que está esperando que el método B le devuelva un resultado) y no ha regresado al método original que llamó al método A.
Para comprender mejor el concepto de recursividad, veamos un ejemplo que es bastante común para los usuarios de computadora: la definición recursiva de un directorio en una computadora. Por lo general, una computadora almacena los archivos...