2.2 改进该算法
从加法的执行次数上面来看，multiply1函数确实做得不错，但它毕竟执行了?log n?次递归调用。由于函数调用的开销很大，因此我们想把程序中的递归调用去掉，以避免此类开销。
在对函数进行转化时，我们所秉持的一项理念是：通用的工作实现起来经常比具体的工作还要简单（It is often easier to do more work rather than less.）。就本例来说，我们要按照下面这种通用的方式进行计算：
r + na
其中的r是一个会在运算过程中持续更新的值，用来累计当前已经算好的那部分na乘积。换句话说，我们所要执行的操作，并不是直接求出两数的乘积，而是在进行乘积累加（multiply-accumulate）。该理念不仅适用于编程，而且还可以用在硬件设计与数学中。对于数学来说，证明一条通用的结论，经常比证明一条具体的结论还要容易。
下面就是我们所要使用的乘积累加函数：
该函数遵循这样一个不变式（invariant）：r + na = r0 + n0a0，其中的r0、n0与a0是这些变量的初始取值。
现在，我们可以继续对递归进行优化。由于函数中包含的那两个递归调用语句，只有第一个参数有所区别，因此我们可以对r变量进行修改，令其把n为偶数与n为奇数时的两种情况全都用同一个通式表达出来：
于是，这个函数就变成了尾递归（tail-recursive），也就是说，它只会在返回值里面进行递归。稍后我们就会利用该特征对其做进一步的变换。
现在，我们先观察该函数的另外两项特征：
n的值很少会取到1。
如果n是偶数，那就没有必要再判断它是不是1了。
基于这两项特征，我们可以先判断n是不是奇数，如果确实是奇数，那么再判断它是不是1。这样可以把和1进行比较的次数缩减为原来的一半：
有些程序员或许认为：编译器的优化机制能够自动帮我们完成上述变换。然而实际上却很少会如此，因为它们不太可能把一种算法变换成另一种算法。
这个函数现在看起来已经相当好了，但离我们的要求还有一段距离，因为我们想要达成的效果是彻底把递归去掉，从而避免此类开销。如果这个函数能变成严格的尾递归（strictly tail-recursive）函数，那我们的想法实现起来就很容易了。
定义2.1 严格的尾递归过程是指那种使用与形式参数完全对应的实际参数，来进行所有递归调用的尾递归过程。
这一次我们还是可以通过修改变量的值来实现这种变换，也就是说，可以先把合适的值赋给相应的变量，然后再使用这些变量进行尾递归：
至此，我们就可以用while(true)结构来代替尾递归了。这样做能够将该函数轻松地转换为迭代式的（iterative）程序：
把乘法累加函数优化好之后，我们可以编写新版的乘法函数，令其在乘法累加函数的帮助下进行计算：
请注意，在上述函数中我们把初始的累加结果直接设置成a，令其可以少调用一次mult_acc4函数。
现在的这个算法已经相当好了，只是当n等于2的幂时还有一些问题。由于我们首先会对n减1，因此如果n是2的幂，那么减去1之后的那个数，其二进制表示形式中的每一个二进制位就都会是1，而这对于mult_acc4函数来说是最坏的情况。由此可见，我们在调用该函数之前，若发现n为偶数，则应反复将其减半（并反复对a翻倍）直至n变为奇数，然后再去调用：
做完上述修改之后，大家可以发现另外一个问题：由于我们在调用mult_acc4函数时，传给参数n的那个n-1值总是偶数，因此会导致该函数第一次对odd(n)所进行判断总是多余的。为此，我们应该先将n-1这个值减半，并对a这个值翻倍，然后再去调用mult_acc4函数，于是就得到了最终的版本：
重写代码
在对乘法算法进行反复变换的过程中，大家可以看到：重写代码其实是一项很重要的工作。没有谁能够第一次就把代码写好，我们都必须在反复的修改中，才能找到最为高效或最为通用的实现方式。因此，程序员不应该抱有那种一步到位的想法。
改进算法的时候，你或许在想：“就算多做一次操作，也不会对算法有太大影响”。然而你所写的这些代码，很有可能要在接下来的许多年中反复地使用。（实际上，你随手修改的那些地方往往就是代码中用得最久的那些地方。）此外，当前这个开销不太大的操作将来可能会替换成另外一种开销相当大的操作，因此，即便只能省下一次操作也是值得的。
努力提升算法的效率还会带来一个好处，就是可以促使你更加深入地思考问题。如果能够把问题理解得更为透彻，那么实现出来的代码也会更加高效。这是个良性的循环。
