viernes, 17 de noviembre de 2017

Recursividad en Java

La recursividad es una técnica potente de programación que puede utilizarse en lugar de la iteración para resolver determinados tipos de problemas.
Por ejemplo, para escribir un método que calcule el factorial de un número entero no negativo, podemos hacerlo a partir de la definición de factorial:
Si n = 0 entonces
0! = 1
si n>0 entonces
n! = n * (n–1) * (n–2) * ... * 3 * 2 * 1 
Esto dará lugar a una solución iterativa en Java mediante un bucle for:
// Método Java no recursivo para calcular el factorial de un número
public double factorial(int n){
    double fact=1;
    int i;
    if (n==0)
        fact=1;
    else
        for(i=1;i<=n;i++)
            fact=fact*i;
 return fact;
}
Pero existe otra definición de factorial en función de sí misma:
0! = 1
n! = n · (n – 1)! ,    si n > 0   (El factorial de n es n por el factorial de n-1)
Esta definición da lugar a una solución recursiva del factorial en Java:
// Método Java recursivo para calcular el factorial de un número
public double factorial(int n){
    if (n==0)
        return 1;
    else
        return n*(factorial(n-1));
}

Un método es recursivo cuando entre sus instrucciones se encuentra una llamada a sí mismo.
La solución iterativa es fácil de entender. Utiliza una variable para acumular los productos y obtener la solución. En la solución recursiva se realizan llamadas al propio método con valores de n cada vez más pequeños para resolver el problema.
Cada vez que se produce una nueva llamada al método se crean en memoria de nuevo las variables y comienza la ejecución del nuevo método.
Para entender el funcionamiento de la recursividad, podemos pensar que cada llamada supone hacerlo a un método diferente, copia del original, que se ejecuta y devuelve el resultado a quien lo llamó.
En la figura siguiente podemos ver como sería la ejecución del programa Java anterior para calcular el factorial de 3. 


·         Uno o más casos base: casos para los que existe una solución directa.
·         Una o más llamadas recursivas: casos en los que se llama sí mismo


Caso base: Siempre ha de existir uno o más casos en los que los valores de los parámetros de entrada permitan al método devolver un resultado directo. Estos casos también se conocen como solución trivial del problema.
En el ejemplo del factorial el caso base es la condición:
if (n==0)
     return 1;
si n=0 el resultado directo es 1    No se produce llamada recursiva

Llamada recursiva: Si los valores de los parámetros de entrada no cumplen la condición del caso base se llama recursivamente al método. En las llamadas recursivas el valor del parámetro en la llamada se ha de modificar de forma que se aproxime cada vez más hasta alcanzar al valor del caso base.
En el ejemplo del factorial en cada llamada recursiva se utiliza n-1
return n * ( factorial(n-1) );
por lo que en cada llamada el valor de n se acerca más a 0 que es el caso base.

La recursividad es especialmente apropiada cuando el problema a resolver (por ejemplo calculo del factorial de un número) o la estructura de datos a procesar (por ejemplo los árboles) tienen una clara definición recursiva.
No se debe utilizar la recursión cuando la iteración ofrece una solución obvia. Cuando el problema se pueda definir mejor de una forma recursiva que iterativa lo resolveremos utilizando recursividad.
Para medir la eficacia de un algoritmo recursivo se tienen en cuenta tres factores:
  • Tiempo de ejecución
  • Uso de memoria
  • Legibilidad y facilidad de comprensión
Las soluciones recursivas suelen ser más lentas que las iterativas por el tiempo empleado en la gestión de las sucesivas llamadas a los métodos. Además consumen más memoria ya que se deben guardar los contextos de ejecución de cada método que se llama.

A pesar de estos inconvenientes, en ciertos problemas, la recursividad conduce a soluciones que son mucho más fáciles de leer y comprender que su correspondiente solución iterativa. En estos casos una mayor claridad del algoritmo puede compensar el coste en tiempo y en ocupación de memoria.

De todas maneras, numerosos problemas son difíciles de resolver con soluciones iterativas, y sólo la solución recursiva conduce a la resolución del problema (por ejemplo, Torres de Hanoi o recorrido de Árboles).

martes, 14 de noviembre de 2017

Colas

Las colas también son llamadas FIFO (First In First Out), que quiere decir “el primero que entra es el primero que sale” como por ejemplo:
La cola del autobús
La cola de la impresora
La cola del banco.

La cola de comedor

Se entiende por cola una estructura de datos en la que se añaden nuevos ítems en un extremo y se suprimen ítems viejos en el opuesto.




Utilizando para colas: Offer - Poll


En conclusión 
Una lista se comporta como una cola si las inserciones las hacemos al final y las extracciones las hacemos por el frente de la lista. También se las llama listas FIFO (First In First Out - primero en entrar primero en salir)



autor:Ing. García Villegas, Christian

PILAS

Una lista se comporta como una pila si las inserciones y extracciones las hacemos por un mismo lado de la lista. También se las llama listas LIFO (Last In First Out - último en entrar primero en salir).
Gracias a las pilas es posible el uso de la recursividad. La variable que llama al mismo procedimiento en el que está, habrá que guardarla así como el resto de variables de la nueva llamada, para a la vuelta de la recursividad ir sacándolas, esto es posible a la implementación de pilas.
Las pilas son estructuras de datos que tienes dos operaciones básicas:
Push (para insertar un elemento)
Pop (para extraer un elemento).
Peek (Muestra si extraer) 
En las pilas los ítems se añaden y se eliminan en el mismo extremo.
Las pilas se conocen también como colas LIFO (último en entrar, primero en salir) al describir  el tipo de cola básico.








autor: Ing. García Villegas, Christian




Creación de un nodo de entrada en Java

Un nodo de entrada se utiliza para recibir un mensaje en un flujo de mensajes, normalmente de un origen no soportado por los nodos de entr...