Хранить число, факториал которого нужно вычислить, мы будем в переменной $n. Можно было бы в самом начале текста программы присвоить этой переменной нужное значение:

Perl
$n=7;

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

Сделаем так, чтобы число попадало в программу (в переменную $n) из командной строки:

Perl
$n=shift @ARGV;

Объяснения отложим на потом, а сейчас отнесёмся к этой строчке как к рецепту. Теперь при запуске программы

% ./factorial.pl 13

в переменной $n будет число $13$.

Для практического вычисления выберем наиболее ясный (но далеко не единственный) подход: Заведём переменную $f, присвоим ей в начале единичное значение, а затем будем домножать по очереди на натуральные числа от $2$ до $n$.

Домножение переменной $f нужно повторить $n-1$ раз. При $n=7$ пришлось бы сделать так:

Perl
$f=$f*2;
$f=$f*3;
$f=$f*4;
$f=$f*5;
$f=$f*6;
$f=$f*7;

Но при больших $n$ текст программы станет ужасен. А самое главное, подобный приём не будет работать сразу для всех $n$, так как количество домножений станет известно лишь в начале исполнения программы.

Специальная конструкция for служит для организации повторяющихся действий (итераций), в том числе, когда количество итераций неизвестно на этапе программирования.

Приведём решение:

Perl
for($i=2; $i<=$n; $i=$i+1)
{
	$f=$f*$i;
}

В фигурных скобках помещается тело цикла. Это набор команд, которые будут выполняться ноль или больше раз, в зависимости от определённых условий. После ключевого слова for в круглых скобках три выражения, отделённые друг от друга точками с запятой. Первое — выражение инициализации, оно будет вычислено один раз в самом начале (у нас — переменной $i будет присвоено значение 2). Второе выражение (сравнение значений переменных $i и $n) — проверка условия. Оно вычисляется перед выполнением тела цикла. Тело будет выполнено лишь при этом условии. Наконец, третье выражение в круглых скобках отвечает за модификацию. Это выражение вычисляется каждый раз после выполнения тела цикла.

Между прочим, для присваиваний $i=$i+1 и $f=$f*$i имеются более короткие эквиваленты: $i+=1 и $f*=$i. Первое из присваиваний можно записать ещё короче: $i++.

Имеется очевидное соотношение, выражающее факториал числа $n$ через факториал $n-1$: $$n!=n\left(n-1\right)!\text{.}$$

Рекурсивная природа факториала даёт возможность испытать рекурсию на весьма простой задаче.

Если возложить вычисление факториала на процедуру factorial, приведённое соотношение позволяет реализовать эту процедуру рекурсивно.

Общая схема программы (независимо от того, рекурсивно ли реализована процедура factorial, или как-то иначе) будет такой:

Perl
sub factorial
{
	❶ тело процедуры
}

print factorial(shift @ARGV), "\n";

Первая попытка воплотить процедуру factorial (вставка ❶) приведёт нас к краху:

Perl
return $_[0]*factorial($_[0]-1);

% ./factorial-recursive.pl 7
Deep recursion on subroutine "main::factorial" at ./factorial-recursive.pl line 10.

(выполнение программы пришлось прервать, поскольку компьютер задумался всерьёз и надолго).

Чтобы разобраться в этой ошибке, проследим за последовательностью вычислений:

Perl
factorial(7)─╮
╭────────────╯
╰▶7*factorial(6)─╮
╭────────────────╯
╰▶7*(6*factorial(5))─╮
╭────────────────────╯
╰▶7*(6*(5*factorial(4)))─╮
╭────────────────────────╯
╰▶7*(6*(5*(4*factorial(3))))─╮
╭────────────────────────────╯
╰▶7*(6*(5*(4*(3*factorial(2)))))─╮
╭────────────────────────────────╯
╰▶7*(6*(5*(4*(3*(2*factorial(1))))))─╮
╭────────────────────────────────────╯
╰▶7*(6*(5*(4*(3*(2*(1*factorial(0)))))))─╮
╭────────────────────────────────────────╯
╰▶7*(6*(5*(4*(3*(2*(1*(0*factorial(-1))))))))─╮
╭─────────────────────────────────────────────╯
╰▶7*(6*(5*(4*(3*(2*(1*(0*(-1*factorial(-2)))))))))─╮
╭──────────────────────────────────────────────────╯
╰▶7*(6*(5*(4*(3*(2*(1*(0*(-1*(-2*factorial(-3))))))))))─╮
╭───────────────────────────────────────────────────────╯
╰▶…

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

Такую неограниченную рекурсию следует прервать вычислением факториала нуля, который, как известно, равен единице. Итак, вторая попытка:

Perl
$n=shift;
return 1 unless $n;	сразу возвращаем единицу для нулевого $n;
					тогда ниже расположенный код выполняться не будет
return $n*factorial($n-1);

И снова неудача:

% ./factorial-recursive.pl 7
0
% ./factorial-recursive.pl 6
0
% ./factorial-recursive.pl 5
0
% ./factorial-recursive.pl 4
0
% ./factorial-recursive.pl 3
0
% ./factorial-recursive.pl 2
0
% ./factorial-recursive.pl 1
0
% ./factorial-recursive.pl 0
1

Программа выдаёт верный результат лишь для нуля. Но случай нуля особенный: там исполнение тела процедуры factorial прекращается досрочно. Похоже, источник ошибки — последняя строчка тела процедуры:

Perl
return $n*factorial($n-1);

Посмотрим, что происходит при вычислении факториала единицы. Для выполнения команды

Perl
return $n*factorial($n-1);

необходимо вычислить выражение $n*factorial($n-1) (на момент начала вычисления значение переменной $n равно единице). Это выражение представляет собой произведение выражений $n и factorial($n-1). Чтобы вычислить произведение, нужно прежде вычислить его сомножители, которые нуждаются в вычислении. В нашем случае в вычислении нуждается лишь второй сомножитель — factorial($n-1), то есть factorial(0). Его значение после вычисления становится равным единице (для нуля процедура, как мы выяснили, работает верно). Но, кроме того, вычисление факториала нуля портит переменную $n:

Perl
$n=shift; здесь $n становится нулём
…

В дальнейшем вычисление выражения $n*factorial($n-1) сводится к вычислению выражения $n*1, но уже при нулевом $n — эта переменная испорчена предшествующим вызовом factorial(0). Теперь неудивительно, что факториал единицы вычислялся как ноль! Вычисление факториала двойки требует вычисления факториала единицы, поэтому и для двойки будет неправильный результат. Эта небольшая ошибка в алгоритме будет многократно растиражирована при вычислении факториалов бо́льших чисел.

Теперь понятно, в чём дело. Рекурсивные вызовы процедуры factorial не только производят вычисления по формуле, но и влияют на «окружающую среду»: меняют переменную $n, которой пользуются совместно. Они ведут себя подобно хозяйкам на коммунальной кухне, где плита с единственной конфоркой: первая хозяйка поставила борщ, затем явилась вторая, сняла борщ и поставила кашу, потом пришла третья, убрала недоваренную кашу и занялась блинами… Когда вернётся первая хозяйка, она вместо своего борща обнаружит чужие блины. Вот если бы у каждой из них была своя конфорка!

Примечание

Удивительно, но ситуацию способно исправить такое, казалось бы, бессмысленное изменение текста программы: замена первого сомножителя $n на выражение (0+$n): Perl return (0+$n)*factorial($n-1); Но это изменение влияет на порядок вычисления сомножителей; теперь первый множитель нуждается в вычислении и будет вычислен до рекурсивного вызова, то есть до порчи переменной $n. Однако такое программирование следует рассматривать как хулиганское. Сейчас мы узнаем, как избежать порчи переменных, «спрятав» их внутри тела процедуры.

Вот если бы у каждого вызова процедуры factorial была своя переменная! К примеру, у первого — $n, у второго — $k, и т. д. Но это невозможно, поскольку это разные вызовы одной и той же процедуры. Однако можно сделать так, чтобы имя $n в каждом вызове было связано со «своей» переменной. Для этого нужно объявить переменную как локальную с помощью команды my:

Perl
my $n;
$n=shift;
…

Можно совместить объявление с присваиванием:

Perl
my $n=shift;
…

Третья версия процедуры заработает правильно:

Perl
my $n=shift;
return 1 unless $n;
return $n*factorial($n-1);

Кстати, ту же самую мысль можно выразить короче:

Perl
my $n=shift;
return $n? $n*factorial($n-1): 1;

Ну и конечно, можно было совсем обойтись без переменной $n:

Perl
return $_[0]? $_[0]*factorial($_[0]-1): 1;

Это сработает, поскольку массив @_ ведёт себя так, как если бы он был объявлен при помощи my: вызываемая процедура получает свой собственный массив с параметрами.

Приведём схему вычислений факториала $7$ при правильной рекурсии:

Perl
factorial(7)─╮
╭────────────╯
╰▶7*factorial(6)─╮
╭────────────────╯
╰▶7*(6*factorial(5))─╮
╭────────────────────╯
╰▶7*(6*(5*factorial(4)))─╮
╭────────────────────────╯
╰▶7*(6*(5*(4*factorial(3))))─╮
╭────────────────────────────╯
╰▶7*(6*(5*(4*(3*factorial(2)))))─╮
╭────────────────────────────────╯
╰▶7*(6*(5*(4*(3*(2*factorial(1))))))─╮
╭────────────────────────────────────╯
╰▶7*(6*(5*(4*(3*(2*(1*factorial(0)))))))─╮
╭────────────────────────────────────────╯
╰▶7*(6*(5*(4*(3*(2*(1*1))))))─╮
╭─────────────────────────────╯
╰▶7*(6*(5*(4*(3*(2*1)))))─╮
╭─────────────────────────╯
╰▶7*(6*(5*(4*(3*2))))─╮
╭─────────────────────╯
╰▶7*(6*(5*(4*6)))─╮
╭─────────────────╯
╰▶7*(6*(5*24))─╮
╭──────────────╯
╰▶7*(6*120)─╮
╭───────────╯
╰▶7*720─╮
╭───────╯
╰▶5040

Испытания любой из рекурсивных версий на больших числах выявит неприятную деталь: начиная с числа $99$ верный результат будет сопровождаться предупреждением о глубокой рекурсии:

% ./factorial-recursive.pl 99
Deep recursion on subroutine "main::factorial" at ./factorial-recursive.pl line 12.
9.33262154439441e+155

Если рекурсия в ваших программах достигает столь опасных глубин, есть причина отказаться от рекурсивного подхода и обратиться к итеративному. Об опасностях рекурсии читайте раздел «Алгоритм Евклида (итеративная версия)» в главе 12. «Вычисление НОД».