Recursividad

Recursividad
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ónexplícita a las instancias más simples, lo que se conoce como casos base, se puede aplicar inducciónsobre las llamadas más pequeñas y suponer que estas quedan resueltas.
En programación, un método usual de simplificación de un problema complejo es la división de este en subproblemas del mismo tipo. Esta técnica de programación se conoce como divide y vencerás y es el núcleo en el diseño de numerososalgoritmos de gran importancia, así como también es parte fundamental de la programación dinámica.

El ejemplo del cálculo recursivo del factorial de un número llevado al campo de la programación, en este ejemplo C++:
int factorial(int x)
{
if (x > -1 && x < 2) return 1; // Cuando -1 < x < 2 devolvemos 1 puesto que 0! = 1 y 1! = 1
else if (x < 0) return 0; // Error no existe factorial denúmeros negativos
return x * factorial(x - 1); // Si x >= 2 devolvemos el producto de x por el factorial de x - 1
}
Este ejemplo está basado en el lenguaje de programación Pauscal:
Proc Factorial(x:Entero):Entero
Si (x > -1 Y x < 2) Devolver 1 ' Cuando x sea mayor que -1 y menor que 2 Devolver 1.
Si (x < 0) Devolver 0 ' Cuando x sea menor a 0, devolver 0
Devolver x * Factorial(x - 1) 'Si x igual o mayor que 2 devolvemos el producto de x por el factorial de x - 1
FinProc
El seguimiento de la recursividad programada es casi exactamente igual al ejemplo antes dado, para intentar ayudar a que se entienda mejor se ha acompañado con muchas explicaciones y con colores que diferencia los distintos sub-procesos de la recursividad.
X = 3 //Queremos 3!, por lo tanto X inicial es 3
X >=2 -> return 3*factorial(2);
X = 2 //Ahora estamos solicitando el factorial de 2
X >= 2 -> return 2*factorial(1);
X = 1 // Ahora estamos solicitando el factorial de 1
X < 2 -> return 1;
[En este punto tenemos el factorial de 1 por lo que volvemos marcha atrás resolviendo todos los resultados]
return 2 [es decir: return 2*1 = return 2*factorial(1)]
return 6 [esdecir: return 3*2 = return 3*factorial(2)*factorial(1)] // El resultado devuelto es 6

Algoritmo implementado en el lenguaje Prolog:
fact(0,1):-!.
fact(N,F):-N1 is N-1,fact(N1,F1),F is N*F1.














Facultad de Ingeniería Mecánica y Eléctrica
Nombre del maestro: M.C. Oscar Rangel Aguilar
Nombre del alumno(a): Brenda Cecilia Macias Ruiz
Matrícula: 1581009
Hora: V1
Tema: RecursividadListas
Una lista enlazada es una de las estructuras de datos fundamentales, y puede ser usada para implementar otras estructuras de datos. Consiste en una secuencia de nodos, en los que se guardan campos de datos arbitrarios y una o dos referencias, enlaces o punteros al nodo anterior o posterior. El principal beneficio de las listas enlazadas respecto a los vectores convencionales es que el ordende los elementos enlazados puede ser diferente al orden de almacenamiento en la memoria o el disco, permitiendo que el orden de recorrido de la lista sea diferente al de almacenamiento.
Una lista enlazada es un tipo de dato autorreferenciado porque contienen un puntero o enlace (en inglés link, del mismo significado) a otro dato del mismo tipo. Las listas enlazadas permiten inserciones yeliminación de nodos en cualquier punto de la lista en tiempo constante (suponiendo que dicho punto está previamente identificado o localizado), pero no permiten un acceso aleatorio. Existen diferentes tipos de listas enlazadas: listas enlazadas simples, listas doblemente enlazadas, listas enlazadas circulares y listas enlazadas doblemente circulares.
Las listas enlazadas pueden ser implementadas en...