Bienvenida

Programacion II

Recursividad

Programación II trata del diseño y análisis formal de algoritmos abordándolo desde el punto de vista recursivo y el iterativo. La formación básica en programación (asignatura PROGRAMACIÓN I, por ejemplo) proporciona conceptos básicos de programación imperativa: secuencia de órdenes, sentencias condicionales, bucles. Usando el típico ejemplo del factorial, se propone como ejercicio el desarrollo de un procedimiento o función que calcule el factorial de un número no negativo (el factorial !n de un número n no negativo es igual a producto de todos los números no negativos iguales o inferiores que n teniendo en cuenta que el factorial de 0 es 1 por definición). Intuitivamente alguien con experiencia en MODULA-2 programaría la siguiente función para cálculo de factorial:

PROCEDURE Factorial(n : CARDINAL) : CARDINAL
BEGIN
  VAR Resultado,i : CARDINAL ;
  Resultado :=1 ;
  FOR i :=1 TO n DO
    Resultado :=Resultado*i ;
  END ;
  RETURN Resultado
END Factorial ;

Existe una vía alternativa para abordar el diseño de algoritmos: la recursiva. Sin embargo la mayoría de las personas que abordan la asignatura PROGRAMACION II por primera vez no han asimilado el concepto de recursividad. El objeto de este apartado es la introducción de ese concepto, dada su importancia para el dominio de la asignatura.

Una aproximación diferente a la programación de una función que calcule el factorial de un número estaría basada en el siguiente razonamiento:

• El factorial de 0 es 1

• El factorial de un número natural n, mayor que cero, es igual al producto de n por el factorial del número n-1, es decir: ! n=n* !(n-1)

Siguiendo este razonamiento se puede llegar a programar el siguiente algoritmo en MODULA-2:

PROCEDURE Factorial(n: CARDINAL): CARDINAL;
BEGIN
  IF n=0 THEN
     RETURN 1
  ELSE
     RETURN n* Factorial(n-1) 
  END
END Factorial;

La primera sorpresa reside en el hecho de que en la línea remarcada se ejecute una llamada a la propia función Factorial. ¿ Es esto posible ?. Conceptualmente si. En la práctica muchos lenguajes de alto nivel permiten la recursividad: Pascal, C, MODULA-2, etc.

En el algoritmo iterativo la solución parece clara: se utiliza una variable en la que se va acumulando el producto de los n números. ¿ Cómo funciona el procedimiento recursivo?. Supongamos que se desea calcular el factorial del número 4. En el programa principal se ejecutará un sentencia análoga a:

Resultado:= Factorial(4);

En esta llamada, y puesto que 4 es distinto de 0, se ejecutará una segunda llamada a Factorial con parámetro 4-1=3

En la segunda llamada se efectuará una tercera llamada a Factorial con parámetro 3-1=2.

En la tercera llamada se efectuará una cuarta llamada a Factorial con parámetro 2-1=1

En la cuarta llamada se efectuará una quinta llamada a Factorial con parámetro 1-1=0

En esta llamada se cumple la condición n=0, por lo tanto se retornará a la cuarta llamada el resultado 1.

La cuarta llamada devolverá a la tercera el resultado 1*1=1

La tercera llamada devolverá a la segunda el resultado 2*1=2

La segunda llamada devolverá a la primera el resultado 3*2=6

La primera llamada devolverá al programa principal el resultado final 4*6=24

Cada llamada supone una nueva ejecución del procedimiento Factorial, en cada llamada se ha de mantener un contexto de ejecución diferente (parámetros, variables locales, punto de retorno), los programas compilados a partir de lenguajes de alto nivel que soportan la recursividad gestionan este proceso de forma transparente al programador.

Esquemáticamente la ejecución de Factorial(5) se resuelve con el siguiente proceso:

El diseño y análisis recursivo de algoritmos es una técnica muy potente una vez dominada. Muchos algoritmos tienen una solución recursiva natural. En muchos casos la programación recursiva permite resolver problemas de forma elegante, con menos código y más fácil de entender. Sin embargo la necesidad de gestionar la pila en la que se suelen mantener los contextos de ejecución independientes hace que la solución recursiva resulte algo menos eficiente, en general, en cuanto a tiempo de ejecución que la iterativa. Siempre es posible obtener la solución iterativa equivalente a una recursiva dada, aunque en muchos casos el programa resultará menos claro y compacto. Especialmente cuando el algoritmo tiene una solución recursiva natural. Se presenta un ejemplo industrial en la NOTA.

Para que una solución recursiva sea correcta se han de cumplir una serie de reglas. Estas reglas son materia importante en el estudio del Capítulo 4 de Peña. Se introducirán los criterios fundamentales utilizando el ejemplo del Factorial:

• Siempre ha de existir una (o varias) condiciones para los parámetros de entrada que permitan devolver un resultado sin necesidad de nueva llamada recursiva. Esta es la llamada solución trivial al problema. En el caso tratado cuando n=0 el resultado inmediato es 1 y no hay llamada recursiva

• Cuando los valores de los parámetros de entrada no cumplen la condición de solución trivial se volverá a llamar recursivamente el mismo procedimiento (solución o soluciones no triviales). En todas las llamadas recursivas que se realicen el valor del parámetro de llamada se ha de modificar de forma que se "aproxime" al valor de solución trivial. En el caso tratado en la llamada recursiva se utiliza n-1 en lugar de n, n-1 está "más próximo" al valor trivial 0 que n. (El concepto intuitivo de "proximidad" utilizado se define rigurosamente en base a la teoría de inducción noetheriana en el capítulo 4 de Peña)

• La solución retornada en el caso de condición no trivial ha de ser correcta en la hipótesis de que la llamada recursiva devuelve una solución correcta. Este concepto es la base del principio de inducción y la parte más importante en el diseño y verificación de un algoritmo recursivo. Para el caso tratado: en la hipótesis de que la llamada Factorial (n-1) devuelve una solución correcta, es decir devuelve ! (n-1), el resultado final es correcto puesto que se devuelve finalmente el valor :

n* Factorial(n-1)= n* ! (n-1)= ! n.

Es importante empezar cuanto antes a razonar en recursivo buscando la aproximación recursiva a problemas simples. Algunos ejemplos:

• La suma de una secuencia de n números puede abordarse de forma iterativa mediante una variable de acumulación inicializada a cero en la que sucesivamente se van sumando los números. Un planteamiento recursivo sería: la suma de una secuencia de n números se puede obtener: si n es mayor que 1, como suma del primero con el resultado de la suma de la secuencia de n-1 números dada por el segundo y siguientes. Si n no es mayor que 1 la suma is igual al valor del elemento único de la secuencia.

• La búsqueda de una palabra en un diccionario se realizaría, por aproximación iterativa, mirando sucesivamente palabras desde la primera página hasta encontrar la palabra buscada u otra que sea posterior a ella en orden alfabético (en este caso la palabra no está en el diccionario). Una solución recursiva sería: abrir el diccionario por la mitad, si la primera palabra de la página es posterior a la buscada abrir el diccionario por la mitad de la mitad posterior y repetir el proceso, si no es así abrirlo por la mitad de la primera mitad y repetir el proceso .... Esta es la forma natural que usamos para buscar palabras en un diccionario.

• Torres de Hanoi:

la tarea planteada a los monjes del templo de Bramah es mover n discos concéntricos de distinto diámetro desde una aguja 1 a otra aguja 3 usando como almacén temporal la aguja 2 si es necesario. No puede mover más de un disco a la vez y nunca ha de permanecer un disco de mayor diámetro sobre otro de diámetro inferior.¿ Quién encuentra una solución iterativa a este problema ?. Sin embargo la solución recursiva es más abordable: mover n discos entre la aguja 1 y la 3 es posible moviendo n-1 discos entre la 1 y la 2, moviendo el disco mayor desde la 1 a la 3 y moviendo luego los n-1 discos desde la 2 a la 3. En general mover n discos desde la aguja i a la j puede conseguirse siguiendo el siguiente procedimiento en pseudocódigo:

   Procedimiento Hanoi(n, i, j)
     Si n=1 entonces
       mover disco de i a j
     Si no entonces
       Hanoi(n-1,i,6-i-j)
       mover disco de i a j
       Hanoi(n-1,6-i-j,j)
     Fin Si
   Fin Hanoi

Así si ejecutamos Hanoi(4,1,3) obtenemos:

Si quieres saber más sobre las Torres de Hanoi, ver applets demostrativos etc. una página imprescindible es:

http://www.pangea.ca/kolar/javascript/Hanoi/HTonWebE.html

y uno de los mejores applets en:

http://www.eng.auburn.edu/~fwushan/Hanoi1.html

NOTA. La transformada Rápida de Fourier

Posiblemente unos de los algoritmos con más trascendencia industrial ha sido el de Transformada Rápida de Fourier (Fast Fourier Transform o FFT). Ha permitido el cálculo rápido de transformadas de Fourier en aplicaciones relacionadas con la óptica, acústica, física cuántica, telecomunicaciones, teoría de sistemas y procesamiento de señales, reconocimiento del habla etc. Fue descubierto por Cooley y Turkey en 1965. La programación de FFTs en su forma más eficiente en cuanto a tiempo de ejecución da lugar a algoritmos iterativos más o menos complejos y muchas veces difíciles de leer. Sin embargo, cuando lo que prima es la claridad del código fuente, la codificación recursiva resulta más simple y clara. La FFT es un algoritmo naturalmente recursivo ya que el cálculo de la transformada de N puntos se basa en la combinación de las transformadas de dos secuencias de N/2 puntos. Una solución programada en C es (se presenta sólo a título de ejemplo, no es necesario comprenderla):

void fft(double *x, double *y, int izda, int dcha)
{
  double vr,vi,wr,wi;  /* partes real e imaginaria de v y w */
  int medio,i,j;
  int n;
  double fase, incfase;

  if(izda<dcha) {
    /* cálculo de las FFTs de las subsecuencias de N/2 puntos */
    medio=(izda+dcha)/2;
    fft(x,y,izda,medio);
    fft(x,y,medio,dcha);
    /* combinación del resultado */
    n=dcha-izda+1;
    incfase=2* M_PI/n;
    for(i=izda; i<=medio; i++) {
      j=i+n/2;
      fase=(i-izda)*incfase;
      vr=x[i];
      vi=y[i];
      wr=x[j]*cos(fase)+y[j]*sin(fase);
      wi=-x[j]*sin(fase)*y[j]*cos(fase);
      x[i]=vr+wr;
      y[i]=vi+wi;
      x[j]=vr-wr;
      y[j]=vi-wi;
    }
  }
  return;
}

Un programa más claro y simple todavía se obtiene en entornos que tienen definido o permiten definer el tipo número complejo ( C++, Java, Fortran, Ada ...)

Volver a texto