本篇通过一道简单的面试题，逐步分析递归算法的时间复杂度，最后找到最优解
同一道题目，同样使用递归算法，既可以写出时间复杂度为O(n)的代码,也可以写出时间复杂度为O(logn)的代码。
why?
这是因为对递归算法的时间复杂度理解不够深入。
下面通过一道面试题，来逐步分析递归算法的时间复杂度，最后找出最优解
面试题：求x的n次方
-
最直观的方式应该就是，一个for循环求出结果，代码如下：
int function1(int x, int n) { int result = 1; // 注意 任何数的0次方等于1 for (int i = 0; i < n; i++) { result = result * x; } return result; }时间复杂度为O(n)，此时面试官会说，有没有效率更好的算法呢？
面试者如果此时没有思路，建议不要说不知道。可以和面试官探讨一下，询问：“可不可以给点提示”。面试官提示说：“考虑一下递归算法”.
-
此时面试者就写出了如下代码，使用递归算法解决了这个问题：
int function2(int x, int n) { if (n == 0) { return 1; // return 1 同样是因为0次方是等于1的 } return function2(x, n - 1) * x; }面试官问：“那么这个代码的时间复杂度是多少？”。
一些同学可能一看到递归就想到了O(logn)，其实并不是这样，递归算法的时间复杂度本质上是要看: 递归的次数 * 每次递归中的操作次数。
那么这里递归了几次呢？
每次递归n都做一次减1的操作，那么就是递归了n次，递归n次时间复杂度是O(n)，每次执行一个乘法操作，而乘法操作的时间复杂度是一个常数项O(1)，所以这段代码的时间复杂度是O(n) (即：O(n*1) = O(n) )
这个时间复杂度可能没有达到面试官的预期。
-
于是面试者又些出了如下递归算法的代码：
int function3(int x, int n) { if (n == 0) return 1; if (n == 1) return x; if (n % 2 == 1) { return function3(x, n / 2) * function3(x, n / 2)*x; } return function3(x, n / 2) * function3(x, n / 2); }面试官看到后微微一笑，问：“这段代码的时间复杂度又是多少呢？” 此时面试者陷入了沉思……
首先看递归了多少次呢，可以把递归抽象出一棵满二叉树。刚刚同学写的这个算法，可以用一棵满二叉树来表示（为了方便表示，选择n为偶数16），如图：
当前这棵二叉树就是求x的n次方，n为16的情况，n为16的时候，进行了多少次乘法运算呢？
这棵树上每一个节点就代表着一次递归并进行了一次相乘操作，所以进行了多少次递归的话，就是看这棵树上有多少个节点。
熟悉二叉树话应该知道如何求满二叉树节点数量，这棵满二叉树的节点数量就是\(2^3 + 2^2 + 2^1 + 2^0 = 15\)，可以发现：这其实是等比数列的求和公式，这个结论在二叉树相关的面试题里也经常出现。
这么如果是求x的n次方，这个递归树有多少个节点呢，如下图所示：(m为深度，从0开始)
时间复杂度忽略掉常数项-1之后，这个递归算法的时间复杂度依然是O(n)。对，你没看错，依然是O(n)的时间复杂度！
此时面试官就会说：“这个递归的算法依然还是O(n)啊”， 很明显没有达到面试官的预期。
-
那么O(logn)的递归算法应该怎么写呢？
想一想刚刚给出的那份递归算法的代码，是不是有哪里比较冗余呢，其实有重复计算的部分。
于是又写出如下递归算法的代码：
int function4(int x, int n) { if (n == 0) return 1; if (n == 1) return x; int t = function4(x, n / 2);// 这里相对于function3，是把这个递归操作抽取出来 if (n % 2 == 1) { return t * t * x; } return t * t; }现在这段代码的时间复杂度是多少呢？
这里仅有一个递归调用，而且每次递归操作的数据规模都除以2，所以这里一共调用了\(log_2 n\)次，每次递归操作都是一次乘法操作，这也是一个常数项的操作，所以这个递归算法的时间复杂度才是真正的O(logn)。
-
恭喜你，通过了考验~~