Recursividad

Se dice que algo es recursivo si se define en función de sí mismo o a sí mismo. También se dice que nunca se debe incluir la misma palabra en la definición de ésta. El caso es que las definiciones recursivas aparecen con frecuencia en matemáticas, e incluso en la vida real. Un ejemplo: basta con apuntar una cámara al monitor que muestra la imagen que muestra esa cámara. El efecto es verdaderamente curioso, en especial cuando se mueve la cámara alrededor del monitor.
En matemáticas, tenemos múltiples definiciones recursivas:
- Números naturales:
(1) 1 es número natural. (2) el siguiente número de un número natural es un número natural
- El factorial: n!, de un número natural (incluido el 0):
(1) si n = 0 entonces: 0! = 1 (2) si n > 0 entonces: n! = n · (n-1)!
Asimismo, puede definirse un programa en términos recursivos, como una serie de pasos básicos, o paso base (también conocido como condición de parada), y un paso recursivo, donde vuelve a llamarse al programa. En un computador, esta serie de pasos recursivos debe ser finita, terminando con un paso base. Es decir, a cada paso recursivo se reduce el número de pasos que hay que dar para terminar, llegando un momento en el que no se verifica la condición de paso a la recursividad. Ni el paso base ni el paso recursivo son necesariamente únicos.
Por otra parte, la recursividad también puede ser indirecta, si tenemos un procedimiento P que llama a otro Q y éste a su vez llama a P. También en estos casos debe haber una condición de parada.
Existen ciertas estructuras cuya definición es recursiva, tales como los árboles, y los algoritmos que utilizan árboles suelen ser en general recursivos.

¿Cuándo utilizar la recursión?
Para empezar, algunos lenguajes de programación no admiten el uso de recursividad, como por ejemplo el ensamblador o el FORTRAN. Es obvio que en ese caso se requerirá una solución no recursiva (iterativa). Tampoco se debe utilizar cuando la solución iterativa sea clara a simple vista. Sin embargo, en otros casos, obtener una solución iterativa es mucho más complicado que una solución recursiva, y es entonces cuando se puede plantear la duda de si merece la pena transformar la solución recursiva en otra iterativa. Posteriormente se explicará como eliminar la recursión, y se basa en almacenar en una pila los valores de las variables locales que haya para un procedimiento en cada llamada recursiva. Esto reduce la claridad del programa. Aún así, hay que considerar que el compilador transformará la solución recursiva en una iterativa, utilizando una pila, para cuando compile al código del computador.Por otra parte, casi todos los algoritmos basados en los esquemas de vuelta atrás y divide y vencerás son recursivos, pues de alguna manera parece mucho más natural una solución recursiva.
Aunque parezca mentira, es en general mucho más sencillo escribir un programa recursivo que su equivalente iterativo. Si el lector no se lo cree, posiblemente se deba a que no domine todavía la recursividad. Se propondrán diversos ejemplos de programas recursivos de diversa complejidad para acostumbrarse a la recursión.