Recursividad

Recurrencia, recursión o recursividad es la forma en la cual se especifica un proceso basado en su propia definición

Un problema que pueda ser definido en función de su tamaño, sea este N, pueda ser dividido en instancias más pequeñas (< N) del mismo problema y se conozca la solución explícita a las instancias más simples, lo que se conoce como casos base, se puede aplicar inducción sobre las llamadas más pequeñas y suponer que estas quedan resueltas

En programación se utiliza para realizar una llamada a una función desde la misma función.

Un algoritmo es recursivo cuando 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.

He aquí algunas de sus aplicaciones más representativas:

1. Demostraciones por Inducción Matemática:

Las Estructuras recursivas son ideales para aplicar y demostrar que es correcto que una Propiedad vale para un caso base o elemental, así como para casos más pequeños.

2. Sirve para definir objetos Fractales mediante Algoritmos Recursivos.

Objeto Fractal: objeto semigeométrico cuya estructura básica, fragmentada o irregular, se repite a diferentes escalas. Por ej. Las Nubes, Las Montañas, un copo de nieve.

3. Para estimar el tiempo de ejecución.

Muchas veces el tiempo de ejecución de un algoritmo se expresa de manera natural como una función recursiva.

4. Para definir complicadas estructuras de datos.

Muchas veces se quiere definir nuevos tipos de datos para manipular grandes cantidades de información.

5. Para analizar limitaciones teóricas de las computadoras.

Existe un teorema que demuestra que todo algoritmo iterativo tiene un equivalente recursivo y viceversa. Se puede “Simplificar un problema indecidible”.

6. Para definir nuevos lenguajes de programación

7. Es un método poderoso usado en Inteligencia Artificial.

8. Solución de Problemas Combinatorios y algunos acertijos.

...