Funciones recursivas. Fractales

Se denominan funciones recursivas a aquellas que se llaman a sí mismas. Un ejemplo típico es el método de ordenación quick-sort, el juego denominado Torres de Hanoi, etc.

Hay varios casos de funciones recursivas que se emplean en la Física, las funciones de Bessel, los polinomios de Hermite, etc.

Empezaremos por distinguir un método iterativo frente a un método recursivo mediante el ejemplo del cálculo del factorial de un número n.

n!=n·(n-1)·(n-2)...2·1

El resultado del factorial de un número entero es un número entero mucho más grande (long), que puede sobrepasar el rango de los enteros (int) si n es grande.

long factorial(int n){
	long resultado=1;
	for(int i=1; i<=n; i++){
		resultado*=i;
	}
	return resultado;
} 
long factorial(int n){
	if(n==0) return 1;
	return (n*factorial(n-1));
}

La geometría de la Tortuga

En primer lugar, creamos una clase que denominaremos Tortuga, por su similitud con la tortuga del lenguaje LOGO, tan popular a mediados de los años 80, en la que definiremos varios métodos que ejecutan movimientos o trazados simples. Una vez definidos los movimientos básicos en la clase Tortuga es posible crear rutinas recursivas que dibujen distintos motivos a escalas diferentes.

El estado de la tortuga, se especifica por su posición x e y y por su ángulo de orientación respecto del eje horizontal X. También podemos asignar a la tortuga un color (rojo, azul o verde)

Los distintos comandos que cambian el estado de la tortuga se seleccionan pulsando en tres botones de radio:

Inicia, sitúa a la tortuga en una posición x e y especificada, orientando la tortuga a lo largo del eje X (ángulo cero).

Gira, cambia la orientación de la tortuga, sumando a su dirección actual, el ángulo que seleccionamos en la barra de desplazamiento. Los posibles ángulos van desde –180º a 180º.

Mueve, desplaza la tortuga una distancia especificada a lo largo de su dirección. Se puede mover la tortuga sin que deje una traza o se puede mover de modo que deje una traza del color seleccionado. Para que dibuje su trayectoria, se activa la casilla titulada Lápiz.

El botón Nuevo borra la trayectoria de la tortuga y da comienzo a una nueva experiencia, situando a la tortuga en el origen, orientada a lo largo del eje X (ángulo cero).

El botón titulado Aplicar ejecuta cada uno de los tres comandos que se definen pulsando en cada uno de los tres botones de radio, e introduciendo los datos requeridos.

Ejemplos:

Inicia X: -50, Y:50 → se pulsa el botón Aplicar
Mueve
100, se activa la casilla Lápiz, se elige el color, se pulsa el botón Aplicar
Gira
-90º → se pulsa el botón Aplicar
Mueve
100 → se pulsa el botón Aplicar
Gira
-90º → se pulsa el botón Aplicar
Mueve
100 → se pulsa el botón Aplicar
Gira -
90º → se pulsa el botón Aplicar
Mueve
100 → se pulsa el botón Aplicar

Se pulsa el botón titulado Nuevo, para borrar la trayectoria anterior. Y a continuación, se ejecuta la siguiente serie de comandos

Inicia X: 0, Y:100 → se pulsa el botón Aplicar
Gira
-30º → se pulsa el botón Aplicar
Mueve
100, se activa la casilla Lápiz, se elige el color, → se pulsa el botón Aplicar
Gira
-60º → se pulsa el botón Aplicar
Mueve
100, → se pulsa el botón Aplicar
Gira
-60º → se pulsa el botón Aplicar
Mueve
100, → se pulsa el botón Aplicar
Gira
-60º → se pulsa el botón Aplicar
Mueve
100, → se pulsa el botón Aplicar
Gira
-60º → se pulsa el botón Aplicar
Mueve
100, → se pulsa el botón Aplicar
Gira
-60º → se pulsa el botón Aplicar
Mueve
100, → se pulsa el botón Aplicar

De este modo, podemos dibujar otras figuras geométricas sencillas.

stokesApplet aparecerá en un explorador compatible con JDK 1.1.

La clase Tortuga

La clase Tortuga tiene los siguientes miembros datos.

Los constructores inicializan los miembros dato, con valores por defecto o explícitos

public class Tortuga {
	double x;
	double y;
	double angulo; //radianes
	Color color;
	Graphics g;
public Tortuga(double x, double y, double angulo, Color color) {
	this.x=x;
	this.y=y;
	this.angulo=angulo*Math.PI/180;
	this.color=color;
}
public Tortuga() {
	this.x=0.0;
	this.y=0.0;
	this.angulo=0.0;
	this.color=Color.black;
}

La función miembro inicia, sitúa la tortuga en el origen, orientada hacia el Este (ángulo 0) y establece como color del lápiz el negro. Esta función proporciona, además, el contexto gráfico g, en el que se representan los movimientos de la tortuga.

public void inicia(Graphics g){
	x=0.0;
	y=0.0;
	angulo=0.0;
	color=Color.black;
	this.g=g;
}

La función colorea cambia el color de dicho lápiz

public void colorea(Color color){
	this.color=color;
}

La función miembro gira, cambia la orientación de la tortuga, sumándole a su orientación actual un determinado ángulo expresado en grados.

public void gira(double angulo){
	this.angulo+=angulo*Math.PI/180;
}

La función miembro salta, cambia la posición actual de la tortuga, a otra especificada por las coordenadas x e y.

public void salta(double x, double y){
	this.x=x;
	this.y=y;
}

La tortuga también puede cambiar de posición saltando a lo largo de su dirección (angulo) una distancia determinada.

public void salta(double distancia){
	double xx=x+distancia*Math.cos(angulo);
	double yy=y-distancia*Math.sin(angulo);
	salta(xx, yy);
}

La función traza es similar a salta, la única diferencia es que la tortuga dibuja con su lápiz el camino (segmento) que sigue para moverse de un punto a otro a lo largo de su dirección (angulo) una distancia especificada. Cuando llega al final del camino la tortuga actualiza su posición.

public void traza(double distancia){
	double xx=x+distancia*Math.cos(angulo);
	double yy=y-distancia*Math.sin(angulo);
	g.setColor(color);
	g.drawLine((int)xx, (int)yy, (int)x, (int)y);
	salta(xx, yy);
}

Fractales

El término fractal proviene de la palabra latina "fractus" y que se acuñó a finales de la década de los 70 por el matemático Benoit Mandelbrot.

Un fractal consta de fragmentos geométricos de orientación y tamaño variable, pero de aspecto similar. Si lo ampliamos nos irá mostrando una serie repetitiva de niveles de detalle, de modo que a todas las escalas que se examine, la estructura presentada será similar.

Para representar un fractal basta con crear una rutina que tome una forma geométrica simple y la dibuje a una determinada escala. Se repite varias veces la llamada a esta rutina de forma recursiva y a diferentes escalas.

Curva de Koch

En la generación del copo de nieve de Koch podemos ver que cada segmento es sustituido por cuatro segmentos cada uno de ellos de un tercio de la longitud del anterior.

La función recursiva que genera la curva de Koch la podemos ver en la figura para el nivel 0 (en la parte inferior) y para el nivel 1 (en la parte superior), y la podemos dibujar en el applet de la geometría de la tortuga. Recordar que para empezar un dibujo se pulsa el botón titulado Nuevo, y para ejecutar un comando hay que pulsar el botón Aplicar.

koch.gif (2086 bytes) Inicia X:-120, Y: 0
Mueve 80
Gira 60º
Mueve 80
Gira -120º
Mueve 80
Gira 60º
Mueve 80

El código de la función recursiva generaKoch que nos traza la curva de Koch es la siguiente

void generaKoch(int nivel, double distancia){
	if(nivel==0){
		tortuga.traza(distancia);
	}else{
		generaKoch(nivel-1, distancia/3);
		tortuga.gira(60.0);
		generaKoch(nivel-1, distancia/3);
		tortuga.gira(-120.0);
		generaKoch(nivel-1, distancia/3);
		tortuga.gira(60.0);
		generaKoch(nivel-1, distancia/3);
	}
}

Para obtener la figura cerrada, se ejecuta el procedimiento generaKoch en cada uno de los tres segmentos de longitud d que forman un triángulo equilátero tal como se ve en la figura.

koch_0.gif (2185 bytes)
void curvaKoch(){
	double distancia=(double)(3*wAlto-30)/(2*1.732); 
	double x=wAncho/2-distancia/2;
	double y=(distancia/3)*1.732/2+5; 
	tortuga.salta(x, y);
	generaKoch(orden, distancia);
	tortuga.gira(-120);
	generaKoch(orden, distancia);
	tortuga.gira(-120);
	generaKoch(orden, distancia);
}

En las siguientes figuras, se muestra las primeras etapas en la generación de la curva de Koch.

Curva de Peano

La función recursiva que genera la curva de Peano la podemos ver en la figura para el nivel 0 (en la parte inferior) y para el nivel 1 (en la parte superior), y la podemos dibujar en el applet de la geometría de la tortuga. Recordar que para empezar un dibujo se pulsa el botón titulado Nuevo, y para ejecutar un comando hay que pulsar el botón Aplicar.

peano.gif (2721 bytes) Inicia X:-120, Y: 0
Mueve 80
Gira -90º
Mueve 80
Gira 90º
Mueve 80
Gira 90º
Mueve 80
Mueve 80
Gira 90º
Mueve 80
Gira 90º
Mueve 80
Gira 90º
Mueve 80
Mueve 80

El código de la función recursiva generaPeano que nos traza la curva de Peano es la siguiente

void generaPeano(int nivel, double distancia){
	if(nivel==0)
		tortuga.traza(distancia);
	else{
		generaPeano(nivel-1, distancia/3);
		tortuga.gira(-90.0);
		generaPeano(nivel-1, distancia/3);
		tortuga.gira(90.0);
		generaPeano(nivel-1, distancia/3);
		tortuga.gira(90.0);
		generaPeano(nivel-1, distancia/3);
		generaPeano(nivel-1, distancia/3);
		tortuga.gira(90.0);
		generaPeano(nivel-1, distancia/3);
		tortuga.gira(90.0);
		generaPeano(nivel-1, distancia/3);
		tortuga.gira(90.0);
		generaPeano(nivel-1, distancia/3);
		generaPeano(nivel-1, distancia/3);
	}
}

La llamada a esta función generaPeano comienza situando la tortuga en el punto inicial x, y, mediante la llamada a la función miembro salta.

void curvaPeano(){
	double distancia=wAlto;
	double x=wAncho/2-wAlto/2;
	double y=wAlto/2;
	tortuga.salta(x, y);
	generaPeano(orden, distancia);
} 

En las siguientes figuras, se muestra las primeras etapas en la generación de la curva de Peano

Curva de Hilbert

Curva de Hilbert de orden cero la podemos generar como sigue en el applet de la geometría de la tortuga. Recordar que para empezar un dibujo se pulsa el botón titulado Nuevo, y para ejecutar un comando hay que pulsar el botón Aplicar

hilbert.gif (2629 bytes)  

Inicia X:-50, Y: 50
Gira
-90º
Mueve
100
Gira
90º
Mueve
100
Gira
90º
Mueve
100
Gira
–90º

Como podemos ver en las figuras, cada segmento se sustituye por otros cuatro de longitud mitad. El procedimiento recursivo es sin embargo, mucho más complejo que en los casos anteriores.

void generaHilbert(int nivel, int direccion, double distancia){
	if(nivel>0){
		tortuga.gira(-90*direccion);
		generaHilbert(nivel-1, -direccion, distancia);
		tortuga.traza(distancia);
		tortuga.gira(90*direccion);
		generaHilbert(nivel-1, direccion, distancia);
		tortuga.traza(distancia);
		generaHilbert(nivel-1, direccion, distancia);
		tortuga.gira(90*direccion);
		tortuga.traza(distancia);
		generaHilbert(nivel-1, -direccion, distancia);
		tortuga.gira(-90*direccion);
	}
}

La llamada a la función recursiva generaHilbert comienza situando la tortuga en un punto inicial x, y, mediante la función miembro salta.

void curvaHilbert(){
	double distancia=wAlto-10;
	double x=wAncho/2-wAlto/2;
	double y=5.0; // 5 de margen
	tortuga.salta(x, y);
	generaHilbert(orden+1, 1, distancia/(potencia2(orden+1)-1));
}

La función auxiliar potencia2, halla la potencia n de 2 y es muy simple de programar

private long potencia2(int n){
	long resultado=1;
	for(int i=1; i<=n; i++){
		resultado*=2;
	}
	return resultado;
}

Lo que observamos al final es una curva cuya longitud se hace cada vez más grande (tiende a infinito) en un recinto limitado. Tras un número suficientemente grande de iteraciones la curva pasará por cualquier punto del plano.

En las siguientes figuras, se muestra las primeras etapas en la generación de la curva de Hilbert.

En el siguiente applet, se visualizan las primeras etapas de la generación de las curvas de Koch, Peano y Hilbert. Se selecciona el nombre de la curva en el control selección y a continuación se pulsa la barra de desplazamiento para elegir el nivel deseado

stokesApplet aparecerá en un explorador compatible con JDK 1.1.

Bibliografía

Barallo Calonge, Javier. Geometría Fractal, Algorítmica y representación. Anaya Multimedia (1993).