RECURSIVIDAD

Recursividad
La recursividad es una función que se llama a sí misma para dividir un problema en problemas más sencillos, el método recursivo debe estar compuesto de una caso base para el cual ya se conoce un resultado y una llamada al mismo método con una versión ligeramente más sencilla del problema inicial.


Ejemplo 1, factoriales:
Para todo n entero natural, se llama factorial n (n!) al producto de todos los enteros entre 1 y n:

n	n!
1	1	1	1
2	2 × 1	= 2 × 1!	= 2
3	3 × 2 × 1	= 3 × 2!	= 6
4	4 × 3 × 2 × 1	= 4 × 3!	= 24
5	5 × 4 × 3 × 2 × 1	= 5 × 4!	= 120
6	etc	etc

Código para los factoriales:

code

1       2 3 4 5 6

<BR> public void factoriales(long n){<P></P> <P> if(n==1) return 1;</P> <P> else return n*factoriales(n-1);<BR> }</P> <P></P>

El método factoriales se llama a sí mismo disminuyendo cada vez el numero inicial en una unidad hasta que llega a valer 1 y por lo tanto alcanza el caso base, en ese momento se devuelven todas las llamadas recursivas realizas al método factoriales retornando el valor del actual multiplicado por el valor anterior.

Ejemplo 2, Fibonachi:

La sucesion de Fibonachi comienza por 0 y 1, y cada numero siguiente es la

suma de los dos anteriores:

0,1,1,2,3,5,8,13,21,34,55,8,9

Código:

code

1 2           3 4 5 6

<BR> public void fibonachi(long n){<P></P> <P> if(n==0 || n==1) return n;</P> <P> else return fibonachi(n-2)+fibonachi(n-1);</P> <P>}</P> <P></P>

Este método esta compuesto de dos casos bases, y de dos llamadas recursivas al método, a esto se le denomina recursividad mútliple, a diferencia del método factoriales que sólo hace una llamada recursiva y se denomina recursividad simple. En ambos casos es de tipo directa, también es posible efectuar recursión indirectamente: una método puede llamar a otro quien, a su vez, acabe llamando al primero.

Programas

   public int Fibonacci (int n, int fibinf, int fibsup)
    {
    Scanner teclado = new Scanner (System.in);
        System.out.println("Ingrese El Numero");
        n = teclado.nextInt();
        System.out.println("-----------------");
        if ((n==0)||(n==1))
        {
            System.out.println("La Suma Es:"+n);
            return n;
        }
        fibinf=0;
        fibsup=1;
        for(int i=2; i<n; i++){
            int x;
            x= fibinf;
            fibinf = fibsup;
            fibsup = x + fibinf;
            System.out.println(""+fibsup);
        }
        return (fibsup);
    }
        public static void main(String[] args) {

        fibonacci1 fb = new fibonacci1 ();
       int n=0, fibinf=0, fibsup=0;
       fb.Fibonacci (n,fibinf,fibsup);

}
}

COLAS

Cola

Una cola es una estructura de datos, caracterizada por ser una secuencia de elementos en la que la operación de inserción push se realiza por un extremo y la operación de extracción pop por el otro. También se le llama estructura FIFO (del inglés First In First Out), debido a que el primer elemento en entrar será también el primero en salir.

Las colas se utilizan en sistemas informáticos, transportes y operaciones de investigación (entre otros), dónde los objetos, personas o eventos son tomados como datos que se almacenan y se guardan mediante colas para su posterior procesamiento. Este tipo de estructura de datos abstracta se implementa en lenguajes orientados a objetos mediante clases, en forma de listas enlazadas.

Usos concretos de la cola

La particularidad de una estructura de datos de cola es el hecho de que sólo podemos acceder al primer y al último elemento de la estructura. Así mismo, los elementos sólo se pueden eliminar por el principio y sólo se pueden añadir por el final de la cola.

Ejemplos de colas en la vida real serían: personas comprando en un supermercado, esperando para entrar a ver un partido de béisbol, esperando en el cine para ver una película, una pequeña peluquería, etc. La idea esencial es que son todos líneas de espera.

Tipos de colas

• Colas circulares (anillos): en las que el último elemento y el primero están unidos.

• Colas de prioridad: En ellas, los elementos se atienden en el orden indicado por una prioridad asociada a cada uno. Si varios elementos tienen la misma prioridad, se atenderán de modo convencional según la posición que ocupen. Hay 2 formas de implementación:

1. Añadir un campo a cada nodo con su prioridad. Resulta conveniente mantener la cola ordenada por orden de prioridad.
2. Crear tantas colas como prioridades haya, y almacenar cada elemento en su cola.

• Bicolas: son colas en donde los nodos se pueden añadir y quitar por ambos extremos; se les llama DEQUE (Double Ended QUEue). Para representar las bicolas lo podemos hacer con un array circular con Inicio y Fin que apunten a cada uno de los extremos. Hay variantes:

• Bicolas de entrada restringida: Son aquellas donde la inserción sólo se hace por el final, aunque podemos eliminar al inicio ó al final.

• Bicolas de salida restringida: Son aquellas donde sólo se elimina por el final, aunque se puede insertar al inicio y al final.

Información adicional

En caso de estar vacía borrar un elemento sería imposible hasta que no se añade un nuevo elemento. A la hora de añadir un elemento podríamos darle una mayor importancia a unos elementos que a otros (un cargo VIP) y para ello se crea un tipo de cola especial que es la cola de prioridad. (Ver cola de prioridad).

Aplicaciones

•Las colas se utilizan en muchos algoritmos y en

situaciones en las que el rendimiento de dos
sistemas que se cruzan datos entre sí es más eficiente
cuando no se intercambian indicativos y señales de

control (handshaking) en cada transferencia.

•También almacenan temporalmente la transferencia

de información, lo que permite procesarla

en origen y en destino a tasas independientes.

•La cola de eventos en Java es un buen ejemplo.

•Tipos derivados: colas de prioridad y flujos de datos

 

Operaciones Básicas

• Crear: se crea la cola vacía.
• Encolar (añadir, entrar, insertar): se añade un elemento a la cola. Se añade al final de esta.
• Desencolar (sacar, salir, eliminar): se elimina el elemento frontal de la cola, es decir, el primer elemento que entró.
• Frente (consultar, front): se devuelve el elemento frontal de la cola, es decir, el primer elemento que entró.

ejemplos

Colas en JAVA

public void inserta(Elemento x) {
        Nodo Nuevo;
        Nuevo = new Nodo(x, null);
        if (NodoCabeza == null) {
            NodoCabeza = Nuevo;
        } else {
            NodoFinal.Siguiente = Nuevo;
        }
        NodoFinal = Nuevo;
    }
 
    public Elemento cabeza() throws IllegalArgumentException {
        if (NodoCabeza == null) {
            throw new IllegalArgumentException();
        } else {
            return NodoCabeza.Info;
        }
    }
 
    public Cola() {
    // Devuelve una Cola vacía
        NodoCabeza = null;
        NodoFinal = null;
    }

PILAS

Concepto.
Una pila (stack en inglés) es una lista ordinal o estructura de datos en la que el modo de acceso a sus elementos es de tipo LIFO (del inglés Last In First Out, último en entrar, primero en salir) que permite almacenar y recuperar datos. Esta estructura se aplica en multitud de ocasiones en el área de informática debido a su simplicidad y ordenación implícita de la propia estructura.

Para el manejo de los datos se cuenta con dos operaciones básicas: apilar (push), que coloca un objeto en la pila, y su operación inversa, retirar (o desapilar, pop), que retira el último elemento apilado.
Una pila (stack en inglés) es una lista ordinal o estructura de datos en la que el modo de acceso a sus elementos es de tipo LIFO (del inglés Last In First Out, último en entrar, primero en salir) que permite almacenar y recuperar datos. Esta estructura se aplica en multitud de ocasiones en el área de informática debido a su simplicidad y ordenación implícita de la propia estructura.

+

Para el manejo de los datos se cuenta con dos operaciones básicas: apilar (push), que coloca un objeto en la pila, y su operación inversa, retirar (o desapilar, pop), que retira el último elemento apilado.





Pila de llamadas
La Pila de llamadas es un segmento de memoria que utiliza esta estructura de datos para almacenar información sobre las llamadas a subrutinas actualmente en ejecución en un programa en proceso.
Cada vez que una nueva subrutina es llamada, se apila una nueva entrada con información sobre ésta tal como sus variables locales. En especial, se almacena aquí el punto de retorno al que regresar cuando esta subrutina termine (para volver a la subrutina anterior y continuar su ejecución después de esta llamada)..


Pila como tipo abstracto de datos
A modo de resumen tipo de datos, la pila es un contenedor de nodos y tiene dos operaciones básicas: push (o apilar) y pop (o desapilar). 'Push' añade un nodo a la parte superior de la pila, dejando por debajo el resto de los nodos. 'Pop' elimina y devuelve el actual nodo superior de la pila. Una metáfora que se utiliza con frecuencia es la idea de una pila de platos en una cafetería con muelle de pila. En esa serie, sólo la primera placa es visible y accesible para el usuario, todas las demás placas permanecen ocultas. Como se añaden las nuevas placas, cada nueva placa se convierte en la parte superior de la pila, escondidos debajo de cada plato, empujando a la pila de placas. A medida que la placa superior se elimina de la pila, la segunda placa se convierte en la parte superior de la pila. Dos principios importantes son ilustrados por esta metáfora: En primer lugar la última salida es un principio, la segunda es que el contenido de la pila está oculto. Sólo la placa de la parte superior es visible, por lo que para ver lo que hay en la tercera placa, el primer y segundo platos tendrán que ser retirados.





Operaciones
Una pila cuenta con 2 operaciones imprescindibles: apilar y desapilar, a las que en las implementaciones modernas de las pilas se suelen añadir más de uso habitual.

• Crear: se crea la pila vacía.
• Apilar: se añade un elemento a la pila.(push)
• Desapilar: se elimina el elemento frontal de la pila.(pop)
• Cima: devuelve el elemento que esta en la cima de la pila. (top o peek)
• Vacía: devuelve cierto si la pila está vacía o falso en caso contrario.

Implementación

Un requisito típico de almacenamiento de una pila de n elementos es O(n). El requisito típico de tiempo de O(1) las operaciones también son fáciles de satisfacer con un array o con listas enlazadas simples.
La biblioteca de plantillas de C++ estándar proporciona una "pila" clase templated que se limita a sólo apilar/desapilar operaciones. Java contiene una biblioteca de la clase Pila que es una especialización de Vector. Esto podría ser considerado como un defecto, porque el diseño heredado get () de Vector método LIFO ignora la limitación de la Pila.


Aplicaciones de las pilas
Las pilas son utilizadas ampliamente para solucionar una amplia variedad de problemas. Se utiliza en compiladores, sistemas operativos y en programas de aplicación.
(Suponemos que $ no está ni en W ni en W´)

• Ejemplo1: Leer una secuencia de caracteres desde teclado

e imprimirla al revés

• Ejemplo2: Verificar si una cadena de caracteres está

balanceada en paréntesis o no

abc(defg(ijk))(l(mn)op)qr SI

abc(def))ghij(kl)m NO

• Ejemplo3: Reconocimiento del Lenguaje,

L={W$W´ / W es una cadena de caracteres y W´es su

inversa}







PROGRAMAS

EJEMPLO1

package pilas;

import java.util.Scanner;

/**

 *

 * @author ALUMNO

 */

public class PilaEstatica {

    public static void main(String[] args) {

        int dato;

        int pila[]=new int[5];

        Scanner captura=new Scanner(System.in);

        for(int tope=0;tope<5;tope++)

        {

            System.out.println("proprcione datos para pila");

            dato=captura.nextInt();

            pila[tope]=dato;

        }

        for (int tope=5;tope>=0;tope--)

            System.out.println("la pila tiene los siguientes datos:"+pila[tope]);

    }

}

EJEMPLO2

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

/**
 *
 * @author alumno
 */
import java.util.Scanner;
public class Pilas {
    public static void main(String[] args) {
        int tope=0;
        int dato;
        int op;
        int pila[]=new int[5];
        Scanner captura=new Scanner(System.in);
        do{
        System.out.println("\t Menu \t");
        System.out.println("Operaciones Con Pilas");
        System.out.println("1.- Insertar");
        System.out.println("2.- Eliminar");
        System.out.println("3.- Mostrar");
        System.out.println("4.- Salir");
        System.out.println("\n");
        System.out.println("Elija La Operacion Que Desee");
        op=captura.nextInt();
        switch(op){
            case 1:
                System.out.println("Inserte Numero");
                dato=captura.nextInt();
                insertar(dato);
                break;
            case 2:
                break;
            case 3:
                break;
            case 4:
                break;
            }
        }while (op!=4);
       
        public int insertar (int dato){
            if(tope>4){
                System.out.println("La Pila Esta Llena");
            }
            else {
                tope++;
                pila[tope]=dato;
            }
            return pila [tope];
    }

}