Algoritmos Recursivos

Los algoritmos recursivos son aquellos que solucionan un problema a través de llamadas a sí mismos. Son bastante y utilizados en lenguajes declarativos como prolog, presentan unas características bastante particulares que presentan unas ventajas y también desventajas, la principal ventaja es el espacio que ocupa el código en el programa, generalmente el tamaño de este tipo de algoritmos es bastante pequeño, la reutilización de código es su principal objetivo ya que por medio de procesos iterativos se llega a la resolución de un problema,  soluciones elegantes, soluciones simples y claras y soluciones a problemas de nivel de complejidad bastante alto.

Sin embargo estos algoritmos presentan una desventaja que tienen que ver con su uso, es decir hay que tener mucho cuidado a la hora de usarlos,  para eso hay unas claves para utilizar algoritmos recursivos de una manera correcta:

1.                  En acción recurrente  del algoritmo el problema a resolver debe de ser de menor complejidad.

2.                  Ha de existir un caso base para que la recursividad no se haga infinita.

 La primera recomendación es mucha importancia, ¿Porque?, simplemente porque no es tiene sentido que a medida que se avanza el problema se complique aún más, además el objetivo de la recursividad es resolver el problema en la menor cantidad de llamadas recursivas, hay que resaltar que las llamadas recursivas inciden mucho en el tiempo de ejecución del programa y en la cantidad de recursos que este puede utilizar a pesar de que le recurrencia ocupa mucho menos espacio suele ser más ineficiente que el uso de un algoritmo de tipo iterativo.

La primera ejecución de un algoritmo recursivo se le llama caso base o punto de partida, se debe de tener en cuenta que entre el caso base y los casos no base se tienen que cubrir todos los estados posibles y en cada llamada al caso base.

En cada llamada el caso no base debe de llevar a la resolución de un problema cada vez más pequeño que no necesariamente no llegan a tocar al caso base.

 Complejidad en algoritmos recursivos.

La complejidad algorítmica representa la cantidad de  recursos (temporales) que necesita un algoritmo para resolver un problema y por tanto permite determinar la eficiencia de dicho algoritmo.

El tiempo empleado por el algoritmo se mide en pasos la medida del tiempo tiene que ser independiente:

     ·   de  la máquina

     ·   del lenguaje de programación

     ·   del compilador

     ·   de cualquier otro elemento hardware o software que influya en el análisis.

Para conseguir esta independencia una posible medida abstracta puede consistir en determinar cuantos pasos se efectúan al ejecutarse el algoritmo.

El tiempo requerido por un algoritmo es función del tamaño de los datos. Por esta razón la complejidad temporal se expresa de la siguiente forma:

T(n)

Dependiendo del problema, el tamaño del dato representa cosas diferentes:

      ·    el número en sí

      ·    el número de dígitos o elementos que lo compone.

Otra característica importante es que no todos los datos, dentro de un problema, poseen la misma importancia de cara a la complejidad algorítmica.

Ejemplo:

Algoritmo de suma lenta

while b>0 do begin

a:=a+1;

b:=b-1;

end;

En este caso T=T(b).

Otra característica es que la complejidad algorítmica no sólo depende del tamaño sino del propio dato en sí.

Ejemplo:

type

tintervalo=0..N;

tvector=array[1..N] of integer

FUNCTION Busquedasecord(v:tvector;elem:telem):tintervalo

var

i:tintervalo;

begin

i:=0;

repeat

i:=i+1;

until (v[i]>=elem) or (i=N);

if v[i]=elem then

Busquedasecord:=i

else

Busquedasecord:=0

End;

En este algoritmo se pueda dar las siguientes situaciones:

     ·         Caso mejor: el elemento este en la primera posición.

     ·         Caso peor: Se tenga que recorrer todo el vector.

     ·        Caso promedio o esperado: Puesto que todas las posiciones son  equiprobables el tiempo será n/2 pasos.