斐波那契数由“比萨的列昂纳多”（Leonardo of Pisa）得名，他的爱称是斐波那契。他于13世纪在一个关于兔子的数学问题中讨论了斐波那契数。最初有一对小兔。一个月后小兔长大为成年兔子，第二个月后它们会生下另一对小兔，这样就有两对兔子了：

下个月，小兔会长大，而成年兔会生下一对小兔：

再下个月，小兔又长大了，两对成年兔子都会生一对小兔：

假设没有兔子死去，并且兔子的繁殖能一直持续，那么每个月会有多少对兔子？

设A(n)为第n月时的成年兔子对数，B(n)为第n月小兔子的对数。那么第n月兔子的总对数设为T(n)，就是A(n) + B(n)：

T(n) = A(n) + B(n)

不难看出，某个月的小兔数目等于上个月的成年兔子数目，因为每对成年兔子都会生下一对小兔。用符号来表示就是B(n) = A(n - 1)。代换到公式里，得到：

T(n) = A(n) + A(n - 1)

每个月，成年兔子的数目等于上个月的兔子总数，因为上个月的小兔会成长为成年兔子，而上个月的成年兔子仍然活着。用符号表示，就是A(n) = T(n - 1)。代入前面的公式，得到：

T(n) = T(n - 1) + T(n - 2)

这样，第n月的兔子总数就是第n - 1月和第n - 2月的兔子数值和。使用这个公式，可以写出计算斐波那契数的函数：

# 计算给定的第n月中兔子的对数
sub fib {
  my ($month) = @_;
  if ($month < 2){1}
  else {
    fib($month-1) + fib($month-2);
  }
}
				

这段程序十分直观，但它有个问题：除非是极小的参数，否则它会花费掉大量时间 ^[4] 。例如，求fib(25)需要递归地计算fib(24)和fib(23)。但调用fib(24)同样会递归调用fib(23)，再调用fib(22)。两次对fib(23)的调用还会去调用fib(22)，这样它就总共被调用3次。其结果是，fib(21)会被计算5次，fib(20)会被计算8次，fib(19)会被计算13次。

这些计算和重复计算都会付出沉重的代价。在我的小型计算机上，计算fib(25)需要大约4秒，进行了242,785次递归调用。计算fib(26)约需要6.5秒，进行392,835次递归调用，fib(27)需要10.5秒，进行635,621次递归调用。计算fib(27)的时间等于计算fib(25)和fib(26)值和，因此函数的执行时间会迅速增长，参数每增加2，时间要增长两倍以上。 ^[5]

运行时间的爆炸速度十分迅猛，这全都是因为需要重复计算已经计算过的内容。递归函数有时会有这个问题，不过在第3章[TODO]我们将看到一个简单的解决方法。

斐波那契数比较深奥，很难找到需要计算它的简单的实际例子。

下面这个例子更实际些。设想有一些值钱的东西，称之为“财宝”，现在需要将它们平均分给两个人。每个东西的价值是已知的，需要确保两个人拿到的东西的总价值相同。或者换个更通俗的说法：已知今天购买的每样东西的重量，现在要两只手各拿一个袋子把它们拎回去，就需要平均地分配重量。

这需要相当的技巧，不信的话可以试着分一下下面这些价值的物品：

$9，$12，$14，$17，$23，$32，$34，$40，$42，$49

由于所有物品的总价值为$272，所以每个人应当分得$136。再试试这个：

$9，$12，$14，$17，$23，$32，$34，$40，$38，$49

这里我将$42的东西换成了$38，这样每个人只能分到价值$134的东西。

这个问题称为剖分问题（partition problem）。更一般地，不是将一堆财宝分成相等的两部分，而是找出一部分财宝，其总价值等于给定的数量。等分两份等同于找出价值等于总价值的一半的财宝，这样剩下的另一半的价值也是相同的。

如果找不出总价值等于给定目标的那部分的话，函数将返回undef：

sub find_share {
  my ($target, $treasures) = @_;
  return [] if $target == 0;
  return if $target<0|| @$treasures == 0;
				

先来看看简单的情况。如果目标数量恰好是零，那么产生这样的一部分财宝满足总价值就十分容易。空列表的总价值必然是零，所以就直接返回它。

如果目标数量小于零，就是不可能实现的，因为我们假定财宝永远是正值。此时问题无解，所以函数可以立即返回失败。如果没有任何财宝，那么因为已知目标值必然大于零，所以判断出无解，立即判定失败。

否则，目标数量是正值，需要进行真正的处理：

  my ($first, @rest) = @$treasures;
  my $solution = find_share($target-$first, \@rest);
  return [$first, @$solution] if $solution;
  return find_share($target , \@rest);
}
				

首先复制财宝的列表，然后将第一个财宝从列表中删除。这是因为我们要考虑该问题的简单情况：去除第一个元素后如何剖分。有两种可能的分法：结果中或者包含有第一个财宝，或者不包含。如果包含第一个财宝，就得在剩下的财宝中找出一个子集，它的总价值等于$target - $first。如果不包含，那就得在剩下的财宝中找出总价值等于$target的子集。因此，其余这段代码就递归调用find_share，分别研究这两种情况。如果第一种情况可行，函数就返回包含第一个财宝的结果；如果第二个方案可行，就返回不包含第一个财宝的结果；如果都不可行，就返回undef。

下面是实际执行的例子。调用find_share(5, [1, 2, 4, 8])：

现在不满足任何简单情况——目标既不是负数也不是零，剩下的财宝列表也非空，因此函数取出第一个元素1放到结果中，然后尝试从剩下的财宝中找出总价值为4的子集：

函数将继续尝试，直到不得不放弃。

接下来函数将剩余元素中的第一个2取出，由于目标值为4，所以执行递归调用，从剩下的两个元素中找出总和等于2的子集：

称这种情况为“方案a”。函数会继续尝试该方案，直到得出方案a无解的结论。它尝试将4放到结果中，但那就超过了给定目标：

因此退回一步，从方案a开始尝试不包含4的情况：

结果仍然未达到目标，于是向结果中加入下一个元素8，显然它超了：

此时$target < 0，所以函数失败，然后尝试忽略8。但这也不行，因为此时结果与目标相比还差2，却没有任何元素可以分配了：

这就是if (@$treasures == 0) { return undef }的情况。

函数已尝试了方案a的所有可能解法，然而全部失败了。这样就能推断，将1和2都放在结果中是不可行的，因此后退一步，尝试忽略2：

现在尝试在结果中加入4：

此时函数得到$target == 0，于是返回成功。这样，已分配的财宝是1和4，总和等于目标5。

通过忽略第一个财宝，从其余的财宝中找答案，从而降低问题的难度的思路很自然。就算是不使用递归的解决方案，很可能最终也要复制递归解决方案的基本结构，并手工模拟函数调用的栈。

这样剖分问题就很容易解决了，只需调用find_share()，找出第一部分，再通过某种方法计算出原数组中未包含在第一部分结果中的那些元素：

sub partition {
  my $total = 0;
  my $share_2;
  for my $treasure (@_) {
    $total += $treasure;
  }

  my $share_1 = find_share($total/2, [@_]);
  return unless defined $share_1;
				

首先，函数计算所有财宝的总值。然后调用find_share()，求出总值恰好等于原数组的总值的一半的子集。如果find_share()返回了未定义值，说明无法等分，于是partition()马上返回失败。否则，就开始计算没有包含在$share_1中的那些财宝，这些就是第二部分：

    my %in_share_1;
    for my $treasure (@$share_1) {
      ++$in_share_1{$treasure};
    }

    for my $treasure (@_) {
    if ($in_share_1{$treasure}) {
      --$in_share_1{$treasure};
    } else {
      push @$share_2, $treasure;
    }
  }
				

该函数使用散列来计算第一部分中每个值出现的次数，然后依次检查原始数组。如果某个财宝在第一部分中出现过，就将它减掉，否则将它放在另一个构成第二部分的列表中。

  return ($share_1, $share_2);
}
				

处理完成后，就返回两个财宝的列表。

代码不少，但大部分都是在处理列表分割。关键的一行是调用find_share()的那一行，它计算真正的答案$share_1。其余的代码都是在求不在$share_1中的财宝的列表$share_2。

但是，find_share函数有个问题。执行它要耗费大量时间，特别是无解的情况。它与fib的问题本质上相同：反复重复同样的工作。例如，假设它尝试从1 2 3 4 5 6 7中找出总和为14的部分。它会从包含1和3的结果开始，尝试是否能让5 6 7满足总和为10的目标。结果是不能，所以它会继续寻找其他方案。稍后，它会从包含4的结果开始，再次尝试是否能让5 6 7满足10的目标。显然这是在浪费时间，find_share应该在第一次尝试后就记住5 6 7不能满足总和10的目标。

我们将在第三章[TODO]讨论如何改正这一点。