Aplicaciones de la recursividad

El proceso de llamadas recursivas siempre tiene que acabar en una llamada a la función que se resuelve de manera directa, sin necesidad de invocar de nuevo la función. Esto será siempre necesario, para que llegue un momento que se corten las llamadas reiterativas a la función y no se entre en un bucle infinito de invocaciones.

Quizás en la teoría cueste más ver lo que es una función recursiva que por la práctica. Un ejemplo típico de recursividad sería la función factorial. El factorial es una función matemática que se resuelve multiplicando ese número por todos los números naturales que hay entre él y 1.

Por ejemplo, factorial de 4 es igual a 4 * 3 * 2 * 1. Si nos fijamos, para el ejemplo de factorial de 4 (factorial se expresa matemáticamente con un signo de admiración hacia abajo, como 4!), se puede resolver como 4 * 3! (4 * factorial de 3). Es decir, podemos calcular el factorial de un número multiplicando ese número por factorial de ese número menos 1.

n! = n * (n-1)!


Existen muchas funciones matemáticas cuyos argumentos son números naturales, que pueden definirse de manera recursiva. Esto quiere decir que el valor de la función para el argumento n puede definirse en términos del argumento n-1 (o alguno anterior). En este tipo de definiciones siempre existirá un caso base a partir del cual parte la definición, el cual normalmente es el valor de la función en cero o en uno, aunque no necesariamente debe ser así.

Usualmente los lenguajes de programación permiten definir funciones de manera recursiva. El lenguaje C es uno de ellos. La definición recursiva para el factorial sería:

int factorial(int n) {
if ((n == 0) || (n == 1))
return(1);
else
return(n*factorial(n-1));
}

Normalmente las definiciones recursivas pueden expresarse en forma no recursiva. Sin embargo, dependiendo del caso, el resultado puede ser más confuso. Por ejemplo, una función en C que calcula el factorial en forma iterativa sería:

int factorial(int n) {
int i, fact = 1;

for (i=2; i<=n; i++)
fact = fact * i;
return(fact);
}