1.8　当递归膨胀时

有时一个问题很明显是递归，然后递归方案很没有效率。一个非常简单的例子是计算Fibonacci数。这是个想象的例子，但它的优点就是非常简单。我们将在3.7节看到一个更实际的例子。

1.8.1　Fibonacci数

Fibonacci数（Fibonacci number）以Leonardo of Pisa 命名，他的别名是Fibonacci，他在13世纪联系一个关于兔子的数学问题探讨了它们。起初，你有一对兔宝宝。兔宝宝一个月就发育成年了，下一个月它们生育了一对新的兔宝宝，这样有两对了：

月份 兔宝宝的对数 成年兔的对数 总的对数

  1    1    0    1
  2    0    1    1
  3    1    1    2

再下一个月，兔宝宝发育，成年兔又生育了一对新的兔宝宝：

  4    1    2    3

之后一个月，兔宝宝发育，两对成年兔各生育一对兔宝宝：

  5    2    3    5

假设没有兔子死亡，且继续生育，那在每个月共有多少对兔子呢？

假设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月的兔子数量的总和。有了这个公式，就可以写下计算Fibonacci数的函数：

### Code Library: fib
# Compute the number of pairs of rabbits alive in month n
sub fib {
  my $n = shift;
  if ($n < 2) { return $n }
  fib($n-2) + fib($n-1);
}

这是非常直接的，但有个问题：除非是小的参数，否则就会一直运行。举个例子，如果你要算fib(25)，它需要递归调用计算fib(24)和fib(23)。但是调用fib(24)也要递归调用fib(23)，另一个调用也要计算fib(22)。两次fib(23)调用都要调用fib(22)，一共三次。结果是fib(21)计算5次，fib(20)计算8 次，fib(19)计算13次。

所有这些计算与重复的计算都会带来沉重的代价。在我的小计算机上，花费了大约4秒计算fib(25)，其间有242 785次递归调用。花费了大约6.5秒计算fib(26)，其间有392 835次递归调用，大约10.5秒进行635 621次递归调用计算fib(27)。 计算fib(27)的时间与计算fib(25)和计算fib(26)的总和时间差不多，因此函数的运行时间快速地增加，参数每增加2，时间将翻倍更多。

运行时间真的很快就无法承受了，这都是由于重复计算了已经计算过的东西。递归函数偶尔会有这样的问题，但是有一个简单的解决方案，将在第3章介绍。

1.8.2　划分

Fibonacci数有点深奥，也很难找到需要计算它们的简单而现实的程序实例。

这里有一个多少有点更现实的例子。有一些值钱的物品，称为“宝物”，想把它们平均分给两个人。知道每个物品的价值，希望确保每个人得到的物品的总价值相等。或者，把问题改得更平凡一点：知道你今天购买的每样杂货的重量，由于你准备一手一个袋子把它们都提回家，你期望平均分配重量。

为了使你相信这个问题是一个需要技巧的问题，试试划分一组10件物品，它们具有这些美元价值：

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

由于物品的总价值是$272，因此每个人将必须得到总价值为$136的物品。然后试试：

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

这里我用$38的物品替换了$42的物品，因此每人将必须得到总价值$134的物品。

这个问题称为划分问题（partition problem）。把问题稍微概括一下：与其尝试把一堆宝物分成两等分，我们不如将尝试找到总价值是给定数目的那些宝物。平均分配宝物与找到一个价值是所有宝物总价值一半的份额是一样的，另一份额是剩余的宝物，它的总价值是相同的。

如果没有一份宝物的总价值等于目标数目，函数将返回undef：

### Code Library: find-share
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])：

目前的份额 目前的总数 目标 剩余的宝物

    0    5     1  2  4  8

普通的情形没有发生，目标数目既不是负数也不是零，现存的宝物列表也不是空的。因此函数试着分配第一项，1，到份额里，然后它在剩余的项中寻找一组能满足总和为4：

1    1    4    2  4  8

函数将继续考察这种情况直到它***放弃。

然后函数分配剩余的第一项，2，到期望值是4的份额里，并递归调用以在最后的两个元素中寻找一组能满足总和为2：

1  2    3    2    4  8

这个称为“a状态”。函数将继续考察这个状态直到它断定a状态是没希望的。它尝试分配4到份额里，但是那超出了目标总数：

1 2 4 7 -2 8

所以它退回去并尝试从状态a继续，但不把4分配到份额里：

1 2 3 2 8

份额还没完成，所以函数分配下一项，8，到份额里，这明显超出了目标总数：

1 2 8 11 -6

这里得到$target < 0，所以函数失败了，尝试忽略8。这还是不行，它得到的份额距离目标数目还差2，没有剩余的项可以分配了。

目前的份额 目前的总数 目标 剩余的宝物

1  2     3    2

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

函数已经尝试了使状态a成功的所有可能，都失败了。它断定：分配了1和2到份额里行不通，然后退回去尝试忽略2：

1    1    4    4  8

现在它尝试分配4到份额里：

1  4    5    0     8

现在函数得到$target == 0，所以它返回成功。分配的宝物是1与4，相加的总和是目标5。

这个思路是忽略第一个宝物然后在剩余的宝物里寻找答案，这样自然地把问题化简到了一个更简单的情形。一个没有递归的方案也许可以通过复制递归方案的底层机制，并人为模拟函数调用栈，而得到结果。

现在解决划分问题简单了，它是对find_share()的一个调用，找到第一份，然后以一些额外的工作计算原始数组中不包含在第一份里的元素：

### Code Library: partition
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;
    }
  }

函数使用一个散列汇总每个值在第一份中出现的次数，然后在原始列表中每次查看一个宝物。如果它看到一个宝物已经在第一份里了，它就扣除；否则，它就把宝物放进宝物列表组成第2份。

  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。

第3章将介绍如何修正这个问题。