Como ejemplo útil se puede presentar el calculo de números factoriales. Él factorial de 0 es, por definición, 1. Los factoriales de números mayores se calculan mediante la multiplicación de 1 * 2 * …, incrementando el número de 1 en 1 hasta llegar al número para el que se está calculando el factorial.
Para entender mejor lo que en realidad es el concepto de recursión veamos un poco lo referente a la secuencia de Fibonacci.
Principalmente habría que aclarar que es un ejemplo menos familiar que el del factorial, que consiste en la secuencia de enteros.
0,1,1,2,3,5,8,13,21,34,...,
Cada elemento en esta secuencia es la suma de los precedentes (por ejemplo 0 + 1 = 0, 1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, ...) sean fib(0) = 0, fib (1) = 1 y así sucesivamente, entonces puede definirse la secuencia de Fibonacci mediante la definición recursiva (define un objeto en términos de un caso mas simple de si mismo):fib (n) = n if n = = 0 or n = = 1
fib (n) = fib (n - 2) + fib (n - 1) if n >= 2
Por ejemplo, para calcular fib (6), puede aplicarse la definición de manera recursiva para obtener:
Fib (6) = fib (4) + fib (5) = fib (2) + fib (3) + fib (5) = fib (0) + fib (1) + fib (3) + fib (5) = 0 + 1 fib (3) + fib (5)
- + fib (1) + fib (2) + fib(5) =
- + 1 + fib(0) + fib (1) + fib (5) =
- + 0 + 1 + fib(5) = 3 + fib (3) + fib (4) = 3 + 1 + fib (0) + fib (1) + fib (4) =
- + fib (1) + fib (2) + fib (4) =
- + 0 + 1 + fib (2) + fib (3) = 5 + fib (0) + fib (1) + fib (3) =
- + 0 + 1 + fib (1) + fib (2) = 6 + 1 + fib (0) + fib (1) =
- + 0 + 1 = 8
If (n < = 1)
return (n);
lofib = 0 ;
hifib = 1 ;
for (i = 2; i < = n; i ++)
{
x = lofib ;
lofib = hifib ;
hifib = x + lofib ;
} /* fin del for*/
return (hifib) ;
Compárese el numero de adiciones (sin incluir los incrementos de la variable índice, i) que se ejecutan para calcular fib (6) mediante este algoritmo al usar la definición recursiva. En el caso de la función factorial, tienen que ejecutarse el mismo numero de multiplicaciones para calcular n! Mediante ambos métodos: recursivo e iterativo. Lo mismo ocurre con el numero de sumas en los dos métodos al calcular la multiplicación. Sin embargo, en el caso de los números de Fibonacci, el método recursivo es mucho mas costoso que el iterativo.
Cadenas recursivas:
Una función recursiva no necesita llamarse a sí misma de manera directa. En su lugar, puede hacerlo de manera indirecta como en el siguiente ejemplo:
a (formal parameters) b (formal parameters)
{ {
. .
b (arguments); a (arguments);
. .
} /*fin de a*/ } /*fin de b*/
En este ejemplo la función a llama a b, la cual puede a su vez llamar a a, que puede llamar de nuevo a b. Así, ambas funciones a y b, son recursivas, dado que se llamas a sí mismo de manera indirecta. Sin embargo, el que lo sean no es obvio a partir del examen del cuerpo de una de las rutinas en forma individual. La rutina a, parece llamar a otra rutina b y es imposible determinar que se puede llamar así misma de manera indirecta al examinar sólo a a.
Pueden incluirse mas de dos rutinas en una cadena recursiva. Así, una rutina a puede llamar a b, que llama a c, ..., que llama a z, que llama a a. Cada rutina de la cadena puede potencialmente llamarse a sí misma y, por lo tanto es recursiva.
APLICACIONES
uno de los ejemplos de recursividad es el juego muy conocido de LAS TORRES DE HANOI://******************************************************************** // hanoi.java // aporte de @ohk // para elhacker.net //******************************************************************** import java.applet.*; import java.awt.event.*; import java.awt.*; //******************************************************************** public class hanoi extends Applet implements Runnable { Graphics g; static public Image fondo; static public int ancho; static public int alto; static public int demora = 200; private boolean imagen_cargada = false; private int total_discos = 3; private Thread mi_hilo; private boolean hilo_iniciado = false; private Label label; private TextField resultado; String salida = ""; int contador = 0; torre t []; int torre_origen = 0; int torre_destino = 2; //---------------------------------------------------------------- public void init () { label = new Label ("Comportamiento de las Torres de Hanoi"); label.setFont (new java.awt.Font ("Georgia Ref", java.awt.Font.BOLD, 20)); resultado = new TextField (40); resultado.setFont (new java.awt.Font ("Georgia Ref", java.awt.Font.BOLD, 15)); //Container contString = getContentPane (); //contString.setLayout (new FlowLayout ()); resultado.setEnabled (false); //contString.add (new ScrollPane (resultado)); g = getGraphics (); String parametro; parametro = getParameter ("TOTAL"); if (parametro != null) total_discos = Integer.parseInt (parametro); parametro = getParameter ("DEMORA"); if (parametro != null) demora = Integer.parseInt (parametro); ancho = size ().width; alto = size ().height; fondo = getImage (getCodeBase (), "egipto.gif"); Image imagenFueraPant = createImage (ancho, alto); Graphics CGFueraPant = imagenFueraPant.getGraphics (); CGFueraPant.drawImage (fondo, 0, 0, this); t = new torre [3]; t [0] = new torre (g); t [1] = new torre (g); t [2] = new torre (g); for (int i = 0 ; i < total_discos ; i++) { t [0].agregar (i); } add (label); add (resultado); } //---------------------------------------------------------------- public boolean imageUpdate (Image img, int infoflags, int x, int y, int ancho, int alto) { if (infoflags == ALLBITS) { imagen_cargada = true; repaint (); return false; } else return true; } //---------------------------------------------------------------- public void paint (Graphics g) { if (!imagen_cargada) showStatus ("Torre de Hanoi: cargando imagen"); else { if (hilo_iniciado) if (mi_hilo.isAlive ()) showStatus ("Torres de Hanoi: Corriendo"); else showStatus ("Torres de Hanoi: Haga clic otra vez para reiniciar"); else showStatus ("Torres de Hanoi: Haga clic para iniciar"); ancho = size ().width; alto = size ().height; g.drawImage (fondo, 0, 0, ancho, alto, this); int x_inc = ancho / 10; t [0].paint (x_inc * 1, x_inc * 2, alto); t [1].paint (x_inc * 4, x_inc * 2, alto); t [2].paint (x_inc * 7, x_inc * 2, alto); } } //---------------------------------------------------------------- public boolean mouseDown (Event evt, int x, int y) { if (!hilo_iniciado || !mi_hilo.isAlive ()) { mi_hilo = new Thread (this); mi_hilo.start (); showStatus ("Torre de Hanoi: Corriendo"); hilo_iniciado = true; resuelve_hanoi (total_discos, torre_origen + 1, torre_destino + 1); } return true; } //---------------------------------------------------------------- public void run () { mover_torre (total_discos, torre_origen, torre_destino, 1); int temp = torre_destino; torre_destino = torre_origen; torre_origen = temp; showStatus ("Torre de Hanoi: Haga clic otra vez para reiniciar"); } //---------------------------------------------------------------- private void mover_torre (int discos, int origen, int destino, int temporal) { if (discos > 0) { mover_torre (discos - 1, origen, temporal, destino); mover_disco (origen, destino); mover_torre (discos - 1, temporal, destino, origen); } } //---------------------------------------------------------------- private void mover_disco (int origen, int destino) { int disco = t [origen].pop (); t [destino].push (disco); } public void resuelve_hanoi (int n, int inicial, int finalizar) { int libre = 0; if (n == 1) { resultado.setText (" Mover disco superior de la torre " + inicial + " a la torre " + finalizar); } else { //Determinar cual es la aguja libre if (inicial != 1 && finalizar != 1) libre = 1; else if (inicial != 2 && finalizar != 2) { libre = 2; } else libre = 3; //Primer subproblema:mover n-1 discos de inicial a libre resuelve_hanoi (n - 1, inicial, libre); //Transferir el disco grande a su posicion final try { Thread.sleep (3200); } catch (InterruptedException e) { } ; resultado.setText (" Mover disco superior de la torre " + inicial + " a la torre " + finalizar); try { Thread.sleep (3200); } catch (InterruptedException e) { } ; //Segundo subproblema: mover n-1 discos de libre a final resuelve_hanoi (n - 1, libre, finalizar); } } }
