Recursividad en Programacion...

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 finen 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 seentienda mejor a continuación se exponen algunos ejemplos:

Factorial: Se desea calcular n! \, (el factorial de n \,, que se define como el producto de todos los enteros positivos de 1 \, a n\,). Se puede definir el problema de forma recurrente como n(n-1)! \,; como (n-1)! \, es menor que n! \, podemos aplicar inducción por lo que disponemos del resultado. El caso base es 0! \,que es 1 \,.
Algoritmo de ordenación por fusión: Sea v un vector de n elementos, podemos separar el vector en dos mitades. Estas dos mitades tienen tamaño n/2 por lo que por inducciónpodemos 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 cero o un elemento, queestá trivialmente ordenado y no hay que hacer nada.
En estos ejemplos podemos observar como un problema se divide en varias (una o más) instancias del mismo problema, pero de tamaño menorgracias a lo cual se puede aplicar inducción, llegando a un punto donde se conoce el resultado (el caso base).

Nota: aunque los términos "recursión" y "recursividad" son ampliamente empleadosen el campo de la informática, el término correcto en castellano es recurrencia [cita requerida]. Sin embargo este último término es algo más específico. Véase relación de recurrencia.