Recursividad

Para empezar con lo que es la recursividad, sepamos primeramente que es, se trata mas que nada de un método que se mande a llamar a si mismo, ya sea una(Recursividad Simple) o mas veces(Recursividad Múltiple) haciendo un reemplazo de métodos directos como formulas que mas adelante les demostraré.

Ahora empezamos con algo sencillo, supongamos que queremos hacer una suma sucesiva del mismo número, la cuál esta operación equivaldrá a la multiplicación.

El método para realizar una multiplicación podría ser de la siguiente manera:

Como se dan cuenta ya mando valores estáticos de 2 y 5, mostrando como resultado 10 mandandolo de esa u otras formas similares, se supone de forma iterativa, ahora hagamoslo de multiplicación a suma sucesiva usando un ciclo FOR.

Pero esas dos fueron de forma Iterativa, ahora hagámonos de manera recursiva.

Para esto, es necesario entender que tenemos que hacer una idea sobre como funciona la recursiva,

un video:

programa de cola estatica

import java.util.Scanner;
/**
 *
 * @author omar
 */
public class Cola {

    private final int MAXIMO = 100;
    private int[] V;
    private int inicio;
    private int fin;

    public Cola() {
        this.V = new int[MAXIMO + 1];
        this.inicio = 0;
        this.fin = 0;
    }
    public boolean esVacia() {
        return inicio == fin;
    }
    public boolean esLlena() {
        return tamanio() == MAXIMO - 1;
    }
    public void agregar(int a) {
        if (esLlena()) {
            System.out.println("Cola Llena! No se puede adicionar.");
        } else {
            fin = (fin + 1) % MAXIMO;
            V[fin] = a;
        }
    }
    public int eliminar() {
        int a = Integer.MIN_VALUE;
        if (esVacia()) {
            System.out.println("Cola Vacia! No se puede eliminar.");
        } else {
            inicio = (inicio + 1) % MAXIMO;
            a = V[inicio];
        }
        return a;
    }
    public int tamanio() {
        return (fin - inicio + MAXIMO) % MAXIMO;
    }
    private void copiar(Cola B) {
        while (!B.esVacia()) {
            agregar(B.eliminar());
        }
    }
    public void leer() {
        Scanner in = new Scanner(System.in);
        System.out.print("Nro.Elementos: ");
        int n = in.nextInt();
        System.out.println("Ingrese elementos:");
        for (int i = 0; i < n; i++) {
            int a = in.nextInt();
            agregar(a);
        }
    }
    public void mostrar() {
        if (esVacia()) {
            System.out.println("Cola Vacia! No se puede mostrar nada.");
        } else {
            Cola X = new Cola();
            while (!esVacia()) {
                int a = eliminar();
                System.out.print(" " + a);
                X.agregar(a);
            }
            this.copiar(X);
            System.out.println("");
        }
    }
    public static void main(String[] args) {

    }
   
}

colas

• DEFINICION

Una cola es un tipo especial de lista abierta en la que sólo se pueden insertar nodos en uno de los extremos de la lista y sólo se pueden eliminar nodos en el otro. Además, como sucede con las pilas, las escrituras de datos siempre son inserciones de nodos, y las lecturas siempre eliminan el nodo leído.

Este tipo de lista es conocido como lista FIFO (First In First Out), el primero en entrar es el primero en salir.

• TIPOS

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.
Bicolas: son colas en donde los nodos se pueden añadir y quitar por ambos extremos. Para representar las bicolas lo podemos hacer con un array circular con Inicio y Fin que apunten a cada uno de los extremos.

• PROGRAMA

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;
}

programa fibonnacci

public class fibonnacci {
    public int fibonaci(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;
System.out.println(" "+fibinf);
        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) {
        fibonnacci fb=new fibonnacci();
        int n=0,fibinf=0,fibsup=1;
        fb.fibonaci(n, fibinf, fibsup);
    }
}

Programa de Menu con pilas

Programa:

public class Menu {
    public static void main(String[] args) {
         Pila op1= new Pila();
         Mostrar op2 = new Mostrar();
        Eliminar op3 = new Eliminar();
        int num=0;
        do{
        System.out.println("\t Operaciones con Pilas \t");
        System.out.println("1.- INSERTAR");
        System.out.println("2.- MOSTRAR");
        System.out.println("3.- ELIMINAR");
        System.out.println("4.- SALIR");
        System.out.println("Eliga su operacion");
       
        Scanner capt =new Scanner(System.in);
              num=capt.nextInt();
        switch(num){
            case 1:
                System.out.println("Insertando");
                op1.Pilam();
                break;
           case 2:
                System.out.println("Mostrando");
                op2.Most();
                break;
           case 3:
                System.out.println("Eliminando");
                op3.Elim();
               
                break;
            case 4:
                System.out.println("Saliendo");
num=7;
break;
        }
    }
         while(num<6);}
}
*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*

public class Pila {
  int NUM=4;
        int pila[]=new int[NUM];
    int tope;
   public void Pilam(){
  
      
        System.out.println("Por Favor Introduzca datos a capturar");
        Scanner captura=new Scanner(System.in);
        for ( tope = 0; tope < NUM; tope++) {
          
            pila[tope]=captura.nextInt();
        }
       
    }
}
*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*

public class Mostrar {
     Pila opm=new Pila();
    public void Most(){
       
        for (opm.tope = 3; opm.tope >=0; opm.tope--) {
            System.out.println("Datos Capturados "+opm.pila[opm.tope]);
        }
    }
}
*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*
public class Eliminar {
    Pila opm1= new Pila();
    public void Elim(){
        if (opm1.tope<5) {
            opm1.tope--;
           for (int i = 3; i >=0; i--) {
            System.out.println(" "+opm1.pila[i]);
        }
    }
    }
}

Pilas

Una pila  es una 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.
En cada momento sólo se tiene acceso a la parte superior de la pila, es decir, al último objeto apilado. La operación retirar permite la obtención de este elemento, que es retirado de la pila permitiendo el acceso al siguiente, que pasa a ser el nuevo tope.
Por analogía con objetos cotidianos, una operación apilar equivaldría a colocar un plato sobre una pila de platos, y una operación retirar a retirarlo.

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.

 Caracteristicas de una pila

• Los elementos se eliminan en orden inverso al que se insertaron El último elementos que se inserta en la pila es el primero en salir
  

EJEMPLO:

public class Pila {
     public Pila(){
  
        int NUM=4;
        int pila[]=new int[NUM];
        System.out.println("Por Favor Introduzca datos a capturar");
        Scanner captura=new Scanner(System.in);

        for (int tope = 0; tope < NUM; tope++) {

          
            pila[tope]=captura.nextInt();

        }
        for (int i = 3; i >=0; i--) {
            System.out.println("Datos Capturados "+pila[i]);
        
        }
    }

}
VIDEO: 

Listas Circulares

Definición.
Una lista circular es una lista lineal en la que el último nodo a punta al primero.
Las listas circulares evitan excepciones en la operaciones que se realicen sobre ellas.Cada nodo siempre tiene uno anterior y uno siguiente.

¿Por qué utilizar una estructura Circular?

En una lista simplemente enlazada, el movimiento siempre fluirá desde la cabeza en dirección hacia el final de la lista, pero ¿qué ocurre cuando desde el último nodo se necesita operar con el primero?, este es el punto diferencial de una estructura abierta y una cerrada.

En una lista circular:

-         No existe algún elemento que apunte a NULL

-         Se integra una estructura tipo anillo

-         Solo hay una cabeza

-         La cabeza siempre será el siguiente enlace para algún nodo

-         Se pueden llegar a crear recorridos en bucles infinitos

Declaraciones de tipos para manejar listas circulares

Los tipos que definiremos normalmente para manejar listas cerradas son los mismos que para para manejar listas abiertas:

typedef struct _nodo \{
   int dato;
   struct _nodo *siguiente;
} tipoNodo;
 
typedef tipoNodo *pNodo;
typedef tipoNodo *Lista;

tipoNodo es el tipo para declarar nodos, evidentemente.

pNodo es el tipo para declarar punteros a un nodo.

Lista es el tipo para declarar listas, tanto abiertas como circulares. En el caso de las circulares, apuntará a un nodo cualquiera de la lista.

Pueden existir Listas Circulares Simplemente Enlazadas y Doblemente Enlazadas.

Gráficamente se tendría:

                    Simplemente Enlazadas                            Doblemente enlazadas

                                                                                                                                            

-         Nótese que con simple o doble referencia, siempre se tendrá solo una cabeza

 Operaciones básicas con listas circulares

A todos los efectos, las listas circulares son como las listas abiertas en cuanto a las operaciones que se pueden realizar sobre ellas:

• Añadir o insertar elementos.
• Borrar elementos.
• Moverse a través de la lista, siguiente.

Añadir elemento en una lista circular.

Partiremos de un nodo a insertar.

El proceso es muy sencillo:

1. Hacemos que nodo->siguiente apunte a lista->siguiente.
2. Después que lista->siguiente apunte a nodo.

Eliminar un nodo en una lista circular con más de un elemento

                                                          Lista con más de un elemento

1. El primer paso es conseguir que lista apunte al nodo anterior al que queremos eliminar. Esto se consigue haciendo que lista valga lista->siguiente mientras lista->siguiente sea distinto de nodo.
2. Hacemos que lista->siguiente apunte a nodo->siguiente.
3. Eliminamos el nodo.