[算法提高] 递归快速幂

逃离我推掉我的手 2022-03-06 03:20 209阅读 0赞

理解递归的想法不难，关键是如何 快速 写出 正确 高效 的递归。

函数递归调用的基本形式：

Type MyFunction(){
        ...
        MyFunction();
    }

下面以递归实现 快速幂 ，说明一下写递归的一些注意点，这些要点是不是必要的我不知道，我想这需要严格的证明。

一般求幂的方法是调用<cmath>中的pow()函数，例如求![X^\{n\}][X_n]我们可以用pow(x, n)函数来得到。(调轮子)

如果要造轮子的话，一种想法是用for循环：

#include <iostream>
    #include <cmath>
    using namespace std;
    
    int forPower(int x, int n){
    	int y = 1;
    	for(int i = 0; i < n; i++){
    		y = y * x;
    	}
    	return y;
    }
    
    int main() {
    	cout << "pow(2,6)=" << pow(2,6) << endl;
    	cout << "forPower(2,6)=" << forPower(2,6) << endl;
    	return 0;
    }

当然，forPower(2,6) = 2 \* 2 \* 2 \* 2 \* 2 \* 2，执行了五次乘法。即forPower(x, n)的时间复杂度大约是O(n)。可不可以更快呢？

比如对于![2^\{8\}][2_8]，2 \* 2 \* 2 \* 2 \* 2 \* 2 \* 2 \* 2也可以写作是\[(2 \* 2) \* (2 \* 2)\] \* \[(2 \* 2) \* (2 \* 2)\]， 即y = 2 \* 2; y = y \* y; y = y \* y, 7次乘法变成了3次。这样一层层的分解计算就可以用递归写出来：

#include <iostream>
    #include <cmath>
    using namespace std;
    
    long long Power(int x, int n) {
    	long long y;
    	if (n == 1) { //递归的边界 
    		return x;
    	}else{
    		y = Power(x, n/2); //递归：函数调用自身
    		if(n % 2 == 0){
    			return y * y; 
    		}else{
    			return y * y * x;
    		}
    	}
    }
    
    int main() {
    	cout << "pow(2,4) = " << pow(2,4) << endl; 
    	cout << "Power(2,4) = " << Power(2,4) << endl;
    	cout << "pow(2,5) = " << pow(2,5) << endl;
    	cout << "Power(2,5) = " << Power(2,5) << endl;
    	return 0;
    }

对于Power(2,7)，图示描述其运算流程：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N3b3JkdHJhdmVsbGVy_size_16_color_FFFFFF_t_70][]

因此，个人的看法是，要写好递归，三个东西很重要：

1.**向内层的递归** y = Power(x, n/2);

2.**向外层的返回** return n % 2 == 0 ? y \* y : y \* y \* x;

3.**边界层的返回** return x;

其实很像数学归纳法。

个人浅见，欢迎批评指正！

[X_n]: https://private.codecogs.com/gif.latex?X%5E%7Bn%7D
[2_8]: https://private.codecogs.com/gif.latex?2%5E%7B8%7D
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N3b3JkdHJhdmVsbGVy_size_16_color_FFFFFF_t_70]: /images/20220306/c956d6fdcc0a48aba8d8dcf621125901.png