Раздел «Язык Си».Factorial:

Факториал

Факториал числа n это произведение первых n натуральных чисел:

n! = 1\cdot 2 \cdot \ldots \cdot n.

В приведенной ниже программе определена функция factorial, вычисляющая факториал.

#include <stdio.h>
long factorial(long x)
{ 
    if( x == 0 ) return 1;
    return x * factorial (x - 1);
}
void main()
{
    long n;
    while( scanf("%ld", &n) == 1)
      printf("%ld\n", factorial (n));
}

Это определение основано на следующей рекуррентной формуле:

n! = n\cdot (n-1)!, \quad 0! = 1.

Для вычисления факторила n! эта функция вызывает саму себя с аргументом n-1

Если бы не было строчки

if( n == 0 ) return 1;
то функция factorial постоянно бы вызывала саму себя, и во время выполнения программы мы получили бы сообщение об ошибке "переполнение стека" или "превышена глубина рекурсии". Для того, чтобы этого не было, необходимо, чтобы при некоторых значения аргумента, функция не вызывала саму себя, а вычисляла свое значение "самостоятельно".

Идея рекурсии заключается в сведении задачи к этой же задаче, но для более простых случаев (например, для меньшего значения аргумента n). Процесс сведения задачи к предыдущей должен когда-нибудь заканчиваться, поэтому рекурсивные функции для простейших входных данных должны "знать", чему они равны и не делать рекурсивных вызовов.

Задания

  1. Улучшите программу, добавив к ней защиту от дурака: если
n < 0, то программа должна по-прежнему адеватно работать, например, сообщать, что факториал для отрицательных чисел не определен, и не вызывать Runtime error — ошибку выполнения программы.