ÉPOCA II. ENERO 1993

INTRODUCCIÓN A LA PROGRAMACIÓN RECURSIVA: ORDENACIÓN DE LISTAS

© Warlord/Impulse

2 de diciembre de 1992

Con este artículo voy a "matar dos pájaros de un tiro": Por un lado, voy a hacer una pequeña introducción a la programación recursiva, técnica que por otro lado muchos de ustedes conocéis aunque en realidad, soléis esquivar. Por otra parte, voy a mostrar un curioso método de ordenación llamado "Quick" (rápido), de excelentes resultados. Este algoritmo lo encontré en un libro llamado "Algoritmos+estructuras de datos=programa" pero que recomiendo no os molestéis en leer.

El programa en C lo he probado en una red Digital, espero que funcione en el Amiga sin problemas. De todos modos, lo único importante es el algoritmo.

Salvo contadas excepciones,todos hemos iniciado nuestros primeros pasos con un viejo Z80 y evidentemente, lo primero que aprendíamos era el BASIC. Reconozco que es un estupendo lenguaje para ser de aquellas fechas, pero no deja de padecer ciertos problemas de alguno de sus contemporáneos como el FORTRAN o el FORTH. Uno de ellos, es sin lugar a dudas la recursividad. Este término se aplica a algoritmos cuya solución viene dada por una serie de etapas, de modo que en la etapa n se soluciona a través de la n-1 u otra anterior. Esta técnica de recursividad nos puede librar de muchos dolores de cabeza y simplificar muchos cálculos. El problema es que, aunque no lo parezca, es difícil de dominar y de entender en que situaciones es conveniente o no aplicar.

Pongamos un ejemplo: Calculemos el factorial de un número. En Basic o en Fortran podría ser algo así:

(recordar, fact(n)=n!=n(n-1)(n-2)......1 )

FACT=1
DO I=N,1 STEP -1
FACT=FACT*I
ENDDO 

No está mal, pero esto es más elegante:

fact (n)
while n>=1 then
 fact(n)=nfact(n-1);
end 

Esta técnica de definir funciones llamando a la propia función es lo que antes he llamado recursividad. Como antes he dicho, no se puede utilizar en todos los lenguajes, pero afortunadamente sí en C, Pascal o Lisp. No hay que pensar que esta técnica resuelve todos los problemas, de hecho plantea otros muchos:

• Es fácil equivocarse y obtener nefastos resultados,con ejemplos tan fáciles como: fact(n)=n*fact(n-1) que llevaría a un bucle sin fin.

• No se puede predecir sus comportamiento y es difícil de seguirle la pista a una de estas rutinas

• Pero el problema más grave es la pérdida de información que dejamos por el camino. En este tipo de rutinas,sólo nos devuelve el último valor (en el caso anterior lo único que queremos, el factorial de n) pero en muchos casos necesitamos todos los resultados intermedios. Poner un ejemplo de éstos no es fácil, pero supongamos que por alguna extraña razón necesitamos el fact(6) y el de 5, 4, 3, 2 y 1.Podíamos calcularlos uno a uno pero también los podemos obtener a través del fact(6)lo cual supondría un considerable ahorro de tiempo. La "pega" es que fact(5) lo conocemos a través del fact(4) y así sucesivamente.Esto es fácil de arreglar en lenguajes no recursivos o bien si estamos programando en Ensamblador.

En el caso del ejemplo anterior:

DO I=1,N
FACTN=FACTN*I
END DO 

Aquí podemos obtener rápidamente Fact 5, 6 o cualquier número fácilmente.

De todos modos,este tipo de problemas no suele aparecer en programas de los llamémosles, normales, así que no voy a ponerme a discutir algo que por otro lado no es nada fácil de resolver en la mayoría de los casos.

Como antes os dije,paso a comentaros este método de ordenación llamado "rápido". Como podéis ver el método consiste en tomar un "pivote" central e ir ordenando alternativamente a derecha e izqda de él. Como veis se utiliza la programación recursiva pues en la propia rutina de ordenación se llama a ella en repetidas ocasiones.

Cuando veáis como funciona os puede parecer bastante malo. Nada más lejos de la realidad. Para los amantes de las demostraciones y la estadística, observar:

Cuando tomamos un elemento central "x",el número de intercambios a realizar será igual al número de elementos a la izqda de él (ed, x-1). Un elemento se cambiará si es mayor que este elemento central. La probabilidad de que esto suceda es (n-x-1)/n. Sumando desde 1 a n(n=número de elementos) obtenemos la media esperada de todos los intercambios:

I= 1 \ n-x
   -*/ ---- * (n-x-1) = función lineal de n.
   n _  n 

Esta función lineal es aproximadamente 2n-(n/2).

El resto de algoritmos suelen utilizar un número de intercambios de tipo cuadrático, con lo cual con 25 elementos el número de intercambios podría rondar los 500.

El programa es el siguiente:

/* Método "Quick" */
/* Programa realizado por Warlord/Impulse */
/* el 2 de Febrero de 1990 */ 
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int lista[1000];
contador=0;
main
{
 int i,j,x,n,stime;
 long ltime;
 printf("óCuántos números a ordenar? \n> ");
 scanf("%d ",&n);
 ltime=time(NULL);
 stime=(unsigned int) ltime/2;
 srand(stime);/*óEs así en el Lattice C?*/
 for (j=1;j<=n;j++)
  {
  lista[j]=(rand()/1000000);/* Los números los acoto en un rango de 1-200*/
  printf("%d numero= %d \n",j,lista[j]);
  }
 ordena (1,n);/* Llamada a la función de ordenación*/
/* Salida de resultados */
for (j=1;j<=n;j++){
 printf("%d numero= %d \n",j,lista[j]);
 printf("Ha necesitado %d intercambios", contador);
 }
/* ------------- SUBRUTINA DE ORDENACION -------------- */
ordena (izqda.dcha)
int izqda,dcha;
{
 int x,i=izqda,j=dcha;
 x=lista[izqda+dcha/2];
 while (i<=j){
  while (lista[i]<x) i++;
  while (lista[j]>x) j--;
  if (i<=j){
   intercambia(&lista[i],&lista[j]);
   j--;i++;contador++;
   }
  }
 if (izqda<j) ordena (izqda,j); /* RECURSIVIDAD */
 if (i<dcha) ordena (i,dcha);
 }
intercambia (a,b)
int *a,*b;
{
 int c;
 c=*a;*a=*b;*b=c;
}