Curso de Estructuras de Datos y Algoritmos / Algoritmos recursivos

En ciencias de la computación, la recursividad es un elemento muy importante en la solución de algunos problemas. Por definición, un algoritmo recursivo es aquel que utiliza una parte de él mismo como solución al problema. La otra parte generalmente es la solución trivial, es decir, aquella cuya solución será siempre conocida, es muy fácil de calcular, o es parte de la definición del problema a resolver. Dicha solución sirve como referencia y además permite que el algoritmo tenga una cantidad finita de pasos.

La implementación de estos algoritmos se realiza generalmente en conjunto con una estructura de datos, la pila, en la cual se van almacenando los resultados parciales de cada recursión.

A manera de ejemplo (típico en la enseñanza de este tema) es el cálculo de factorial de manera recursiva.

Se puede definir el factorial de un número entero positivo x como sigue:

x!=x*(x-1)*(x-2)...*3*2*1

donde ! indica la operación unaria de factorial.

Definimos, además:

1!=1 0!=1

Sin embargo, podemos observar que la definición del factorial de un número x, puede expresarse, a su vez, a través del factorial de otro número:

x!=x*(x-1)!

Es decir, para conocer el factorial de x basta con conocer el factorial de x-1 y multiplicarlo por x. Para conocer el factorial de x-1 basta con conocer el factorial de x-2, y multiplicarlo por x-1. Este proceso se realiza recursivamente, hasta llegar a la solución trivial, donde necesitamos el factorial de 1, el cual es 1.

Lo importante a notar en la igualdad anterior es que expresa un proceso recursivo, donde definimos una operación en términos de sí misma.

El seudocódigo queda así:

   inicio de la rutina Factorial
      Factorial(parámetro: entero x)
           si x vale 1 o x vale 0
             devolver 1
           si no
             devolver x*Factorial(x-1)

    fin de la rutina Factorial

Ventajas:

-Algunos problemas son esencialmente recursivos, por lo cual su implementación se facilita mediante un algoritmo de naturaleza recursiva, sin tener que cambiarlo a un método iterativo, por ejemplo. -En algunas ocasiones el código de un algoritmo recursivo es muy pequeño

Desventajas:

-Puede llegar a utilizar grandes cantidades de memoria en un instante, pues implementa una pila cuyo tamaño crece linealmente con el número de recursiones necesarias en el algoritmo. Si los datos en cada paso es muy grande, podemos requerir grandes cantidades de memoria.