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);
}

Video

Recursividad

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:

Un problema que pueda ser definido en función de su tamaño, sea este N, pueda ser dividido en instancias más pequeñas (< N) del mismo problema y se conozca la solución explícita a las instancias más simples, lo que se conoce como casos base, se puede aplicar inducción sobre las llamadas más pequeñas y suponer que estas quedan resueltas. Para que se entienda mejor a continuación se exponen algunos ejemplos: Factorial(x: Entero): Sea N := x el tamaño del problema, podemos definir el problema de forma recurrente como x*Factorial(x - 1); como el tamaño de Factorial(x - 1) es menor que N podemos aplicar inducción por lo que disponemos del resultado. El caso base es el Factorial(0) que es 1. Ordenación por fusión(v: vector): Sea N := tamaño(v), podemos separar el vector en dos mitades. Estas dos mitades tienen tamaño N/2 por lo que por inducción podemos aplicar la ordenación en estos dos subproblemas. Una vez tenemos ambas mitades ordenadas simplemente debemos fusionarlas. El caso base es ordenar un vector de 0 elementos, que está trivialmente ordenado y no hay que hacer nada. En estos ejemplos podemos observar como un problema se divide en varias (>= 1) instancias del mismo problema, pero de tamaño menor gracias a lo cual se puede aplicar inducción, llegando a un punto donde se conoce el resultado (el caso base)..