Análisis de algoritmos recursivos

Recursividad

La recursividad es un concepto fundamental en matemáticas y en computación . Es una alternativa diferente para implementar estructuras de repetición (iteración) .

Se puede usar en toda situación en la cual la solución pueda ser expresada como una secuencia de movimientos, pasos o transformaciones gobernadas por un conjunto de reglas no ambiguas .

La recursividad es un recurso muy poderoso que permite expresar soluciones simples y naturales a ciertos tipos de problemas. Es importante considerar que no todos los problemas son naturalmente recursivos.

Un objeto recursivo es aquel que aparece en la definición de si mismo, así como el que se llama a sí mismo.

La recursividad es un fenómeno que se presenta en muchos problemas de forma natural, delegando la solución de un problema en la solución de otro más pequeño.

El análisis temporal de un algoritmo recursivo vendrá en función del tiempo requerido por la(s) llamada(s) recursiva(s) que aparezcan en él.

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, 𝑻(𝒏) = 𝑬(𝒏), en donde en la expresión 𝐸 aparece la propia función 𝑻.

Ecuaciones en recurrencia

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

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

Ejemplo 2. Fibonacci recursivo

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.

 Ejemplo 3. Torres de Hanói recursivo

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

 

Ejemplo 4. Búsqueda binaria recursiva

Considerando la operación como operación básica las comparaciones, y tomado un coste de 0 cuando Tam(numeros[])=0, podemos construir la ecuación recurrente para calcular la complejidad del algoritmo.

Ejemplo 5. Merge-sort

Sea A un arreglo de n elementos y p, r índices del rango a ordenar

Recurrencias homogéneas

Son de la forma:

                             Donde los coeficientes ai son números reales, y k es un número natural entre 1 y n

Para eliminar la recurrencia se buscan términos que sean combinaciones de funciones exponenciales de la forma:

Donde los valores 𝑐1, 𝑐2, … , 𝑐𝑛 y 𝑟1, 𝑟2, … , 𝑟𝑛 son números reales, y 𝑝1(𝑛), … , 𝑝𝑘(𝑛) son polinomios en 𝑛 con coeficientes reales.

Para resolverlas haremos el cambio 𝑥 𝑘 = 𝑇(𝑛), con lo cual obtenemos la ecuación característica asociada:

Llamemos 𝑟1, 𝑟2, … , 𝑟𝑘 a sus raíces, ya sean reales o complejas. Dependiendo del orden de multiplicidad de tales raíces, pueden darse los siguientes casos:

•  Caso 1: Raíces distintas
• Caso 2: Raíces con multiplicidad mayor que 1

Caso 1. Raíces distintas

Si todas las raíces de la ecuación característica son distintas, esto es, 𝑟𝑖 ≠ 𝑟𝑗 si 𝑖 ≠ 𝑗, entonces la solución de la ecuación en recurrencia viene dada por la expresión:

                   Donde los coeficiente ci se determinan a partir de las condiciones iniciales

Caso 2. Raíces con multiplicidad mayor que 1

Supongamos que alguna de las raíces (p.e. 𝑟1) tiene multiplicidad 𝑚 > 1 . Entonces la ecuación característica puede ser escrita en la forma:

En cuyo caso la solución de la ecuación en recurrencia viene dada por la expresión:

              Donde los coeficientes ci se determinan a partir de las condiciones iniciales

Este caso puede ser generalizado, si 𝑟1, 𝑟2, … , 𝑟𝑘 son las raíces de la ecuación característica de una ecuación en recurrencia homogénea, cada una de multiplicidad 𝑚𝑖 , esto es, si la ecuación característica puede expresarse como:

Entonces la solución a la ecuación en recurrencia viene dada por la expresión:

                Donde los coeficientes ci se determinan a partir de las k condiciones iniciales

Recurrencias homogéneas (Ejemplo)