Lab. Algoritmos computacionales: Análisis recursivo

Recursividad e iteración

La recursividad es una técnica de programación importante, se utiliza para realizar una llamada a una función desde la misma función. Se emplea en problemas cuya solución se puede hallar solucionando el mismo problema, pero con un caso de menor tamaño.

Algunas razones para usar la recursividad pueden ser: problemas "casi" irresoluble con las estructuras iterativas, soluciones elegantes y más simples. Una condición necesaria es la asignación dinámica de memoria.

Dentro de la recursividad entra la modularidad, que consiste en dividir el algoritmo en módulos, cada uno de estos lleva a cabo una función, muchas de las veces los módulos sirven para varios algoritmos, el módulo más pequeño se le llama subrutina. Muchas veces utilizamos subrutinas de las bibliotecas estándares de ANSI C como:

Impresión en el terminal (stdio.h)
Lectura de datos desde el teclado (stdio.h)
Operaciones matemáticas (math.h)
Manipulación de cadena de caracteres (string.h)

Iteración es la repetición de una serie de instrucciones en un programa de computadora. Puede usarse tanto como un término genérico (como sinónimo de repetición) así como para describir una forma específica de repetición con un estado que puede sufrir cambios.

Pentágono iterativo.

La iteración puede aproximarse por medio de técnicas recursivas en lenguajes de programación funcional. El ejemplo que sigue está escrito en Scheme. Nótese que es un código recursivo (un caso especial de iteración), pues la definición de "cómo iterar", la función iter, se llama a sí misma de manera de solucionar la instancia del problema.

La recursividad y la iteración (ejecución en bucle) están muy relacionadas, cualquier acción que pueda realizarse con la recursividad puede realizarse con iteración y viceversa. Normalmente, un cálculo determinado se prestará a una técnica u otra, sólo necesita elegir el enfoque más natural o con el que se sienta más cómodo.

Claramente, esta técnica puede constituir un modo de meterse en problemas. Es fácil crear una función recursiva que no llegue a devolver nunca un resultado definitivo y no pueda llegar a un punto de finalización. Este tipo de recursividad hace que el sistema ejecute lo que se conoce como bucle "infinito".

¿En que consiste la recursividad?

El método principal (main) puede hacer el llamado a subrutinas, al igual que esas subrutinas pueden llamar a otras, y esas a otras, no hay limite fijo para seguir llamando.

En el cuerpo de sentencias del subalgoritmo se invoca al propio subalgoritmo para resolver “una versión más pequeña” del problema original.

Habrá un caso (o varios) tan simple que pueda resolverse directamente sin necesidad de hacer otra llamada recursiva.

Pasos para un programa recursivo

Obtención de una definición exacta del problema
Determinar el tamaño completo del problema que hay que resolver (parámetros en la llamada inicial)
Resolver el o los casos bases o triviales (no recursivos)
Resolver el caso geenral en terminos

Análisis asintótico revisitado

Todo toma tiempo en la recursividad toma tiempo, como la asignación de una variable, la llamada a una rutina, ademas de que hay que tomar en cuenta los pasos a realizar, escribir una salida y leer una entrada simple, todo toma tiempo constante.

Algoritmo recursivo

Es un algoritmo que demuestra la solución a un problema llamándose a si mismo, esto como ya lo sabemos se llama método recursivo.

Las claves para construir un subprograma recurrente son:

Cada llamada 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 que los algoritmos recurrentes sean más ineficientes en tiempo que los iterativos aunque suelen ser mucho más breves en espacio.

Ejemplo

Solución recursiva a las Torres de Hanoi:

Si n=1 mueva el disco de A a C y pare

Mueva los n-1 discos superiores de A a B, con C auxiliar

Mueva los discos restantes de A a C

Mueva los n-1 discos de B a C, usando A como auxiliar

Planteamos un procedimiento recursivo con cuatro parámetros: