Recursión

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.

Recursión 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, las instancias complejas de un proceso se definen en términos de instancias más simples, estando las finales más simples definidas de forma explícita.

Funciones definidas de forma recurrente

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!:

Con esta definición veamos como funciona 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

fuente: wikipedia