Capítulo 2. Complejidad Temporal de Métodos Recursivos

Algoritmos Recursivos

Un algoritmo recursivo es aquel que expresa la solución a un problema en términos de una llamada a sí mismo. Esta llamada a si mismo se denomina llamada recursiva o recurrente. Para evitar un ciclo sin fin es muy importante definir lo que se conoce como el caso base o condición de corte.

A lo largo del curso se utiliza la notación de pseudocódigo de forma tal que cada uno pueda utilizar el lenguaje de programación que le resulte más familiar para implementar el algoritmo.

A continuación presentamos un ejemplo general de un método recurrente.

Este algoritmo genérico sirve para ilustrar a que nos referimos cuando decimos caso base.

Llamamos 'proceso' a una función que se encargue de realizar algo con la entrada, ya sea sumarle una constante o ejecutar cualquier cosa que sea de interés para nuestro problema.

En el caso que la entrada al método A no cumpla la condición de base, se efectúa la llamada recurrente, restando una constante 'c' a la entrada.

Es lógico que se reduzca la entrada en alguna forma, sino no podríamos llegar nunca al caso base y de esa manera finalizar la ejecución del algoritmo.

Consideraremos dos formas de reducir la entrada: restando o dividiendo. Con cualquiera de ellas estamos logrando el objetivo. Sin embargo, veremos que el análisis de complejidad temporal varía dependiendo del caso.

Antes de profundizar en cada caso, notar las siguientes definiciones para comprender la notación:

Caso 1: Sustracción sobre la entrada

Este es el caso visto en el ejemplo del método A. La función que representa el costo para estos casos es

Para este caso de sustracción, lo que determina el costo del algoritmo será el valor de 'a' respecto de 1 como se ve a continuación:

Caso 2: División de la entrada

En este caso, en lugar de restar algún elemento de la entrada, lo que hacemos es dividir la misma generando así entradas más pequeñas para la llamada recursiva. La función que representa el costo para este caso es

El costo del algoritmo en estos casos estará determinado por la relación existente entre los parámetros a, b y k (grado del polinomio f(n))

En el próximo capítulo utilizaremos estas funciones para analizar la complejidad temporal de algunos ejemplos de métodos recurrentes.

Fuentes:
Programación III - Apuntes de Cátedra. Cuadrado Estrebou, María Fernanda. Trutner, Guillermo Hernán.