ARBOLES

Es un conjunto de nodos en cada nodo hay información



Cada nodo pude contener ( Strings, alfanuméricos y caracteres especiales)
1.Nodo vacio T= Q => T = [ ]

2.Raíz = Se desprende los subarboles

3.Logitud: es el numero de ramas o aristas desde la raíz hasta el nodo en referencia.

4.Profundidad: Se cuentan los nodos desde la raíz hasta el ultimo nodo.

5.Grado: Cantidad de nodos que tiene la raíz.

6.Tamaño. Es el numero de nodos del orden

Nota: Los nodos vacios se llaman externos y los nodos llenos se llaman internos.

Otras características:

Recorridos
•Preorden [R, I, D]
•Inorden [I,R,D]
•Post Orden [I,D,R]

COLAS

Cola (Principio fijo) FIFO
FIFO

First → in → Primero en entrar.
First → out → Primero en salir.



Operaciones con la cola:

1)Enqueve: Añade un elemento final de la cola.
2)Dequeve: elimina el primer elemento de la cola.
3)IsEmpty: La cola esta vacía.
4)IsFull: La cola esta llena.




Consideraciones:

1.La operación de insertar no tiene restricciones.
2.No se puede remover elementos de una lista vacía (Underflow)
3.Se necesita una arreglo y dos variables numéricas (Font – primer elemento se incializa en 0 y Rear Posición del ultimo elemento de la fila -1.


Fila Circular

1.El elemento anterior al primero es el último (en inglés es una dequeue)
2.Implementación con arreglos.



Fila Doble

Los elementos pueden insertarse o eliminarse por cualquiera de los dos extremos.

Variantes:

•Doble fila con entrada restringida
•Doble fila con Salida restringida

Operaciones:

•Insertar elementos Insertar elementos
•Eliminar elementos Eliminar elementos
•Ver si la fila esta vacía
•Ver si la fila esta llena
•Imprimir los elementos Imprimir los elementos
•Obtener el largo de la fila Obtener el largo de la fila

JAVA:
import java.io.*;

//Declaramos la clase calculatorTest

public class ejecutar_cola{

//Declaramos el metodo principal

public static void main (String args[])throws IOException {

BufferedReader entrada = new BufferedReader (new InputStreamReader(System.in));

int Espacios = 0;

char Resp,

op; String aux;

//---

Imprimir Menu ----

\\ System.out.println("\n :: XROM RELOADED :: 19/07/07 \n");

System.out.print("\t Cuantos espacios quiere en la Cola (entre 3 y 30 recomendable)? :"); Espacios = Integer.parseInt(entrada.readLine());

Cola Ejecutar = new Cola(Espacios);

//--- Imprimir Menu ----

\\ System.out.println("\n\n\t ------------

//-------- Menu Cola Simple --------\\\\------------ \n ");

do { System.out.println("\n\n1.- Imprimir Cola");

// Mostrar System.out.println("2.- Agregar Elemento a la Cola");

// Push System.out.println("3.- Quitar Elemento de la Cola");

// Pop System.out.print("\n\n Elija una Opcion : ");

aux = entrada.readLine(); op = aux.charAt(0);

//---- Elegir opcion ---

\\ switch (op) { case '1': Ejecutar.Imprimir();

break; case '2':

Ejecutar.Push();

break;

case '3': Ejecutar.Pop();

break;

default:

System.out.println("opcion fuera de rango !!"); }

// Fin del switch System.out.print("Desea hacer otra operacion ?? S / N ");

aux = entrada.readLine(); Resp = aux.charAt(0); } while (Resp == 'S' Resp == 's'); }

// Fin del metodo main }

// Fin de la calse Cola.java(Clase y Metodos de la Cola)

----------------------------------------------------------

Ejemplo: cola de espera

import java.util.*;

public class ColaEspera {

/** Clase interna para almacenar todos los datos de un cliente*/

private static class DatosCliente { Cliente c; long entrada, salida;

// milisegundos

/** Constructor; pone la hora de entrada*/ DatosCliente (Cliente c) {

this.c=c; entrada=Reloj.ahora(); }

void atiende() { salida=Reloj.ahora(); } }

// colas del servicio private Queue colaEspera;

private Queue colaAtendidos;

/**Constructor de ColaEspera *

/ public ColaEspera() {

colaEspera=new LinkedList();

colaAtendidos=new LinkedList(); }

** * Nuevo cliente; se mete en la cola de espera */

public void nuevoCliente(Cliente c)

{ DatosCliente datos=new DatosCliente(c);

colaEspera.add(datos);

} /** * Atender cliente: se saca de la cola de * espera y se mete en la de atendidos;

* retorna el cliente atendido */

public Cliente atenderCliente() throws NoSuchElementException {

DatosCliente datos=colaEspera.remove();

datos.atiende();

colaAtendidos.add(datos);

return datos.c; }

public double tiempoEsperaNoAtendidos() {

long tiempo=0;

int num=0;

long ahora=Reloj.ahora();

for (DatosCliente datos: colaEspera) { tiempo=tiempo + ahora-datos.entrada; num++; }

if (num==0) { return 0.0; }

else { return (((double) tiempo)/num)/1000.0; } }

public double tiempoEsperaNoAtendidos() {

long tiempo=0;

int num=0; long ahora=Reloj.ahora();

for (DatosCliente datos: colaEspera) { tiempo=tiempo + ahora-datos.entrada; num++; }

if (num==0) { return 0.0; }

else { return (((double) tiempo)/num)/1000.0; } }

Ejemplo con cola de prioridad /** *

Clase enumerada que representa la * urgencia de un cliente */

public enum Urgencia { baja, media, alta }

import java.util.*;

/public class ColaEsperaConUrgencia {

/** * Clase interna para almacenar los datos * de un cliente con urgencia */

private static class DatosCliente implements Comparable {

Cliente c; Urgencia urg; /** *

Constructor de DatosCliente */

DatosCliente (Cliente c, Urgencia urg) { this.c=c; this.urg=urg; }

/* * Comparación de clientes por su urgencia */

public int compareTo(DatosCliente otro) { return this.urg.compareTo(otro.urg); } //

cola del servicio private Queue colaEspera;

/** * Constructor de ColaEspera */ public ColaEsperaConUrgencia() { colaEspera=new PriorityQueue(); } /** * Nuevo clie

nte; se mete en la cola de espera *

/ public void nuevoCliente (Cliente c, Urgencia urg) { DatosCliente datos=new DatosCliente(c,urg); colaEspera.add(datos); }

/** * Atender cliente: se saca de la cola de * espera; retorna el cliente atendido */

public Cliente atenderCliente() throws NoSuchElementException { DatosCliente datos=colaEspera.remove(); return datos.c; }

/** *

Mostrar el estado de la cola de espera */

public void muestraEstado()

{ System.out.println();

System.out.println("--Estado de la cola--");

System.out.println("No atendidos "+ colaEspera.size());

if (colaEspera.size()>0) { for (DatosCliente datos:colaEspera) { System.out.println(datos.c+" urgencia: "+datos.urg); }

} }

/** * Num clientes en espera */ public int numClientesEnEspera() { return colaEspera.size();

} }

PILAS

Datos que se introducen (añaden o apilan) o se extraen (extraen o des apilan).

Tope (Se debe analizar cuando esta vacía)



Operaciones con la pila

1. PUSH: Añade un elemento a la pila.
2. POP: Quita un elemento a la pila.
3. PEEK: Tope de la pila.
4. IsEmpty: (Esta vacía) Determina que una pila no tiene elementos.
5. IsFull: (Esta llena) Determina si la pila esta llena.
6. Size: Determina el numero de elementos de la pila.

Ejemplo:


LIFO:
Last → in → ultima en entrar
First → out → primera en salir
Implementación:
1) Mediante un arreglo (Estatico) - Tamaño –Vector

[-1(Tope)][0][1][2][3]

2) Lista Enlazadas ( Dinamicas)



AN ( extraer, des apilar)

Ejemplo (1+2)*4+3

Entrada Operación Pila
1Apila operador 1
2Apila operador 1,2
+Añade 3
4Apila operador 3,4
*Añade 12
3Apila operador 12,3
+Añade 15 (Tope)

Nota: No tiene encuentra los paréntesis y pera de izquierda a derecha

Metodo_Principal.java

(Metodo Principal) JAVA:
import java.io.*;

public class Metodo_Principal{

/Declaramos el metodo principal public static void main (String args[])throws IOException {

BufferedReader entrada = new BufferedReader (new InputStreamReader(System.in));

int Espacios = 0;

char Resp, op;

String aux;

//--- Imprimir Menu ---- \\

System.out.println("\n :: XROM RELOADED :: 19/07/07 \n"); System.out.print("\t Cuantos espacios quiere en la Pila (entre 3 y 30 recomendable)? :");

Espacios = Integer.parseInt(entrada.readLine());

Pila Ejecutar = new Pila(Espacios);

System.out.println("\n\n\t --- //---- Menu Pila------\\\\---- \n");

do { System.out.println("\n\n1.- Imprimir Pila");

// Mostrar System.out.println("2.- Agregar Elemento a la pila");

// Push System.out.println("3.- Quitar Elemento de la pila");

// Pop System.out.print("\n\n Elija una Opcion : ");

aux = entrada.readLine();

op = aux.charAt(0);

//---- Elegir opcion ---\\ switch (op) { case '1': Ejecutar.Imprimir();

break;

case '2': Ejecutar.Push();

break;

case '3': Ejecutar.Pop();

break;

default: System.out.println("opcion fuera de rango !!"); }

// Fin del switch System.out.print("Desea hacer otra operacion ?? S / N ");

aux = entrada.readLine();

Resp = aux.charAt(0);

} while (Resp == 'S' Resp == 's');

System.out.println(" Garcias por utilizar este programa.. "); System.out.println("\t para mas informacion en :: WWW.XROMRELOADED.TK ::");

} // Fin del metodo main }

// Fin de la calse Pila.java

(Clase y Metodos) JAVA:

// Libreria necesaria para introducir datos desde el Teclado import java.io.*;

// Inicio de la Clase Pila public class Pila {

//----- Atributos de la pila ------\\

public int Pila [];

// Estructura de la pila public int Top, Max , Elem;

// variables para la pila

//Top : El Tope de la pila , referencia al ultimo elemento que esta en la pila //Max : Maximo de espacios que tiene la pila //Elem : Elemento que se agrega a la pila (Tecleado por el usuario)

public char Resp;

// Variables para SubMenus. public String aux;

//----- Contructor -------\\

public Pila (int Espacios){

// se recibe como parametro los Espacios de la pila Pila = new int [Espacios];

// Asignamos los espacios en la Pila Max = Pila.length - 1; Top = -1;

// Top se declara como -1 como referencia a que no existen datos en la pila }

// fin del constructor

//----- Metodos de la pila -------\\

// Metodo Imprimir

public void Imprimir ()

{ for (int n = 0 ; n <= Max ;

n++ ) { System.out.println(n + ".- " + Pila [n]);

}

} //----Fin del Metodo Imprimir

// Metodo Push ---

public void Push ( ) throws IOException

{ // Metodo para ingresar datos ...

BufferedReader entrada = new BufferedReader (new InputStreamReader(System.in));

do { // if (1) if(Top != Max)

{ // Si la pila No esta llena ....

// Se puede agregar un nuevo dato a la pila ....

System.out.print("\t Ingrese un numero entero : ");

Elem = Integer.parseInt(entrada.readLine());

Top ++;

// Se incrementa Top como referencia de que se agrego un nuevo dato Pila[Top] = Elem;

// Se agrega el nuevo elemento a la pila // if (1.1) if (Top == Max) {

// Si la pila quedo llena entoces ...

// Imprimir mensaje System.out.print("\n La Pila a quedado llena !! ");

// con esta variable detenemos el bucle do - while Resp = 'N';

} // Fin del if (1.1) } else { System.out.p

rintln("\n Pila llena !! Imposible introducir un valor a la pila"); Resp = 'N';

// detenemos el bucle }

// Fin del if (1)

// if (2) if (Resp != 'N') {

// Si es diferente de No , entoces seguir preguntado si se desea introducir mas datos

System.out.print("Desea introducir un dato mas ??"); aux = entrada.readLine();

Resp = aux.charAt(0);

} // Fin del if (2) }

while (Resp == 'S' Resp == 's');

// Continuar ciclando simpre y cuando sea Resp = 's' } //

Fin del Metodo Push

// Metodo Pop ----

public void Pop () {

if(Top != -1) {

// Si la pila no esta vacia entonces ....

System.out.println("Se borro el Dato : " + Pila[Top]);

// Eliminar dato Pila[Top] = 0;

// remplaza el valor por un cero (Eliminado) Top --;

// Top se reduce para decir que un elemento se borro }

else {

// De lo contrario imprime .."que la pila esta vacia" System.out.println("Pila Vacia... Imposible Eliminar");

} // fin del if }

//-----Fin del Metodo Pop } // Fin de la Clase Pila ----

COLASQUIZ

// QueueDemo.java

import com.javajeff.cds.*;

class QueueDemo {
public static void main (String [] args) {
System.out.println ("ArrayLinearQueue Demo");
System.out.println ("---------------------");
queueDemo (new ArrayLinearQueue (5));
System.out.println ("ArrayCircularQueue Demo");
System.out.println ("---------------------");
queueDemo (new ArrayCircularQueue (6)); // Need one more slot because
// of empty slot in circular
// implementation
}

static void queueDemo (Queue q) {
System.out.println ("Is empty = " + q.isEmpty ());
System.out.println ("Is full = " + q.isFull ());

System.out.println ("Inserting \"This\"");
q.insert ("This");

System.out.println ("Inserting \"is\"");
q.insert ("is");

System.out.println ("Inserting \"a\"");
q.insert ("a");

System.out.println ("Inserting \"sentence\"");
q.insert ("sentence");

System.out.println ("Inserting \".\"");
q.insert (".");

try {
System.out.println ("Inserting \"One last item\"");
q.insert ("One last item");
}
catch (FullQueueException e) {
System.out.println ("One insert too many");
System.out.println ("Is empty = " + q.isEmpty ());
System.out.println ("Is full = " + q.isFull ());
}

System.out.println ();

while (!q.isEmpty ())
System.out.println (q.remove () + " [Is empty = " + q.isEmpty () +
", Is full = " + q.isFull () + "]");

try {
q.remove ();
}
catch (EmptyQueueException e) {
System.out.println ("One remove too many");
}
System.out.println ();
}
}
************************
// ArrayLinearQueue.java

package com.javajeff.cds;

public class ArrayLinearQueue implements Queue {
private int front = -1, rear = -1;
private Object [] queue;

public ArrayLinearQueue (int maxElements) {
queue = new Object [maxElements];
}

public void insert (Object o) {
if (rear == queue.length - 1)
throw new FullQueueException ();
queue [++rear] = o;
}

public boolean isEmpty () {
return front == rear;
}

public boolean isFull () {
return rear == queue.length - 1;
}

public Object remove () {
if (front == rear)
throw new EmptyQueueException ();
return queue [++front];
}
}

*****************
// ArrayCircularQueue.java

package com.javajeff.cds;

public class ArrayCircularQueue implements Queue {
private int front = 0, rear = 0;
private Object [] queue;

public ArrayCircularQueue (int maxElements) {
queue = new Object [maxElements];
}

public void insert (Object o) {
int temp = rear;
rear = (rear + 1) % queue.length;
if (front == rear) {
rear = temp;
throw new FullQueueException ();
}
queue [rear] = o;
}

public boolean isEmpty () {
return front == rear;
}

public boolean isFull () {
return ((rear + 1) % queue.length) == front;
}

public Object remove () {
if (front == rear)
throw new EmptyQueueException ();
front = (front + 1) % queue.length;
return queue [front];
}
}


**************************
// Queue.java

package com.javajeff.cds;

public interface Queue {
void insert (Object o);
boolean isEmpty ();
boolean isFull ();
Object remove ();
}


****************************
// FullQueueException.java

package com.javajeff.cds;

public class FullQueueException extends RuntimeException {

/**
*
*/
private static final long serialVersionUID = 1L;
}


***********************
// EmptyQueueException.java

package com.javajeff.cds;

public class EmptyQueueException extends RuntimeException {

/**
*
*/
private static final long serialVersionUID = 1L;
}

SEGUNDO CORTE

COLAS

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.

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.

En estos casos, el primer elemento de la lista realiza su función (pagar comida, pagar entrada para el partido o para el cine) y deja la cola. Este movimiento está representado en la cola por la función pop o desencolar. Cada vez que otro elemento se añade a la lista de espera se añaden al final de la cola representando la función push o encolar. Hay otras funciones auxiliares para ver el tamaño de la cola (size), para ver si está vacía en el caso de que no haya nadie esperando (empty) o para ver el primer elemento de la cola (front).

Operaciones Básicas
Crear: se crea la cola vacía.
Encolar (añadir, entrar, push): se añade un elemento a la cola. Se añade al final de esta.
Desencolar (sacar, salir, pop): 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 primero elemento que entró.

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;
}
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:
Añadir un campo a cada nodo con su prioridad. Resulta conveniente mantener la cola ordenada por orden de prioridad.
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.

LISTAS ENLAZADA

Una lista enlazada es una serie de nodos, conectados entre sí a través de una referencia, en donde se almacena la información de los elementos de la lista. Por lo tanto, los nodos de una lista enlazada se componen de dos partes principales:

class NodoLista
{
Object elemento;
NodoLista siguiente;
}
La referencia contenida en el nodo de una lista se denomina siguiente, pues indica en dónde se encuentra el siguiente elemento de la lista. El último elemento de la lista no tiene nodo siguiente, por lo que se dice que la referencia siguiente del último elemento es null (nula).

La siguiente figura muestra un ejemplo de una lista enlazada cuyos elementos son strings:
La referencia lista indica la posición del primer elemento de la lista y permite acceder a todos los elementos de ésta: basta con seguir las referencias al nodo siguiente para recorrer la lista.
NodoLista aux=lista;
aux=aux.siguiente;
Siguiendo con el ejemplo anterior, para insertar un nuevo nodo justo delante del nodo referenciado por aux se deben modificar las referencias siguiente del nodo aux y del nodo a insertar.
NodoLista nuevo=new NodoLista(...);
//"nuevo" es la referencia del nodo a insertar en la lista
nuevo.siguiente=aux.siguiente;
aux.siguiente=nuevo;
//Notese que no es lo mismo realizar los cambios de referencia
//en un orden distinto al presentado, puesto que en ese caso
//se "pierde" la lista desde el nodo siguiente a aux

El procedimiento presentado a continuación es un ejemplo de cómo se programa el recorrido de una lista enlazada. Se supondrá que los objetos almacenados en cada nodo son strings:

void recorrido(NodoLista lista)
{
NodoLista aux=lista;
while (aux!=null)
{
System.out.println(aux.elemento);
aux=aux.siguiente;
}
}
Para invertir el orden de la lista, es decir, que el último elemento de la lista ahora sea el primero, que el penúltimo elemento de la lista ahora sea el segundo, etc..., modificando sólo las referencias y no el contenido de los nodos, es necesario realizar una sola pasada por la lista, y en cada nodo visitado se modifica la referencia siguiente para que apunte al nodo anterior. Es necesario mantener referencias auxiliares para acordarse en donde se encuentra el nodo anterior y el resto de la lista que aún no ha sido modificada:
void invertir(NodoLista lista)
{
NodoLista siguiente=lista;
NodoLista anterior=null;
while(lista!=null)
{
siguiente=lista.siguiente;
lista.siguiente=anterior;
anterior=lista;
lista=siguiente;
}
}
La implementación vista de los nodos también se conoce como lista de enlace simple, dado que sólo contiene una referencia al nodo siguiente y por lo tanto sólo puede recorrerse en un solo sentido. En una lista de doble enlace se agrega una segunda referencia al nodo previo, lo que permite recorrer la lista en ambos sentidos, y en general se implementa con una referencia al primer elemento y otra referencia al último elemento.

Una lista circular es aquella en donde la referencia siguiente del último nodo en vez de ser null apunta al primer nodo de la lista. El concepto se aplica tanto a listas de enlace simple como doblemente enlazadas.

En muchas aplicaciones que utilizan listas enlazadas es útil contar con un nodo cabecera, tambien conocido como dummy o header, que es un nodo "falso", ya que no contiene información relevante, y su referencia siguiente apunta al primer elemento de la lista. Al utilizar un nodo cabecera siempre es posible definir un nodo previo a cualquier nodo de la lista, definiendo que el previo al primer elemento es la cabecera.
Si se utiliza un nodo cabecera en una lista de doble enlace ya no es necesario contar con las referencias primero y último, puesto que el nodo cabecera tiene ambas referencias: su referencia siguiente es el primer elemento de la lista, y su referencia anterior es el último elemento de la lista. De esta forma la lista de doble enlace queda circular de una manera natural.

ESTRUCTURAS DINAMICAS PUNTEROS - NODOS

Esta ahora veniamos trabajando con variables, dimensionadas que son direcciones simbolicas de posiciones de memoria, de forma que existe una relacion bien determinada entre nombres de variables y posiciones de memoria durante toda la ejecucion del programa. aunque el contenido de la variable puede cambiar durante la ejecucion del programa. otro comportamiento de estas variables es que no pueden crecer ni disminuir por si mismas durante su ejecucion. sin embargo en muchas ocasiones es conveniente poder disponer de un metodo por el cual, podamos adquirir posiciones de memoria adicionales, amedida que las vayamos necesitando durante su ejecucion y al contrario liberarlas cuando no se necesiten.

la variables y estructuras de datos que reunen estas condiciones se llaman dinamicas y se representan con la ayuda de un nuevo tipo de dato, llamado puntero, que se define como un dato que indica la posicion de memoria ocupada por otro dato. puede concebirse como una fecha, que apunta al dato en cuestion.

TECNICAS DE PROGRAMACION - RECURSIVIDAD

Recursividad
La recursividad es una técnica de programación importante. Se utiliza para realizar una llamada a una función desde la misma función. Como ejemplo útil se puede presentar el cálculo de números factoriales. Él factorial de 0 es, por definición, 1. Los factoriales de números mayores se calculan mediante la multiplicación de 1 * 2 * ..., incrementando el número de 1 en 1 hasta llegar al número para el que se está calculando el factorial.
El siguiente párrafo muestra una función, expresada con palabras, que calcula un factorial.
"Si el número es menor que cero, se rechaza. Si no es un entero, se redondea al siguiente entero. Si el número es cero, su factorial es uno. Si el número es mayor que cero, se multiplica por él factorial del número menor inmediato."
Para calcular el factorial de cualquier número mayor que cero hay que calcular como mínimo el factorial de otro número. La función que se utiliza es la función en la que se encuentra en estos momentos, esta función debe llamarse a sí misma para el número menor inmediato, para poder ejecutarse en el número actual. Esto es un ejemplo de recursividad.
La recursividad y la iteración (ejecución en bucle) están muy relacionadas, cualquier acción que pueda realizarse con la recursividad puede realizarse con iteración y viceversa. Normalmente, un cálculo determinado se prestará a una técnica u otra, sólo necesita elegir el enfoque más natural o con el que se sienta más cómodo.
Claramente, esta técnica puede constituir un modo de meterse en problemas. Es fácil crear una función recursiva que no llegue a devolver nunca un resultado definitivo y no pueda llegar a un punto de finalización. Este tipo de recursividad hace que el sistema ejecute lo que se conoce como bucle "infinito".
Para entender mejor lo que en realidad es el concepto de recursión veamos un poco lo referente a la secuencia de Fibonacci.
Principalmente habría que aclarar que es un ejemplo menos familiar que el del factorial, que consiste en la secuencia de enteros.
0,1,1,2,3,5,8,13,21,34,...,
Cada elemento en esta secuencia es la suma de los precedentes (por ejemplo 0 + 1 = 0, 1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, ...) sean fib(0) = 0, fib (1) = 1 y así sucesivamente, entonces puede definirse la secuencia de Fibonacci mediante la definición recursiva (define un objeto en términos de un caso mas simple de si mismo):
fib (n) = n if n = = 0 or n = = 1
fib (n) = fib (n - 2) + fib (n - 1) if n >= 2
Por ejemplo, para calcular fib (6), puede aplicarse la definición de manera recursiva para obtener:
Fib (6) = fib (4) + fib (5) = fib (2) + fib (3) + fib (5) = fib (0) + fib (1) + fib (3) + fib (5) = 0 + 1 fib (3) + fib (5)
1. + fib (1) + fib (2) + fib(5) =
1. + 1 + fib(0) + fib (1) + fib (5) =
2. + 0 + 1 + fib(5) = 3 + fib (3) + fib (4) =
3. + fib (1) + fib (2) + fib (4) =
3 + 1 + fib (0) + fib (1) + fib (4) =
4. + 0 + 1 + fib (2) + fib (3) = 5 + fib (0) + fib (1) + fib (3) =
5. + 0 + 1 + fib (1) + fib (2) = 6 + 1 + fib (0) + fib (1) =
6. + 0 + 1 = 8

Obsérvese que la definición recursiva de los números de Fibonacci difiere de las definiciones recursivas de la función factorial y de la multiplicación . La definición recursiva de fib se refiere dos veces a sí misma . Por ejemplo, fib (6) = fib (4) + fib (5), de tal manera que al calcular fib (6), fib tiene que aplicarse de manera recursiva dos veces. Sin embargo calcular fib (5) también implica calcular fib (4), así que al aplicar la definición hay mucha redundancia de cálculo. En ejemplo anterior, fib(3) se calcula tres veces por separado. Sería mucho mas eficiente "recordar" el valor de fib(3) la primera vez que se calcula y volver a usarlo cada vez que se necesite. Es mucho mas eficiente un método iterativo como el que sigue parar calcular fib(n).


Mediante ambos métodos: recursivo e iterativo. Lo mismo ocurre con el numero de sumas en los dos métodos al calcular la multiplicación. Sin embargo, en el caso de los números de Fibonacci, el método recursivo es mucho mas costoso que el iterativo.


Propiedades de las definiciones o algoritmos recursivos:

Un requisito importante para que sea correcto un algoritmo recursivo es que no genere una secuencia infinita de llamadas así mismo. Claro que cualquier algoritmo que genere tal secuencia no termina nunca. Una función recursiva f debe definirse en términos que no impliquen a f al menos en un argumento o grupo de argumentos. Debe existir una "salida" de la secuencia de llamadas recursivas.
Si en esta salida no puede calcularse ninguna función recursiva. Cualquier caso de definición recursiva o invocación de un algoritmo recursivo tiene que reducirse a la larga a alguna manipulación de uno o casos mas simples no recursivos.