Entender la recursividad
Detalles- Detalles
- Categoría: Artículos
- Publicado el Miércoles, 06 Diciembre 2006 12:03
En las matemáticas, que aparecieron muchísimo antes que la computación, las definiciones recursivas son frecuentes, ya que en muchos casos son sencillas de entender y elegantes. Las definiciones recursivas suelen responder a funciones que se definen en base a un caso menor de sí mismas. Pero la recursividad en programación tiene otras implicaciones. 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.
{mospagebreak title=Resolviendo el factorial}
RESOLVIENDO EL FACTORIAL
Programar una función recursiva es sencillo. Observa este método en C# para resolver el factorial.
static int Factorial(int n)
{
int resultado;
if (n == 1) //caso base
resultado = 1;
else //otro caso
resultado = n * Factorial(n - 1);
return resultado;
}
El problema de esta función recursiva es que cuando n es distinto de 1, por ejemplo... n=5, se produce una nueva invocación de la función pasando como parámetro n=4. Esta nueva invocación provoca que en la pila de llamadas se reserve espacio para esta nueva invocación, y la llamada original (con n=5) queda "en suspenso" hasta que se resuelve la llamada con n=4. En ese momento, en la pila de llamadas hay DOS parámetros n... uno que vale 5 y otro que vale 4... pero también hay dos variables "resultado", y además, la dirección de retorno que permitirá que una vez resuelto el caso con n=4 se pueda retomar el caso n=5 (lo que se denomina el "contexto de ejecución").
Pero como puedes imaginar, ahí no termina la cosa, por que n=4 no se puede resolver sin volver a invocar la función de nuevo con n=3... y nuevamente se debe volver a invocar con n=2... y nuevamente con n=1.
Al llegar a ese punto, n=1 es el caso base, que se resuelve sin llamada recursiva. En la pila de llamadas estará el contexto de ejecución de las anteriores llamadas (n=5, n=4, =3, n=2 y la propia n=1).
El caso base provoca que la función devuelva un 1. La llamada con n=1 se elimina de la pila y recoge el resultado (un 1) la llamada con n=2, que multiplica ese 1 por 2, y devuelve el resultado (un 2). Se elimina su contexto de la pila y recoge el resultado la llamada con n=3, y multiplica ese 2 por el 3 (un 6). Nuevamente el mismo proceso... la llamada con n=4 recoge ese 6 y multiplica 6 por 4 (24). Se retorna el 24 y lo recoge la llamada de n=5, que multiplica el 24 por 5 (120), y finalmente devuelve ese resultado.
Bueno... funcionar, funciona... pero para un simple factorial de 5, se han hecho 5 llamadas a función, lo cual implica que en cada una de ellas, la CPU o el intérprete han tenido que salvar el contexto en la pila de llamadas, que para cada una de ellas se ha reservado espacio para un parámetro n, y también para cada una de ellas se ha creado una variable "resultado". Se ha producido un salto de retorno y se ha retornado un parámetro 5 veces.
Si no sabes qué es eso de la pila de llamadas, lee nuestro artículo Code, stack, data & heap en la ejecución de programas
La función es bonita, pero poco práctica. Demasiado gasto de memoria y demasiado trabajo para la CPU cuando puede obtenerse el mismo resultado de una forma mucho más sencilla: iterativamente... es decir, ingeniando una forma de que a través de unos pasos repetitivos lleguemos a la misma solución.
En el caso del factorial es muy sencillo obtenerla... el factorial de 5 consiste en multiplicar 5 por todos los numeros naturales anteriores hasta llegar a 1... Incluso diría más... el 1 es innecesario... basta con llegar a 2. (porque multiplicar por 1 da el mismo resultado).
static int FactIterativo(int n)
{
int resultado=1;
for (int contador=n;contador>=2;contador--) {
resultado = resultado * contador;
}
return resultado;
}
Calcular el factorial de 5 mediante éste método iterativo no requiere de ninguna otra llamada a función. Los parámetros y las variables, como n, resultado o contador se crean una sola vez. La variable contador vale en cada iteración 5, 4, 3 y 2.... mientras la variable resultado vale en cada iteración 5, 20, 60 y 120. Con solo tres variables hemos solucionado el problema. En la solución recursiva, las variables se crean para cada llamada recursiva.
Pero es más... resulta que la pila de llamadas tiene un tamaño LIMITADO y en principio DESCONOCIDO. Eso quiere decir que puede almacenar un número de llamadas limitado y que no sabemos cuál es. En el método recursivo, existirá un valor de n que provocará un error de ejecución conocido como desbordamiento de pila o stack overflow... y lo peor es que a priori no podemos saber cual es ese valor. Este problema es inherente a la recursividad, y aparece potencialmente en todas las implementaciones recursivas. Además, su comportamiento no tiene por qué ser regular. Es posible que en una ejecución se produzca con un valor de n, y en otra con otro... ya que depende de lo que cabe en la pila de llamadas en el momento de la ejecución del método. Además, si ejecutamos el mismo método en distintas plataformas, obtendremos el desbordamiento de la pila con valores muy dispares, ya que cada compilador, intérprete, CPU o sistema operativo asignará a nuestro problema un espacio distinto de pila de llamadas.
Cierto es que en el procedimiento iterativo corremos otros riesgos... por ejemplo, que el valor del factorial se haga tan grande que no quepa en una variable de tipo int, pero ese riesgo es controlable: yo sé cuál es la máxima capacidad de un int en C# (viene en cualquier manual), así que con unas pocas cuentas puedo saber qué valor de n puede darme problemas, y poner mecanismos para solucionarlo.
{mospagebreak title=El drama de Fibonacci}
EL DRAMA DE FIBONACCI
Si la implementación recursiva de la función factorial es, aparte de ineficiente, peligrosa por la posibilidad de provocar un desbordamiento de pila, hay otros problemas en los que la cantidad de llamadas que se producen aumentan muchísimo los riesgos y la ineficiencia. Un ejemplo sencillo de esto es la Sucesión de Fibonacci.
Nuevamente, la definición en terminos recursivos de la sucesión de Fibonacci es muy elegante y sencilla de entender:
-El primer y segundo término de la sucesión (n=1 y n=2) es 1
-Del tercero en adelante (n>2), es la suma de los dos términos anteriores.
En un lenguaje un poquito más matemático...
fib(1)=1 fib(2)=1 fib(n)=fib(n-1)+fib(n-2) cuando n>2
Precioso... lo digo en serio. Es el colmo de la elegancia. Definimos dos casos base (n=1 y n=2), y el resto se definen en función de los dos inmediatamente anteriores.
Por ejemplo, el término tercero (n=3) es la suma de los dos casos base, es decir, 2. El cuarto es la suma del tercero (2) y el segundo (1), es decir, 3. El quinto es la suma del cuarto (3) y del tercero (2), es decir, 5... y así sucesivamente.
Sin embargo, computacionalmente hablado, implementar la función de Fibonacci en estos términos recursivos no es tan elegante, aunque pudiera parecerlo.
static int fib(int n) {
int resultado;
if (n==1)
resultado=1;
else if(n==2)
resultado=1;
else
resultado=fib(n-1)+fib(n-2);
return resultado;
}
En esta función, si la invocamos, por ejemplo con n=6, debemos tener en cuenta que al no ser un caso base, se vuelve a invocar recursivamente DOS veces, con n=5, y con n=4. A su vez, cada una de esta, necesita DOS llamadas más, y cada una esas DOS más... y así hasta llegar a los casos base, que no necesitan una nueva llamada, y son los que cortan esta cascada de llamadas recursivas.
Si represento estas llamadas recursivas gráficamente, el resultado es una estructura arborescente binaria, con una profundidad que depende del n inicial.
En esta representación, en cada círculo se representa el valor de n para una invocación de la función, empezando con n=6. Para calcular fib(6), es necesario calcular fib(5) y fib(4)... y para calcular fib(4) es necesario calcular fib(3) y fib(2).... y así sucesivamente. La recursividad se corta con fib(2) o fib(1), que son los casos base. ¡Imagina el tamaño del gráfico para calcular fib(25)!... tendría unos 150000 nodos.
La cantidad de llamadas que son necesarias para calcular fib(6), es de 15 nada menos. En un instante dado, la cantidad de llamadas máxima que hay es de 5 (la profundidad del arbol).
Pero hay otra cosa que asombra más todavía... fíjate que fib(4) se calcula dos veces, y que fib(3) se calcula tres veces. Realmente sólo es necesario hacerlo una vez. ¿Para qué tantas?... bueno... por la propia implementación recursiva de la función. Calcular fib(100) con este algoritmo haría una y otra vez lo mismo tantas veces que tardaría una barbaridad en finalizar.
Por supuesto, en el caso de la sucesión de Fibonacci también es sencillo obtener una versión iterativa.
Basta percatarse de que para calcular fib(6) podemos empezar por calcular fib(1) y fib(2), que son muy fáciles por ser los casos base, y anotarlo, por ejemplo, en un par de variables.
a=1 //fib(1)
b=1 //fib(2)
Sabiendo esto, ¿Puedo calcular fib(3) con el contenido de a y b?... Por supuesto... voy a almacenarlo en una variable llamada c.
a=1 //fib(1)
b=1 //fib(2)
c=2 //fib(3)
Para calcular fib(4) necesito conocer fib(3) y fib(2)... Vamos a aplicar el ingenio. Ya no necesito fib(1), contenido en a, así que voy a "desplazar" el contenido de las variables... voy a almacenar fib(2) en a, y fib(3) en b, dejando libre c. En ese c, voy a almacenar fib(4), simplemente sumando a y b
a=1 //fib(2)
b=2 //fib(3)
c=3 //fib(4)
Repito la operación para fib(5)
a=2 //fib(3)
b=3 //fib(4)
c=5 //fib(5)
Otra vez para fib(6)
a=3 //fib(4)
b=5 //fib(5)
c=8 //fib(6)
Anda... ya he llegado. Tengo almacenado en c el valor de fib(6)... Cuatro iteraciones y tres variables... y en ningún momento calculo más de una vez ningún termino de la sucesión.
Esta función implementa esta solución. (Tomada del artículo Sucesión de Fibonacci)
static int Fibonacci(int n)
{
if (n < 3) //los dos primeros terminos son 1
return 1;
else // a partir del tercero
{
int a = 1;
int b = 1;
int contador = 2;
int c;
do
{
contador++; //término que calcula esta iteración
c = a + b; //calcular término
//preparo las variables para la próxima vuelta
a = b;
b = c;
} while (n != contador);
return c;
} //fin else
}
Con esta implementación, calcular fib(100) toma apenas un instante, mientras que con la implementación recursiva toma una cantidad de tiempo que escapa de lo razonable en un entorno productivo.
{mospagebreak title=Conclusión}
En ningún momento quiero dar la impresión de que la recurisividad en programación sea intrínsecamente mala. Nada más lejos de mi intención.
La recursividad en la programación es una herramienta fantástica para expresar muchos algoritmos de manera sencilla. Nos sirve para experimentar con facilidad, resolver muchos problemas de manera sencilla y elegante, demostrar propiedades acerca de los algoritmos y un montón de cosas más. Pienso sinceramente que su dominio por parte de cualquier programador es imprescindible. Grandes desarrollos en el campo de los compiladores, los fractales, la compresión de datos...y un sinfín más hubieran sido mucho más difíciles sin una primera aproximación recursiva.
Pero desde el punto de vista de un entorno productivo, es decir, cuando se requiere una explotación de una aplicación de una manera lo más segura y eficiente posible, la recursividad suele presentar una gran ineficiencia, y el peligro inherente y difícilmente controlable de un desbordamiento de pila. En estos entornos, si hemos utilizado recursividad durante el desarrollo es altamente recomendable obtener una solución iterativa equivalente para la versión en producción, que podremos controlar con mucha mayor eficacia.
Esta solución iterativa se puede lograr siempre. En algunos casos sencillos (como los que hemos visto del factorial o de la sucesión de Fibonacci) basta con dedicar un pequeño análisis al significado de la función para encontrar una serie de pasos repetitivos que nos lleven a la solución.
Estos casos son sencillos de resolver porque nos podemos dar cuenta de que la cantidad máxima de información (dicho de otro modo, de memoria, de variables locales y parámetros) que necesitamos para resolver el problema en un instante dado está perfectamente acotada, y a medida que vamos solucionando casos nuevos, podemos ir descartando la solución de casos antiguos. Por ejemplo, en la sucesión de fibonacci sólo necesitamos en un instante dado conocer los dos casos anteriores... por eso para calcular fib(6) empezamos por fib(1) y fib(2), y cuando calculamos fib(3) nos deshacemos de fib(1), porque no lo volveremos a necesitar... cuando calculamos fib(4) nos deshacemos de fib(2)... y asi hasta llegar a fib(6). Sólo necesitamos fib(4) y fib(5). (Estos son esquemas de problemas en los que podemos aplicar programación dinámica)
Existen no obstante otros problemas que tienen solución recursiva en los que esta cantidad máxima de memoria necesaria no puede acotarse... Es decir... no podemos "deshacernos" de porciones de información, y quedarnos sólo con las últimas generadas. En ese caso, podemos aplicar una transformación recursivo-iterativa metódica. En estas transformaciones, lo que hacemos es sustituir las llamadas recursivas por un bucle y una estructura dinámica de tipo pila. Esa bucle y la estructura deben sustituir al trabajo que hace la pila de llamadas durante la recursión. Al construir una pila con memoria dinámica, podemos controlar en todo momento su tamaño y otras propiedades, cosa que no ocurre con la pila de llamadas... pero de eso hablaremos en otro artículo.
