Estructura de datos

Instituto Tecnológico Superior de Teziutlán Estructuras de Datos Recursividad

Temario
2.1 Definición 2.2 Métodos recursivos 2.3 Ejemplo de casos recursivos

Contenidos 2.1 Definición
Unalgoritmo 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 o recurrente. Generalmente, si laprimera llamada al subprograma se plantea sobre un problema de tamaño u orden N, cada nueva ejecución recurrente del mismo se planteará sobre problemas, de igual naturaleza que el original, pero de untamaño menor que N. De esta forma, al ir reduciendo progresivamente la complejidad del problema que resolver, llegará un momento en que su resolución sea más o menos trivial (o, al menos,suficientemente manejable como para resolverlo de forma no recursiva). En esa situación diremos que estamos ante un caso base de la recursividad. Las claves para construir un subprograma recurrente son: Cadallamada recurrente se debería definir sobre un problema de menor complejidad (algo más fácil de resolver). Ha de existir al menos un caso base para evitar que la recurrencia sea infinita. Es frecuente quelos algoritmos recurrentes sean más ineficientes en tiempo que los iterativos aunque suelen ser mucho más breves en espacio.

2.2 Métodos recursivos
Como se puede ver, la recursividad no representaninguna dificultad y de hecho es una herramienta muy útil para programación de algoritmos. Hay muchos algoritmos que sólo se resuelven con recursividad, o al menos cuya resolución más directa yelegante está basada en realizar funciones recursivas, que se llamen a si mismas para obtener el resultado final. Por ejemplo el recorrido de diversas estructuras de datos, como las de tipo árbol, siemprese acostumbran a realizar de manera recursiva, para poder estar seguros de que pasamos por todas las ramas del árbol.

2.3 Ejemplo de casos recursivos

Quizás en la teoría cueste más ver lo que...