Por ejemplo, la función factorial de un número natural positivo (vamos a contemplar el factorial números positivos, excluido el 0). Recordemos que un factorial consiste multiplicar un número por todos los anteriores hasta llegar al 1.

De esta manera, por ejemplo, el factorial de 5 (vamos a llamarlo F(5), aunque en matemáticas suele escribirse como 5!) es 5×4×3×2×1. Si nos fijamos, 4×3×2×1 es el factorial de 4, es decir F(4), pero además 3×2×1 es el factorial de 3…F(3) y así sucesivamente… Cuando llegamos al 1, F(1) se calcularía como 1 multiplicado por todos los números anteriores al 1 hasta llegar al 1, pero como ya estamos en el 1, F(1)=1, sin multiplicarlo por nada más.

Esta cualidad de que el factorial de un número pueda escribirse en términos del factorial de un número anterior viene muy bien para dar una definición recursiva del factorial: Diremos que el factorial de un número n es n multiplicado por el factorial del anterior, es decir el factorial de n-1. Esto vale para todos los números naturales positivos del dos en adelante, pero no para el 1, ya que el 1 no tiene un número anterior. Al factorial de 1 le llamaremos “caso base”, y directamente lo definiremos como 1, y no en función de un factorial más pequeño. De ésta manera, ya podemos definir la función factorial recursivamente:

F(1)=1
F(n)=n×F(n-1)      Si n>1
 

Bonito y elegante.

Las definiciones recursivas casi siempre van en esta línea. Hay uno o varios casos de la función que se resuelven directamente. Son los casos base. En el factorial, el caso base es cuando n=1, que directamente decidimos que es 1. El resto de los casos, los definimos en función del un factorial "más pequeño".

La mayor parte de los lenguajes de programación modernos permiten programar funciones recursivas, a la manera de las matemáticas… Pero hay una substancial diferencia entre una función matemática y un función programada: mientras que una función matemática como ésta describe QUÉ es el factorial, una función programada describe CÓMO se obtiene.

Dicho de otra manera: Las más de las veces, las descripciones funcionales matemáticas se hacen con objeto de describir algo, de tal manera que un lector humano sea capaz de entenderlo y razonar sobre ello. Por esta manera, en muchas ocasiones, son descripciones bastante elegantes: breves, concisas, preparadas para que el entendimiento humano capte su idea con relativa facilidad. Sin embargo, la perspectiva cambia cuando pasamos al mundo de la computación. Poner en práctica una idea matemática a través de las herramientas que nos brinda la programación, no significa necesariamente trasladar al lenguaje de programación una definición matemática tal cual. Cada línea de programa que escribimos requiere el gasto de una serie de recursos de computación: tiempo de CPU, memoria, etc… Es necesario tener estos factores en cuenta a la hora de programar.

La recursividad en programación, aunque está permitida en prácticamente todos los lenguajes modernos, no es una herramienta demasiado útil en un entorno productivo, por una serie de factores que veremos más adelante. No obstante, al igual que ocurre con la recursividad en matemáticas, es una técnica que a menudo nos presenta maneras elegantes de resolver un problema, pero de poca utilidad práctica, debido a los problemas colaterales que plantea.

Muchos programadores noveles se preguntan ¿Cuándo debo utilizar entonces recursividad? En la humilde opinión del que escribe, la respuesta es bastante clara.

La recursividad puede venir bastante bien para empezar a resolver cierto tipo de problemas. Es necesario que todos los programadores la dominemos y sepamos sus beneficios. Mientras estemos en un entorno experimental (las primeras fases de resolución de un problema, en un laboratorio de programación, resolviendo ejercicios de clase…) la recursividad es un arma poderosa.

En el momento en que nuestro trabajo debe formar parte de un entorno productivo no experimental, es decir, un programa o aplicación que debe servir a alguien para algún fin productivo, la recursividad debe evitarse a toda costa. Si la hemos empleado en fases prematuras del desarrollo, será necesario aplicar transformaciones para convertir las soluciones recursivas en iterativas.