Рекурсивное вычисление факториала на языке Си

Рассмотрим вычисление факториала с помощью рекурсивной функции.

Факториал вычисляется по следующей формуле:

Для его нахождения будем использовать рекурсивную функцию. Рекурсивная функция — это функция, которая вызывает сама себя.

Начнем писать программу. Подключим необходимые библиотеки и напишем рекурсивную функцию factorial(n):

#include <stdio.h>
#include <conio.h>

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

#include <stdio.h>

#include <conio.h>

long int factorial(long int n)

{

if (n == 0 || n == 1) return 1;

return n * factorial(n - 1);

}

Разберем функцию подробнее. Будем работать с типом данных long int — это длинный целый тип. Для нашей программы этот тип подходит лучше всего, потому что факториал — чрезвычайно быстрорастущая функция. Условие if (строка 6) — условие остановки рекурсии.

Рассмотрим пример. Допустим необходимо вычислить факториал пяти (n=5). Вызываем функцию factorial(5), условие остановки не срабатывает, переходим к оператору return (строка 7). Умножаем n на то, что вернет функция factorial(n — 1), вычисляем эту функцию: в нее мы передаем число 4 (5-1=4). То есть мы спускаемся на уровень ниже. И так мы будем спускаться вниз да тех пор, пока n не станет равным единице или нулю, тогда сработает условие остановки рекурсии. Функция вернет 1. Единица будет умножена на n (=2), и так, по уровням, будем подниматься наверх, умножая на текущее для конкретного уровня число n то, что вернет функция с уровня, который ниже. В результате мы получим значение факториала.

Примечание. Факториал нуля равен единице (0!=1).

Теперь напишем функцию main():

int main ()
{
    long int n;
    printf("Calculation n!\nInput n: ");
    scanf_s("%d", &n);
    if (n >= 0)
        printf("%d! = %d\n", n, factorial(n));
    else
        printf("Error. n must be >= 0\n");
    _getch();
    return 0;
}

int main ()

{

long int n;

printf("Calculation n!\nInput n: ");

scanf_s("%d", &n);

if (n >= 0)

printf("%d! = %d\n", n, factorial(n));

else

printf("Error. n must be >= 0\n");

_getch();

return 0;

}

В ней мы просим пользователя ввести число n и считываем его с клавиатуры. Далее выполняем проверку: число n должно быть больше или равно нулю. Если условие выполняется, то вычисляем факториал и выводим его значение на экран, если условие не выполняется, то выводим в консоль сообщение об ошибке.

Демонстрация работы программы представлена на рисунке: