LENGUAJES DE PROGRAMACIÓN  
 
 
Empezando con Java

EMPEZANDO CON JAVA

 
 

 

6.6. Recursividad.

 

anterior :: indice :: siguiente

 

6.1. Introducción.

6.2. Declaración de métodos.

6.3. Parametros de los métodos.

 

6.4. Parametros vargs o parametros arbitrarios.

6.5. Sobrecarga de métodos.

6.6. Recursividad.

 

 

 

 

La recursividad sucede cuando un método se ejecuta a sí mismo. Cada vez que el método se ejecuta a sí mismo, se crean sus parámetros y variables locales en la Pila, por cada ejecución que se realice. Cuando se hace un método con recursividad, se debe usar una condición para detener las ejecuciones sucesivas del método. Por ejemplo el siguiente programa:

 

 
import java.util.Locale;
import java.util.Scanner;
import java.lang.Math;

class Ejemplo01{
    static int n;

    static void Infinito(){
      System.out.printf("a %n");
      Infinito();
    }

 public static void main(String[] args){
    Infinito();
    System.out.printf("FIN DEL PROGRAMA %n");
  }
}
 

Código fuente 10: Recursividad Infinito.

 

Realiza una recursividad del método Infinito, pero el programa se ejecutará hasta que este deje de funcionar por falta de memoria en la Pila. El programa deja de funcionar cuando la Pila se llene, finalizando el programa bruscamente con un mensaje de error, impidiendo que se muestre el mensaje : FIN del programa.

Debido a que el método se ejecuta sucesivamente a sí mismo, sin ninguna condición entonces no existe la posibilidad de terminar con el método infinito que ejecuto al anterior, y eso hace que no se pueda destruir o liberar espacio en la Pila.

El siguiente programa es parecido al anterior, pero usa una condición para controlar la recursividad. A continuación el ejemplo:

 

 
import java.util.Locale;
import java.util.Scanner;
import java.lang.Math;

class Ejemplo02{
    static int n;

    static void Finito(int c){
      System.out.printf("%d %n",c);
      c+=1;
      if (c<=9) Finito(c);
    }

 public static void main(String[] args){
    Finito(0);
    System.out.printf("FIN DEL PROGRAMA %n");
  }
}
 

Código fuente 11: Recursividad controlada por una condición.

 

En este caso el método Finito, usa una condición y se ejecuta asimismo sólo 9 veces, evitando que la pila se llene y el programa pueda continuar con su funcionamiento, mostrando el mensaje: FIN del programa.

La recursividad que hemos visto se conoce como recursividad simple o directa, existe otra caso de recursividad, que se conoce como recursividad indirecta o circular, esta se produce cuando un método ejecuta a otra, que a su vez terminará ejecutando de nuevo al primer método. El siguiente programa muestra un ejemplo de recursión circular o indirecta:

 

 
import java.util.Locale;
import java.util.Scanner;
import java.lang.Math;

class Ejemplo03{
    static int n;

    static void ProcedimientoA(int c){
      System.out.printf("%d %n",c);
      if (c>0) ProcedimientoB(c);
    }

    static void ProcedimientoB(int c){
      ProcedimientoA(c-1);
    }

 public static void main(String[] args){
    ProcedimientoA(20);
  }

}
 

Código fuente 12: Recursividad indirecta o circular.

 

Algunos problemas matemáticos se pueden implementar con el uso de la recursividad simple o directa, como ejemplo tenemos el cálculo de factoriales, obtener el término n de la serie de Fibonacci, y el algoritmo recursivo de Ackermann. A continuación la implementación de los problemas matemáticos mencionados:

 

 
import java.util.Locale;
import java.util.Scanner;
import java.lang.Math;

class Ejemplo04{
    static int n;

    static int Factorial(int n){
      if (n==0) {return 1;}
      else {return n*Factorial(n-1);}
    }

    static int Fibonacci(int n){
      if (n<2) {return n;}
      else {return Fibonacci(n-1)+Fibonacci(n-2);}
    }

    static int Ack(int m, int n){
      if (m==0) {return n+1;}
      else if (n==0) {return Ack(m-1,1);}
      else {return Ack(m-1,Ack(m,n-1));}
    }

 public static void main(String[] args){
    System.out.printf("%d %n",Factorial(5));
    System.out.printf("%d %n",Fibonacci(20));
    System.out.printf("%d %n",Ack(3,1));
  }
}
 

Código fuente 13: Ejemplos de recursividad, Factorial, Fibonacci y Ackerman.

 

Las descripciones recursivas en las matemáticas se usan para describir algo, de tal manera que un ser humano sea capaz de entenderlo. Es por eso que son descripciones breves y concisas, para que se comprendan con relativa facilidad. Pero, cuando usamos la recursividad en la programación, nos encontramos con una serie de factores como la falta de memoria en la Pila, que impiden poner en práctica las descripciones recursivas. En esos casos es recomendable convertir un método recursivo en un método iterativo, siempre y cuando sea posible. A modo de ejemplo el cálculo del término n de la serie fibonacci en un método iterativa:

 

 
import java.util.Locale;
import java.util.Scanner;
import java.lang.Math;

class Ejemplo05{

    static int Fibonacci(int n){
      int i,j,c,aux;
      i=1;
      j=0;
      for (c=1;c<=n;c++)
       {
         aux=j+i;
         i=j;
         j=aux;
        };
      return j;
    }

 public static void main(String[] args){
    System.out.printf("%d %n",Fibonacci(20));
  }

}
 

Código fuente 14: Ejemplo iterativo de fibonacci.

 

Otros ejemplos de recursividad directa o simple para mencionar serían: calcular el Máximo Común Divisor, las Torres de Hanoi, la suma de los elementos de un arreglo, Quick Sort, etc.

 

Delicious

 

anterior :: indice :: siguiente

 

 
 

  SUGERENCIAS