Unidad 1

RECURSIÓN.-
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ó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 deFactorial(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 simplementedebemos fusionarlas. El caso base es ordenar un vector de 0 elementos, que está trivialmente ordenado y no hay que hacer nada.
Números naturales.-
Un ejemplo de conjunto definido de forma recurrente es el de los números naturales:
a) 0 pertenece a N
b) Si n pertenece a N, entonces n+1 pertenece a N
c) Si X verifica a) y b) , entonces N está incluido en X
Los números naturales es el conjuntode números enteros no negativos.
Aquellas funciones cuyo dominio puede ser recursivamente definido pueden ser definidas de forma recurrente.
El ejemplo más conocido es la definición recurrente de la función factorial n!:

Ejemplo de esta función para el valor del factorial de 3:
-------------------------------------------------
3! = 3 · (3-1)!-------------------------------------------------
= 3 · 2!
-------------------------------------------------
= 3 · 2 · (2-1)!
-------------------------------------------------
= 3 · 2 · 1!
-------------------------------------------------
= 3 · 2 · 1 · (1-1)!
-------------------------------------------------
= 3 · 2 · 1 · 0!-------------------------------------------------
= 3 · 2 · 1 · 1
-------------------------------------------------
= 6
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 numerosos algoritmos de granimportancia, 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 < 2) return 1; // Caso base: Cuando X < 2 devolvemos 1 puesto que 1! = 1
-------------------------------------------------
return x*factorial(x - 1); // Si X >= 2 devolvemos el producto de 'X' por el factorial de 'X'-1
-------------------------------------------------
}
El seguimiento de la recursividad programadaes 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...