Para resolver algorítmicamente un problema, disponemos de distintos tipos de bucle (loop en inglés): «Para» (for en inglés), «Mientras» (while), «Repetir hasta que» (repeat until). Por desgracia, estas estructuras no siempre son tan fáciles de implementar. La condición de salida del bucle depende a menudo de parámetros que se modifican durante la ejecución; demostrar que esta condición acabará siendo verdadera no es sencillo. Para los aficionados a la programación funcional, la cuestión ni siquiera se plantea: se niegan a usar bucles; si no se emplean variables, ¿para qué iterar?
El remedio para todos estos males es la recursividad.
Un algoritmo es recursivo si se llama a sí mismo. Atención: no todos los lenguajes informáticos lo permiten. El ejemplo clásico de recursividad es el cálculo del factorial: el factorial de un número entero n (denotado n!) es igual a n multiplicado por el factorial de n – 1. Como hay que detenerse en algún momento, se define el factorial de 1 como 1. Este ejemplo muestra que, al escribir un procedimiento recursivo, hay dos reglas que respetar: hace falta una condición de terminación —aquí, n = 1— y hay que volver a aplicar el procedimiento a un «conjunto estrictamente más pequeño» —aquí, n – 1 es efectivamente estrictamente menor que n—. Para concretarlo del todo, aquí está el pseudocódigo de nuestro procedimiento.
Veamos cómo se desarrolla el algoritmo para n = 3.
