## 1.3 ECUACIONES DE RECURRENCIA

El análisis del tiempo de ejecución de un programa recursivo vendrá en función del tiempo requerido por la(s) llamada(s) recursiva(s) que aparezcan en él. De la misma manera que la verificación de programas recursivos requiere de razonar por inducción, para tratar apropiadamente estas llamadas, el cálculo de su eficiencia requiere un concepto análogo: el de ecuación de recurrencia.

Demostraciones por inducción y ecuaciones de recurrencia son por tanto los conceptos básicos para tratar programas recursivos.

Supongamos que se está analizando el costo de un algoritmo recursivo,intentando calcular una función que indique el uso de recursos, por ejemplo el tiempo, en términos del tamaño de los datos; denominémosla T(n) para datos de tamaño n. Nos encontramos con que este costo se define a su vez en función del costo de las llamadas recursivas, es decir, de T(m) para otros tamaños m (usualmente menores que n). Esta manera de expresar el costo T en función de sí misma es lo que denominaremos una ecuación recurrente y su resolución, es decir, la obtención para T de una fórmula cerrada (independiente de T) puede ser dificultosa.

El análisis temporal de un algoritmo iterativo es simple con base en la operación básica de este, para los algoritmos recursivos nos vamos a encontrar con una dificultad añadida, pues la función que establece su tiempo de ejecución viene dada por una ecuación en recurrencia, es decir,T(n) = E(n), en donde en la expresión E aparece la propia función T.

Cuando se quiere calcular la demanda de recursos de un algoritmo definido recursivamente, la función complejidad que resulta no está definida sólo en términos del tamaño del problema y algunas constantes, sino en términos de la función complejidad misma. Además no es una sola ecuación, dado que existen otras (al menos una) que determinan la cantidad de recursos para los casos base de los algoritmos recursivos. Dada esta situación, para poder obtener el comportamiento del algoritmo, es necesario resolver el sistema recurrente obtenido.

Ejemplo 1: Factorial recursivo

    int  Factorial( int  num )

    {

         if  ( num  ==  0 )

             return  1;

         else

            return  num * Factorial(  num -  1 );

    }

Considerando el producto de num*Factorial(num-1) como operación básica, y el costo del caso base como 1 (T(0)=1), podemos construir la ecuación recurrente para calcular la complejidad del algoritmo como sigue:

T(0) = 1 Costo del caso base

T(n) = 1 + T(n-1)

Ejemplo 2: Fibonacci recursivo

    int  Fibonacci(int  num)

    {

         if  (num  ==0)

             return  0;

         else if (num  ==  1)

             return  1;

         else

            return  Fibonacci(num-1) + Fibonacci  (num-2);

    }

Considerando la suma Fibonacci(num-1) + Fibonacci (num-2) como operación básica, y el costo 1 de los 2 casos base podemos construir la ecuación recurrente para calcular la complejidad del algoritmo:

T(0)=1 Costo de n=0

T(1)=1 Costo de n=1

T(n)= T(n-1) + T(n-2)

Ejemplo 3: Torres de Hanói recursivo

    Hanoi(N, Src, Aux, Dst)

    {

      if(n>0)

      {

      Hanoi(N -  1, Src, Dst,  Aux);

      Mover_de(Src,Dst);

      Hanoi(N -  1, Aux, Src, Dst);

      }

      return;

    }

Considerando la operación Mover_de(Src,Dst) como operación básica, y tomado un costo de 0 cuando N=0, podemos construir la ecuación recurrente para calcular la complejidad del algoritmo:

T(0)=0

T(n)=T(n-1) + 1 + T(n-1) = 2T(n-1)+1

Resolución de Recurrencias

Las ecuaciones de recurrencia son utilizadas para determinar cotas asintóticas en algoritmos que presentan recursividad.
Veremos dos técnicas básicas y una auxiliar que se aplican a diferentes clases de recurrencias:

• Método de sustitución
• Método de iteraciones
• Método maestro

###