Recursividad

En el tema de hoy se analizara....

Recursividad

-Concepto

Recurrencia, recursión o recursividad es la forma en la cual se especifica un proceso basado en su propia definición. Siendo un poco más precisos, y para evitar el aparente círculo sin fin en esta definición:
Un problema que pueda ser definido en función de su tamaño, sea este N, pueda ser dividido en instancias más pequeñas (< N) del mismo problema y se conozca la solución explícita a las instancias más simples, lo que se conoce como casos base, se puede aplicar inducción sobre las llamadas más pequeñas y suponer que estas quedan resueltas.
Para que se entienda mejor a continuación se exponen algunos ejemplos:

• Factorial(x: Entero): Sea N := x el tamaño del problema, podemos definir el problema de forma recurrente como x*Factorial(x - 1); como el tamaño de Factorial(x - 1) es menor que N podemos aplicar inducción por lo que disponemos del resultado. El caso base es el Factorial(0) que es 1.

• Ordenación por fusión(v: vector): Sea N := tamaño(v), podemos separar el vector en dos mitades. Estas dos mitades tienen tamaño N/2 por lo que por inducción podemos aplicar la ordenación en estos dos subproblemas. Una vez tenemos ambas mitades ordenadas simplemente debemos fusionarlas. El caso base es ordenar un vector de 0 elementos, que está trivialmente ordenado y no hay que hacer nada.

En estos ejemplos podemos observar como un problema se divide en varias (>= 1) instancias del mismo problema, pero de tamaño menor gracias a lo cual se puede aplicar inducción, llegando a un punto donde se conoce el resultado (el caso base)..

-Imagenes
Veremos algunas imagenes que demuestre que es recursividad

Imagen de cacao

Anuncio de cacao con una imagen recursiva. La mujer muestra un paquete idéntico al del propio anuncio, conteniendo así a otra mujer que muestra otro paquete más pequeño, de forma recursiva.

Triangulos repetidos

Imagen recursiva formada por un triángulo. Cada triángulo está compuesto de otros más pequeños, compuestos a su vez de la misma estructura recursiva.

Es amor es todo

Quien come a quien

Recursividad infinita

Quien mira a quien

-Aplicacion

Factorial -- n! = n × (n-1)!

    -
Para todo número natural n, se llama n factorial o factorial de n al producto de todos los naturales desde 1 hasta n:

Que de un modo resumido, se puede expresar como:

Sucesión de Fibonacci -- f(n) = f(n-1) + f(n-2)

     - En matemática, la sucesión de Fibonacci es la siguiente sucesión infinita de números naturales:

La sucesión inicia con 0 y 1, y a partir de ahí cada elemento es la suma de los dos anteriores.
A cada elemento de esta sucesión se le llama número de Fibonacci. Esta sucesión fue descrita en Europa por Leonardo de Pisa, matemático italiano del siglo XIII también conocido como Fibonacci. Tiene numerosas aplicaciones en ciencias de la computación, matemáticas y teoría de juegos. También aparece en configuraciones biológicas, como por ejemplo en las ramas de los árboles, en la disposición de las hojas en el tallo, en la flora de la alcachofa y en el arreglo de un cono.

Números de Catalan -- C(2n, n)/(n+1)

     -
En combinatoria, los números de Catalan forman una secuencia de números naturales que aparece en varios problemas de conteo que habitualmente son recursivos. Obtienen su nombre del matemático belga Eugène Charles Catalan (1814–1894).
El n-ésimo número de Catalan se obtiene, aplicando coeficientes binomiales, a partir de la siguiente fórmula:

• Las aplicaciones sucesivas de un operador binario pueden representarse con un árbol binario. En este caso, C_n es el número de árboles binarios de n + 1 hojas, en los que cada nodo tiene cero o dos hijos:

• C_n es el número de caminos monótonos que se pueden trazar a través de las líneas de una malla de n × n celdas cuadradas, de forma que nunca se cruce la diagonal. Un camino monótono es aquél que empieza en la esquina inferior izquierda y termina en la esquina superior derecha, y consiste únicamente en tramos que apuntan hacia arriba o hacia la derecha. El recuento de estos caminos es equivalente a contar palabras de Dyck: X significa "moverse a la derecha" e Y significa "moverse hacia arriba". Los siguientes diagramas muestran el caso n = 3:

Las Torres de Hanói

    -Es un rompecabezas o juego matemático inventado en 1883 por el matemático francés Éduard Lucas.^[1] Este solitario se trata de un juego de ocho discos de radio creciente que se apilan insertándose en una de las tres estacas de un tablero. El objetivo del juego es crear la pila en otra de las estacas siguiendo unas ciertas reglas. El problema es muy conocido en la ciencia de la computación y aparece en muchos libros de texto como introducción a la teoría de algoritmos.

Función de Ackermann

En teoría de la computación, la función de Ackermann es una función recursiva que toma dos números naturales como argumentos y devuelve un único número natural. Como norma general se define como sigue:

Ahora bien, a efectos pedagógicos se puede utilizar una versión alternativa:

Codigo
- Aqui le anexo un codigo en JAVA de programa de Fibonacci

/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package fubonachi;
import java.util.*;
/**
*
* @author alumno
*/
public class Fubonachii
{
public int Fubonachii(int n, int fininf, int finsup)
{
Scanner Cap=new Scanner(System.in);
System.out.println("Ingrese un numero");
n=Cap.nextInt();
System.out.println("------------------------");
if(n==0||n==1)
{
System.out.println("La suma es " +n);
return n;
}
fininf=0;
finsup=1;
for(int i=2;i<=n;i++)
{
int x;
x=fininf;
fininf=finsup;
finsup=x+fininf;
System.out.println(" " +finsup);
}
return (finsup);
}
public static void main(String[] args)
{
Fubonachii fb= new Fubonachii();
int n=0, fininf=0, finsup=1;
fb.Fubonachii(n, fininf, finsup);
}
}

-Videos

Torres de Hanoi

Teoria de Recursidad

Fuentes:

Texto

http://es.wikipedia.org/

Videos

http://www.youtube.com/

Imagenes

http://www.google.com.mx/imghp?hl=es&tab=wi

Colas

 -Concepto
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.
-Funciones

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.

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).

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ó.

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.

-Aplicacion

Las operaciones principales en una cola son la de insercion y extraccion de datos, llamadas encolar (enqueue) y desencolar (dequeue).

• 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

-Codigo

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

Ahora se analiza un tipo de tabla llamada "Pila"
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.
En cada momento sólo se tiene acceso a la parte superior de la pila, es decir, al último objeto apilado (denominado TOS, Top of Stack en inglés). La operación retirar permite la obtención de este elemento, que es retirado de la pila permitiendo el acceso al siguiente (apilado con anterioridad), que pasa a ser el nuevo TOS.
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.

Tipo de Pila

En la figura F31-3 se presentan ejemplos de a) pila llena, b) pila con algunos elementos y c) pila vacía.

 -Aplicacion

Las pilas suelen emplearse en los siguientes contextos:

• Evaluación de expresiones en notación postfija (notación polaca inversa).
• Reconocedores sintácticos de lenguajes independientes del contexto
• Implementación de recursividad.

 -Codigo

• Pila Estatica 

public class PilaArray
{
 
 private int vector[];
 private int cima, tamano;


  public PilaArray( int tamano_p)//tamano de la pila parametro constructor
  {
    if( tamano_p < 0)
    {   
      tamano = 0; 
      System.err.println("Error, tamano no valido");
    }//fin if
    else
    {
       
       vector = new int[ tamano_p ];
       tamano = tamano_p;
       cima = -1;
    }//fin else   
   
   
     
  }
   
//para saber si la pila esta vacia
  public boolean vacia()
  {
   if(cima == -1)
       return true;
  
   return false;
  }
   
 
  //Devuelva true si logra insertar elemento
  public boolean inserta(int valor)
  {
    //si ya no hay espacio... 
    if( cima == tamano-1 )
    {
      System.err.println("OverFloat");
      return false;
    }   
    else
    {
      vector [ ++cima ] = valor;
      System.out.println("Agregado correctamente");
      return true;
    }   
  }
 
  //devuelve el valor de la cima de la pila
  public int cima()
  {
    //si la pila esta vacia... 
    if( vacia() ) 
    {
       System.err.println("La pila esta vacia");
       //si la pila esta vacia se retorna un 0 ... solo por ejemplo
      
       return 0;
    } 
    else
    {
      return vector[ cima-- ]; 
    }   
  }
 
  //limpia la pila
  public void vaciar()
  {
     cima = -1;
  }
 
 
}//fin clase pila

• Pila Dimanica

Codigo Main

import java.util.*;
public class Main
{
 public static void main(String[] args)
 {
  //Variables del Sistema
  Pila MiPila = new Pila(); //Variable tipo pila
  Scanner in=new Scanner(System.in);//Variable que lee desde teclado
  int intOpc1,intOpc2;//Variables que contienen la opcion elegida por el usuario
  try
  {
   //Cuerpo del Programa
   do
   {
    //Menu del Sistema
    System.out.print("---------------------------------------\n");
    System.out.print("           Sistema Multipila\n");
    System.out.print("---------------------------------------\n");
    System.out.print("1. Agregar Pila\n");
    System.out.print("2. Eliminar Pila\n");
    System.out.print("3. Ver Ultima Pila Ingresada\n");
    System.out.print("4. Salir\n\n");
    System.out.print("Opcion: ");
    //Lectura de la Opcion
    intOpc1=in.nextInt();
    //Filtramos Seleccion
    switch(intOpc1)
    {
        //Caso Agregar Pila
     case 1:System.out.print("Ingresa el Elemento de la Pila: ");
            MiPila.push(in.next());
            break;
     //Caso Eliminar Pila
     case 2:MiPila.pop();
            break;
     //Caso Ver Ultima Pila Registrada
     case 3:System.out.print("Ultimo Dato ingresado en la Pila: "+MiPila.getData()+"\n");
            break;
     //Caso Salir
     case 4:System.exit(0);
             break;
     //Caso Erroneo
     default: System.out.print("Opcion incorrecta!\n");
    }
   }while(intOpc1!=4);
  }
  catch (Exception e)
  {
      System.err.println("\nWARNING: " + e.getMessage());
  }
 }
}

Codigo Pila

public class Pila
{
 //Atributos de la Clase
 protected Object ArrDatos[];

 //Constructor de la Clase
 public Pila()
 {
  //Creamos el Arreglo de Elementos
  ArrDatos=new Object[0];
 }

 //Metodos de la Clase
 //->Determina si una pila esta vacia o no
 private boolean isEmpty()
 {
  if(ArrDatos.length==0)
      return true;
  else
      return false;
 }
 //->Redimensiona Pila
 private void redim(boolean bolParametro)
 {
  Object ArrAux[];
  //Filtramos el parametro de la funcion
  if (bolParametro)
  {
   //Si es + creamos un arreglo auxiliar con un elemento mas
   ArrAux=new Object[ArrDatos.length+1];
   //Recorremos el arreglo de datos
   for(int i=0;i<ArrDatos.length;i++)
    //pasamos la informacion al Auxiliar
    ArrAux[i]=ArrDatos[i];
  }
  else
  {
   //Si es - creamos un arreglo auxiliar con un elemento menos
   ArrAux=new Object[ArrDatos.length-1];
   //Recorremos el arreglo de datos
   for(int i=0;i<ArrAux.length;i++)
    //pasamos la informacion al Auxiliar
    ArrAux[i]=ArrDatos[i];
  }
  //Redimensionamos el Arreglo de Datos al tamaño final
  ArrDatos=new Object[ArrAux.length];
  //Pasamos toda la informacion del Auxiliar al Original
  ArrDatos=ArrAux;
 }
 //->Agrega elemento a Pila
 public void push(Object ObjDato)
 {
  //Redimensionamos el Arreglo
  redim(true);
  //Ingresamos elemento a pila
  ArrDatos[ArrDatos.length-1]=ObjDato;
 }
 //->Elimina elemento a Pila
 public void pop()
 {
  //Revisamos estado de la Pila
  if (!isEmpty())
      //Si contiene elementos Redimensionamos la Pila
      redim(false);
  else
      //Si esta vacia generamos una Excepción
      throw new RuntimeException("Pila Vacia...");
 }
 //->Obtiene dato de Pila
 public Object getData()
 {
  //Revisamos estado de la Pila
  if(!isEmpty())
      //Si contiene elementos mandamos el dato
      return(ArrDatos[ArrDatos.length-1]);
  else
      //Si esta vacia generamos una Excepción
      throw new RuntimeException("Pila Vacia...");
 }
}