Recursividad

Recursividad
[pic]

Anuncio de cacao con una imagen recursiva. La mujer muestra un paquete idéntico al del propio anuncio, conteniendo así a otra mujer que muestra otro paquete más pequeño, deforma recursiva.
[pic]

Imagen recursiva formada por un triángulo.

Cada triángulo está compuesto de otros más pequeños, compuestos a su vez de la misma estructura recursiva.
Recurrencia, recursióno 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 problemaque 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ón explícita a las instancias más simples, loque 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, puede definir el problema de forma recurrente como x*Factorial(x - 1); como el tamaño de Factorial(x - 1) es menor que N se puedeaplicar inducción por lo que se dispone del resultado. El caso base es el Factorial(0) que es 1.
• Ordenación por fusión(v: vector): Sea N := tamaño(v), se puede separar el vector en dos mitades.Estas dos mitades tienen tamaño N/2 por lo que por inducción se puede aplicar la ordenación en estos dos subproblemas. Una vez que se tienen ambas mitades ordenadas simplemente se debe fusionarlas.El caso base es ordenar un vector de 0 elementos, que está trivialmente ordenado y no hay que hacer nada.
En estos ejemplos se puede observar como un problema, se divide en varias (>= 1) instanciasdel mismo problema, pero de tamaño menor gracias 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...