Recursividad

Algoritmo recursivo


Un algoritmo recursivo es un algoritmo que expresa la solución de un problema en términos de una llamada a sí mismo. La llamada a sí mismo se conoce como llamada recursiva.
Algunos ejemplos de recurrencia:
En un texto: Para saber qué es la recurrencia, primero hay que saber qué es la recurrencia.
En un acrónimo: ¿Qué es GNU? -> GNU No es Unix
¿Qué es PHP? -> PHP: Hipertext Preprocessor

En matemáticas: f(x) = x * f(x-1)
En un algoritmo: FUNCIÓN Factorial(n)
INICIO
SI (n<2) ENTONCES
Factorial = 1;
SINO
Factorial = n * Factorial(n-1);
FIN-SI
FIN
Generalmente, si la primera llamada al subprograma se plantea sobre un problema de tamaño u orden N, cada nueva ejecución recurrente del mismo se planteará sobre problemas, de igual naturaleza que el original, pero de un tamaño menor que N. De esta forma, al ir reduciendo progresivamente la complejidad del problema a resolver, llegará un momento en que su resolución sea más o menos trivial (o, al menos, suficientemente manejable como para resolverlo de forma no recursiva). En esa situación diremos que estamos ante un caso base de la recursividad.
Las claves para construir un subprograma recurrente son:
Cada llamada recurrente se debería definir sobre un problema de menor complejidad (algo más fácil de resolver).
Ha de existir al menos un caso base para evitar que la recurrencia sea infinita.
Es frecuente que los algoritmos recurrentes sean más ineficientes en tiempo que los iterativos aunque suelen ser mucho más breves en espacio.

Recursividad indirecta
Cuando en una subrutina hay llamadas a ella misma se habla de recursividad directa, en contraposición, cuando se tienen varias subrutinas y éstas se llaman unas a otras formando ciclos se dice que la recursión es indirecta.Subrutina_A --> Subrutina_B --> Subrutina_A
Subrutina_A --> Subrutina_B --> Subrutina_C --> Subrutina_D --> Subrutina_A

algoritmo torres hanoi

ALGORITMO RECURSIVO:
n = 0
palo A
palo B
palo C
si n = 1
imprimir "Pasar A a B"
else
Hanoi (n-1,A,C,B)
iprimir "Pasar A a B"
Hanoi (n-1,C,B,A)
fin
Procedimiento:
Hanoi (3,1,2,3)
Hanoi (1,1,2,3) ;Cambia 1 a 2
Hanoi (2,1,3,2) Cambia de 1 a 3
Hanoi (1,2,3,1) Cambia de 2 a 3
Cambia de 1 a 2 ; Cambia de 1 a 2 ; Cambia de 1 a 2
Hanoi (1,3,1,2) Cambia de 3 a 1
Hanoi (2,3,2,1) Cambia de 3 a 2 ; Cambia de 3 a 2
Hanoi (1,1,2,3) Cambia de 1 a 2CODIGO JAVA
import java.util.*;
public class Hanoi {
// move n smallest discs from one pole to another, using the temp pole
public static void hanoi (int n, String from, String temp, String to) {
if (n == 0) return;
hanoi (n-1, from, to, temp);
System.out.println("Move disc " + n + " from " + from + " to " + to);
hanoi (n-1, temp, from, to);
}
public static void muestraminuto (){
GregorianCalendar gc = new GregorianCalendar ();
System.out.println ( gc.get (Calendar.MINUTE));
System.out.println ( gc.get (Calendar.SECOND));
System.out.println ( gc.get (Calendar.MILLISECOND));
}
public static void main(String[] args) {
// int N = 3;
int N = Integer.parseInt(args[0]);
muestraminuto();
hanoi(N, "A", "B", "C");
muestraminuto();
}}

Nodos

Un nodo es un punto de intersección o unión de varios elementos que confluyen en el mismo lugar. Ahora bien, dentro de la informática la palabra nodo puede referirse a conceptos diferentes según en ámbito en el que nos movamos:
En redes de computadoras cada una de las máquinas es un nodo, y si la red es Internet, cada servidor constituye también un nodo.

En estructuras de datos dinámicas un nodo es un registro que contiene un dato de interés y al menos un puntero para referenciar (apuntar) a otro nodo. Si la estructura tiene sólo un puntero, la única estructura que se puede construir con el es una lista, si el nodo tiene más de un puntero ya se pueden construir estructuras más complejas como árboles o grafos
La eficiencia. Antiguamente los programadores gastaban mucho tiempo en ahorrar espacio de memoria y disminución de tiempos de ejecución.

Hoy, aunque se debe tener presente siempre el ahorro de memoria y el tiempo de ejecución, los avances de Hw hacen que esta variable no sea tan exigente como en tiempos pasados.

TEMA 2. ESTRUCTURAS LINEALES


OBJETIVOS
En este tema se definen varios tipos abstractos de datos que tienen una propiedad común, disponer de una estructura lineal.Para cada uno de estos TAD se realiza su especificación y se dan implementaciones alternativas. Para ilustrar la utilidad de losmismos se presentan ejemplos de aplicación para su realización en Java.

INTRODUCCION


♦ Las estructuras lineales son importantes porque aparecen con mucha frecuencia en situaciones de la vida: Una cola de clientes
de un banco, las instrucciones de un programa, los caracteres de una cadena o las páginas de un libro.
♦ Características: existe un único elemento, llamado primero, existe un único elemento, llamado último, cada elemento, excepto el
primero, tiene un único predecesor y cada elemento, excepto el último, tiene un único sucesor.


♦ Operaciones: crear la estructura vacía, insertar un elemento, borrar y obtener un elemento. Para definir claramente el
comportamiento de la estructura es necesario determinar en qué posición se inserta un elemento nuevo y qué elemento se borra o se obtiene.
♦ Principales estructuras lineales: pilas,
colas y listas.

Una pila es un contenedor de objetos que son insertados y eliminados de acuerdo con el principio de que el último en entrar es el primero en salir.
♦ También se les denomina estructuras LIFO
(Last In First Out).

TAD PILA

Las pilas pueden representarse mediante el uso de:
• Arreglos.
• Listas enlazadas.
Al utilizar arreglos para implementar pilas, tenemos la limitante de espacio de memoria reservada. Una vez establecido un máximo de capacidad para la pila, ya no es posible insertar más elementos.
La variable cima contiene el número de elementos actualmente e la pila y puede ser utilizada como un subíndice o como un puntero al elemento superior de la pila. Si una pila no tiene elementos, se dice que es una pila vacía. La variable o puntero cima se incrementa en uno al poner un elemento en la pila y se decrementa en uno al quitar el elemento.

Listas

class SLLDelDemo {
static class Node {
String name;
Node next;
}
public static void main (String [] args) {
Node top = new Node ();
top.name = "Jordan";
top.next = null;
Node temp = new Node ();
temp.name = "Eduardo";
temp.next = top;
top = temp;

temp = new Node ();
temp.name = "";
temp.next = top;
top = temp;

temp = new Node ();
temp.name = "Jorge";
temp.next = top;
top = temp;

dump (" ", top);

top = top.next;
dump (" ", top);

temp = new Node ();
temp.name = "Jorge";
temp.next = top;
top = temp;


temp = top;

while (temp.name.equals ("Camilo") == false)
temp = temp.next;
temp.next = temp.next.next;
dump (" ", top);
}
static void dump (String msg, Node topNode) {
System.out.print (msg + " ");
while (topNode != null) {
System.out.print (topNode.name + " ");
topNode = topNode.next;
}
System.out.println ();
}