假设有一组由n个不同的元素。为说明得具体些，我们假设这些元素是英文字母。那么，它们有多少种不同的排列顺序？显然，结果取决于n，所以结果是n的函数。该函数称为阶乘函数（factorial function）。n的阶乘就是n个不同元素的不同排列顺序的数目。数学家通常用感叹号来表示，所以n的阶乘可以写为n!。不同的顺序也称为排列（permutation）。 下面来计算几个阶乘。显然，一个元素的排列方法只有一种，所以 1!=1。两个元素有两种排列方式：A-B和B-A，因此 2!=2。稍稍动一动笔，就会发现三个元素有六种排列方式：

C  AB      C  BA
A C B      B C A
AB  C      BA  C
			

怎样才能保证没有漏掉任何情况？找出一个构建每一种可能的组合的方法并不难，在第4章(TODO)我们将介绍一个程序，它能列出所有排列。这里介绍另一种方法。在由两个元素组成的排列中添加一个新元素，就能组成含有三个元素的任意排列。两个元素的排列有两种情况：AB和BA。 每种排列下，都可以将C放在三个地方：开头，中间，或结尾。因此可作出的选择有 2·3 = 6 中，并且由于每种选择都会生成不同的排列，所以总共必然有六种排列。上述列表的左边那一列是将C插入到AB中的情况，右边那列是将C插入到BA的情况，所以上述结论是完整的。

类似地，如果想知道四个元素有多少种排列，可以使用同样的方法。三个元素有六种排列，而插入第四个元素的位置有四个，所以总共有 6·4 = 24 种顺序：

D  ABC      D  ACB      D  BAC      D  BCA      D  CAB      D  CBA
A D BC      A D CB      B D AC      B D CA      C D AB      C D BA
AB D C      AC D B      BA D C      BC D A      CA D B      CB D A
ABC  D      ACB  D      BAC  D      BCA  D      CAB  D      CBA  D
			

接下来我们要写一个函数，对于任意n，它可以计算n个元素的排列数目。

刚才我们看到，如果知道了n - 1个元素的可能的排列数，就可以计算n个元素的排列数。从n - 1个元素的(n - 1)!种排列中取出一种，然后将第n个元素插入到排列中的n个可能的位置中，就可以得到n个元素的一种排列。因此，n个元素的总排列数为(n-1)!·n：

sub factorial {
  my ($n) = @_;
  return factorial($n-1) * $n;
}
			

哎呀，这个函数不行，不论给什么输入，都不会产生任何结果，原因是我们忘记了终止条件。要计算factorial(2)，它首先会去计算factorial(1)。要计算factorial(1)，它首先会去计算factorial(0)。要计算factorial(0)，它首先会去计算factorial(-1)。无穷无尽。要改正这一点，只需明确地告诉函数0!的值是什么，这样当它执行0时，就不需要再递归调用了：

sub factorial {
  my ($n) = @_;
  return 1 if $n == 0;
  return factorial($n-1) * $n;
}
			

现在它就可以正确执行了。

至于为何0的阶乘是1，恐怕并不是那么一目了然。回过头来看看阶乘的定义。factorial($n)是给定的$n个元素的不同排列的数目。factorial(2)等于2，因为两个元素有两种排列：('A', 'B')和('B', 'A')。factorial(1)等于1，因为一个元素只有一种排列：('A')。factorial(0)等于1，因为零个元素只有一种排列方式：( )。可能有人要说0!应该等于0，但从上面( )的例子可以清楚地看到并非如此。

在递归函数中正确地选择基线操作极其重要，如果弄错了，函数的所有其他结果也都不会正确。如果前面的函数没有return 1，而是错误地return 0，那么它就无法计算阶乘，而是永远返回零。

sub factorial {
  ($n) = @_;
  return 1 if $n == 0;
  return factorial($n-1) * $n;
}