例如幂运算第二章 幂运算 - 图1,我们需要 x 进行 n-1 次自乘才能完成。
如果我们将乘法的次数作为运行时间的度量，则我们可以通过一些方法尽可能的减少乘法的次数。

1. 原理

若 n 是偶数，则第二章 幂运算 - 图2可以化成 x^(n/2) x^(n/2)=(xx)^(n/2)，若 n 是奇数，则可以化成 x^(n/2) x^(n/2) x=(xx)^(n/2) x。
这样，我们就减少了指数的值，也就是乘法的次数（隐性增加的是乘数的大小）。

2. 代码实现

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int  Pow(int x,int n){
  4.     if(n==0)
  5.         return 1;
  6.     if(n==1){
  7.         return x;
  8.     }
  9.     if(n%2==0){
  10.         return Pow(x*x,n/2);
  11.     }else if(n%2==1){
  12.         return Pow(x*x,n/2)*x;
  13.     }
  14. }
  15. int main(){
  16.     cout<<Pow(2,5)<<endl;
  17. }

代码分析

  • 首先看到第二个递归基也就是6~8行，其实这个是没有必要的，因为在第10行和第12行的两个递归调用中，第二个参数在最后都必定可以归于0，也就是第一个递归基，所以第二个递归基的去除对整个程序没有什么影响。
  • 另外，第12行的 可以改成等价的语句： return Pow(x,n-1) *x ,书上说对程序无影响，因为乘法序列是相同的。我觉得会加深一定的递归层数，但是不多。存疑。
  • 另外书中针对第十行有几个变形：
    1. return Pow(Pow(x,2),N/2);
    2. return Pow(Pow(x,N/2),2);
    3. return Pow(x,N/2)*Pow(x,N/2);
    其中第一个和第二个是错误的，因为当 N=2时，递归的过程中 N又等于2，形成了循环。
    第三个虽然不是错误的，但是使用了两次相同的递归，改变了复杂度，降低了效率。分析？待做。

    3. 应用

    应用于密码学。 实例描述见：P26 中。