Revursividad

Programación y Estructura de Datos
Recursividad

Algoritmo Recursivo
Un algoritmo recursivo es un algoritmo que expresa la solución de un problema en términos de una llamada a sí mismo. Lallamada a sí mismo se conoce como llamada recursiva. Ejemplo: void funcionRecursiva(int a) { …………… …………… funcionRecursiva(a+1); …………… …………… }

Algoritmo Recursivo
• Para que un algoritmo recursivo nose convierta en infinito debe contener una condición que garantice la terminación del algoritmo recursivo en un tiempo finito. • Es lo que se conoce como CONDICIÓN DE PARADA, que debe hacer que no segeneren más llamadas recursivas. • También debe contener un PASO DE LA RECURSIVIDAD, que garantice que al ejecutar el algoritmo recursivo se tiende a la condición de parada.

Función Recursiva
Unasolución que involucra volver a utilizar la función original, con parámetros que se acercan más al caso base. Los pasos que sigue el caso recursivo son los siguientes:
1. El procedimiento se llama así mismo 2. El problema se resuelve, resolviendo el mismo problema pero de tamaño menor 3. La manera en la cual el tamaño del problema disminuye asegura que el caso base eventualmente se alcanzaráRecursividad - Ventajas
• Proporciona simplicidad en la comprensión de los problemas. • Es un método natural de resolver problemas. • Permite una gran potencia de cálculo.

• La corrección de losalgoritmos se comprueba fácilmente.

Recursividad - Desventajas
• Aumenta el consumo de recursos de la máquina (sobre todo de la pila). • Es más lenta que las soluciones iterativas equivalentes(siempre que exista la solución iterativa equivalente).

Recursividad - ¿Por qué escribir programas recursivos? • Son mas cercanos a la descripción matemática. • Generalmente mas fáciles de analizar• Se adaptan mejor a las estructuras de datos recursivas. • Los algoritmos recursivos ofrecen soluciones estructuradas, modulares y elegantemente simples.

Recursividad – Consideraciones...