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.