Factorial en C

Más ejercicios resueltos

Si deseas revisar más ejercicios resueltos, haz click en el siguiente botón. 

Calcular el factorial de un número es uno de los problemas clásicos que se suelen analizar cuando se inicia en el mundo del paradigma de programación modular. Es típico que se desarrollen ejemplos de la función factorial en esta fase. En este artículo, analizamos al detalle y paso a paso, funciones para el cálculo del factorial en ANSI C presentando 5 alternativas de solución a través de diversas versiones usando estructuras algorítmicas iterativas, la recursión así como la programación dinámica. Si deseas conocer con más detalle la definición del factorial usada en este problema, haz click en el siguiente enlace.

Parte de esta análisis se encuentra sintetizado en el vídeo «Factorial Iterativo en ANSI C» en nuestro canal de YouTube. Te invitamos a que lo visites.

A continuación presentamos las 5 alternativas de solución que nos permitirán entender cómo se calculan los factoriales en ANSI C. Se analizará cada alternativa con sumo detalle. Las versiones que se analizarán son las siguientes:

  • Función principal. 
  • Versión usando la instrucción \texttt{while}.
  • Versión usando la instrucción \texttt{do..while}.
  • Versión usando la instrucción \texttt{for}.
  • Versión recursiva.
  • Versión usando Programación Dinámica.

Función principal

Realizaremos la implementación de la función \texttt{main}. Este será la misma para las primeras 4 versiones. Tiene básicamente 3 objetivos:

  •  Leer el dato de entrada.
  • Validar el dato leído.
  • Invocar a la función que va a realizar el cálculo del factorial.

 

Para la lectura de datos se utiliza la función \texttt{scanf}. Recuerde que para poder usar esta función, se debe incluir el archivo de cabecera \texttt{stdio.h} (Standard Input Output). El dato leído será almacenado en la variable \texttt{n}.
 
La validación la realizaremos con una selectiva doble que en ANSI C se implementa con la estructura de control \texttt{if..else}. Se emitirá un mensaje informativo si es que el número es menor 0 pues el factorial no está definido para números negativos o si el número es mayor que 20. Pero, ¿por qué no dejamos que el número n sea mayor que 20? Pues, como ya vimos antes, sucede que las factoriales incrementan su magnitud muy rápido y en ANSI C el factorial de 21, sobrepasa el rango de representación permitido para el tipo de dato \texttt{long} que usaremos para representar el factorial.
 
Una vez que la variable se ha validado, se procede a invocar a la función factorial usando como argumento el número \texttt{n} leído. La invocación se realiza al momento de realizar la impresión. En la impresión, además, estamos incluyendo al lado del número, el carácter de admiración (!) para que se imprima el número con la notación más conocida para el factorial. 
#include<stdio.h>

long factorial(int n);

int main() {
    int n;
    printf("Ingrese número n (0<=n<=20): ");
    scanf("%d", &n);

    if (n < 0 || n > 20)
        printf("Debe ingresar un número en el rango [0..20]");
    else
        printf("%d!=%li", n, factorial(n));
    return 0;
} 

Función Factorial: versión con instrucción while

Pasaremos ahora a diseñar la primera versión. Esta versión permitirá calcular el factorial de un número en ANSI C usando un ciclo while. Antes de describir la implementación, analizaremos los datos de entrada y de salida de esta función. La función factorial recibe como parámetro el número \texttt{n}. Este parámetro se ha definido con el tipo de dato \texttt{int} que permite representar números enteros en C. Se asume que este número \texttt{n} es mayor o igual que cero. La función retorná el factorial del parámetro \texttt{n}. Dado que el factorial puede contener magnitudes muy grandes, se ha optado por definir como tipo de dato del valor de retorno, \texttt{long}. El tipo de dato \texttt{long} permite retornar enteros largos en C y poseen mayor rango de representación que las variables de tipo \texttt{int}.

El siguiente paso a realizar es el control de flujo. La implementación de esta versión se basa en una estructura iterativa con entrada controlada. Diseñaremos el control de flujo usando un contador, al que se le suele denominar variable de control. Hemos nombrado esta variable de control con el identificador \texttt{i}. Como deseamos generar todos los factores de la productoria, inicializamos la variable de control con el valor de 2. La iniciamos en 2  dado que 1 es el elemento neutro para la nultiplicación, por lo tanto multiplicar por 1 no afecta en nada a la productoria. De esta manera nos ahorramos una iteración.

En ANSI C, la entrada controlada se implementa mediante la instrucción \texttt{while}. Colocamos como condición de la iteración \texttt{i<=n}. Esto significa que la iteración se realizará mientras esta condición se cumpla. Como tenemos que garantizar que la iteración finalice en algún instante del tiempo, actualizamos la variable de control. Al finalizar de la iteración, incrementamos su valor en 1. De esta manera en la próxima iteración \texttt{i} contendrá el valor del siguiente factor a utilizar para el cálculo de la productoria. Para el incremento hemos usado el operador unario \texttt{++}. Recuerde que \texttt{i++} equivale a \texttt{i=i+1}

La productoria se almacena convenientemente en la variable llamada \texttt{productoria}. La productoria ha sido definida con el tipo de dato \texttt{long}, pues es el valor que deseamos retornar y como ya vimos anteriormente, los factoriales suelen ser números muy grandes que exceden rápidamente el rango de representación del tipo de dato \texttt{int}. Inicializamos a la productoria con el valor de 1 por ser el elemento neutro para la multiplicación. Y actualizamos su valor dentro de la iteración. En la actualización simplemente multiplicamos el valor de la \texttt{productoria} por \texttt{i}, nos aseguramos que esta actualización se realice antes de actualizar la variable \texttt{i}.

El valor que retorna la función se indica a través de la sentencia \texttt{return}.

long factorial(int n) {
    long productoria = 1;
    int i = 2;
    while (i <= n) {
        productoria *= i;
        i++;
    }
    return productoria;
} 

Función Factorial: versión con instrucción do..while

Pasaremos ahora a diseñar la segunda versión. Esta versión permitirá calcular el factorial de un número en ANSI C usando un ciclo do while. En ANSI C la salida controlada, se implementa mediante la instrucción \texttt{do–while}.  

Esta instrucción se caracteriza por repetir el conjunto de instrucciones asociado mientras la condición de iteración se cumpla. Pero, a diferencia de la entrada controlada, en la salida controlada, el control de flujo se gestiona luego de la ejecución del bloque de instrucciones asociado a la estructura iterativa. En términos prácticos, esto significa que en una salida controlada, el bloque de instrucciones se ejecuta siempre por lo menos una vez.

Por esta razón, no podemos inicializar la variable de control \texttt{i}  con el valor de 2 ya que dentro de la iteración la variable \texttt{productoria}  se multiplica por \texttt{i} . Como esto se ejecuta por lo menos una vez, no permitirá calcular el factorial de cero ni de uno, por este motivo, la variable de control \texttt{i}  se debe inicializar con el valor de 1.

long factorial(int n) {
    long productoria = 1;
    int i = 1;
    do {
        productoria *= i;
        i++;
    } while (i <= n);
    return productoria;
} 

Función Factorial: versión con instrucción for

A continuación, procederemos a analizar la implementación del cálculo del factorial usando la instrucción for en ANSI C. La instrucción \texttt{for} se comporta como un ciclo iterativo con entrada controlada. Y como tal, utiliza tipicamente una variable de control, una condición de iteración y una actualización de dicha variable de control.

En el caso del cálculo del factorial, la variable de control la hemos llamado \texttt{i} y la inicializamos en 2. La condición de iteración es \texttt{i<=n}, lo que significa que se iterará hasta que el valor de \texttt{i} sea igual a \texttt{n} y cada vez que se termine la iteración, la variable se incrementa en 1. La ventaja que ofrece la instrucción \texttt{for} es que la inicialización de la variable de control, la condición de iteración y la actualización de la variable de control, se configura en un solo lugar, a diferencia de las otras estructuras algorítmicas iterativas.

La iteración producirá diferentes valores de \texttt{i} en cada ciclo, usamos este hecho para generar la productoria deseada. Para esto se inicializa la \texttt{productoria} en 1  y en cada ciclo, se multiplica por el valor de \texttt{i}.

long factorial(int n) {
    long productoria;
    int i;
    for (i = 2, productoria = 1; i <= n; i++)
        productoria *= i;
    return productoria;
}
 

Función Factorial: versión recursiva

La cuarta versión a implementar es la versión recursiva. Quizás sea la más simple de entender pues prácticamente es la representación en ANSI C de la definición recursiva. Los algoritmos recursivos suelen ser simples de implementar pero en muchas ocasiones no son tan eficientes como las implementaciones iterativas.

long factorial(int n) {
    if (n<=1)
        return 1;
    return n*factorial(n-1);
}
 

Función Factorial: versión usando Programación Dinámica

Algoritmos como el cálculo de factorial poseen una característica, para hallar el valor de n!, debe calcularse (n-1)!. Esto se realiza independientemente de la versión y no importa si la versión es iterativa o recursiva.

Esto no ofrecería ningún problema si es que la función se ejecuta una sola vez, pero ¿qué pasa cuando en un programa necesitamos invocar varias veces a la función factorial? Pues, en ese caso las soluciones implementadas no serian eficientes. Por ejemplo, imagínese que hacemos las invocaciones a las funciones \texttt{factorial(4)}\texttt{factorial(6)}. En este caso hipotético se calcularían dos veces el \texttt{factorial(4)} lo que es un uso innecesario de tiempo.

¿Cómo evitamos recalcular tantas veces los factoriales? Pues existe una técnicas de programación llamada programación dinámica que justamente busca reducir el tiempo de ejecución de los algoritmos. Esto lo logra reusando resultados obtenidos previamente. Estos resultados suelen ser almacenados en arreglos o matrices. 

Función principal

Vamos a diseñar la función principal para el cálculo del factorial. Hay ligeros cambios en relación a las versiones anteriores. Los dos primeros objetivos son los mismo pero el tercer y cuarto son diferentes.

  •  Leer el dato de entrada.
  • Validar el dato leído.
  • Invocar al módulo que va a realizar la inicialización del arreglo.
  • Retornar el valor del factorial usando el arreglo inicializado.
 
 
El primer gran cambio que vemos es que no existe una función \texttt{factorial}. Entonces ¿cómo se hace para hallar el valor del factorial? Pues en lugar de ello se usa un arreglo, al que convenientemente hemos denominado \texttt{factorial}. Dicho arreglo va a contener el valor de los factoriales de forma que \texttt{factorial[0]} contendrá el valor del factorial de \texttt{0}, \texttt{factorial[1]} contendrá el valor del factorial de \texttt{1} y en general \texttt{factorial[n]} contendrá el valor del factorial de \texttt{n}.

Resulta muy sencillo el retornar los factoriales pero ¿cómo se inicializa dicho arreglo? Pues este es en realidad el problema de la programación dinámica. Debemos llenar el arreglo con el valor de los factoriales antes de usar el arreglo. Esta inicialización la debemos hacer una única vez durante todo el algoritmo.

El arreglo ha sido declarado con la instrucción \texttt{long factorial[MAX\_FACTORIALES+1]}. Esto significa que el arreglo tendrá 21 elementos. Los índices válido para el arreglo serán [0..20]. Creamos un arreglo cuyo máximo índice es el valor de 20 debido a que es el máximo factorial que se puede representar en ANSI C.

#include<stdio.h>
#define MAX_FACTORIALES 20

void inicializar_arreglo(long* factorial);

int main() {
    int n;

    long factorial[MAX_FACTORIALES + 1];    

    printf("Ingrese número n (0<=n<=20): ");
    scanf("%d", &n);

    if (n < 0 || n > MAX_FACTORIALES)
        printf("Debe ingresar un número en el rango [0..20]");
    else{
        inicializar_arreglo(factorial);
        printf("%d!=%li", n, factorial[n]);
    }
    return 0;
} 

Inicialización del arreglo

A continuación presentamos el algoritmo para inicializar el arreglo. Básicamente lo que hacemos es inicializar el primer elemento con el valor de \texttt{0}. Luego en un ciclo iterativo, que en realidad puede ser usando cualquiera de las versiones previamente analizadas, se actualizan los demás elementos del arreglo. En dicha actualización siempre se usa el valor anterior.

void inicializar_arreglo(long* factorial) {
    int i;
    factorial[0] = 1;
    for (i = 1; i <= MAX_FACTORIALES; i++)
        factorial[i] = i * factorial[i - 1];
}
 

Conclusión

Hemos presentado en este artículo, 5 alternativas de solución al cálculo del factorial usando ANSI C. Se ha utilizado estructuras iterativas con entrada controladasalida controladarecursión y programación dinámica.  Podrá descargar la solución propuesta en el repositorio GitHub de iterando++ a través del siguiente enlace

Hemos preparado otros artículos adicionales en donde describimos al detalle la implementación de este problema PSeInt y en otros lenguajes de programación. Te invitamos a leer los siguientes artículos de iterando++

Si quieres profundizar en el lenguaje ANSI C, no hay mejor libro que C Programming Language de Brian Kernighan  y Dennis Ritchie. Es un libro clásico escrito por el creador del lenguaje C. Uno de los libros favoritos de los que inician en ANSI C es  C Programming Absolute Beginner’s Guide de Greg Perry y Dean Miller.

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *