我想很多学生递归算法在时间上的复杂性很模糊，这次让我们通透地谈谈吧。
“同一个主题，一个同学用同样的递归算法写O(N )的代码，一个同学写o ) Logn )的代码”。
为什么会这样呢？
如果不充分理解递归的时间复杂性，就会变成这样！
那么，我们来模拟简单的面试问题、面试场景，逐步分析递归算法的时间复杂度，最后找出最优解，看看即使是相同的递归，o(n )的代码是怎么写的。
问题：求x的n次方
想想这么简单的主题。 代码应该怎么写呢？ 最直观的方法是用for循环求结果。 代码如下所示。
信息1 (英寸，英寸)
int结果=1； //注意任何数的0次方都将是1
for (英制=0； in； I ) {2}
结果=结果* x；
}
返回结果；
}
的复杂度为o(n )。 这时面试官会说，有没有效率更高的算法呢？
“这个时候没有想法的话，”我不能。 不要说“我不知道”之类的话。
请与面试官商量，问问“可以给我提示吗”。 面试官提示：“想想递归算法”。
那么，可以写如下递归算法，用递归解决了这个问题。
信息2 (intx，intn ) {
if(n==0) {
返回1； //return1也同样是因为0次方是1
}
返回函数2 (x，n-1 ) *x；
}
面试官“那么，这个代码的时间复杂度是多少？ ”。
也许有些同学看到递归就觉得o(logn )，但实际上不是。 递归算法的时间复杂性本质上要看：“递归的次数*每次递归的操作次数”。
现在，让我们来看看代码。 这里递归了几次？
每n-1次，n次递归的时间复杂度为o(n )，每次进行乘法操作时，乘法操作的时间复杂度为常数项o )1)，因此该代码的时间复杂度为n*1=o ) n )。
这个时间的复杂性没有达到面试官的期望。 于是，我写了以下递归算法的代码：
信息3 (intx，intn ) {
if(n==0) {
返回1；
}
if(n%2==1) {
返回函数3 (x，n/2 )函数3 ) x，n/2 ) x；
}
返回函数3 (x，n/2 )函数3 ) 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; } int t = function4(x, n / 2);// 这里相对于function3，是把这个递归操作抽取出来 if (n % 2 == 1) { return t * t * x; } return t * t; }再来看一下现在这份代码时间复杂度是多少呢？
依然还是看他递归了多少次，可以看到这里仅仅有一个递归调用，且每次都是n/2 ，所以这里我们一共调用了log以2为底n的对数次。
「每次递归了做都是一次乘法操作，这也是一个常数项的操作，那么这个递归算法的时间复杂度才是真正的O(logn)」。
此时大家最后写出了这样的代码并且将时间复杂度分析的非常清晰，相信面试官是比较满意的。
总结
对于递归的时间复杂度，毕竟初学者有时候会迷糊，刷过很多题的老手依然迷糊。
「本篇我用一道非常简单的面试题目：求x的n次方，来逐步分析递归算法的时间复杂度，注意不要一看到递归就想到了O(logn)！」
同样使用递归，有的同学可以写出O(logn)的代码，有的同学还可以写出O(n)的代码。
对于function3 这样的递归实现，很容易让人感觉这是O(logn)的时间复杂度，其实这是O(n)的算法！
int function3(int x, int n) { if (n == 0) { return 1; } if (n % 2 == 1) { return function3(x, n / 2) * function3(x, n / 2)*x; } return function3(x, n / 2) * function3(x, n / 2); }可以看出这道题目非常简单，但是又很考究算法的功底，特别是对递归的理解，这也是我面试别人的时候用过的一道题，所以整个情景我才写的如此逼真，哈哈。
大厂面试的时候最喜欢用“简单题”来考察候选人的算法功底，注意这里的“简单题”可并不一定真的简单哦！
如果认真读完本篇，相信大家对递归算法的有一个新的认识的，同一道题目，同样是递归，效率可是不一样的！
就酱，「代码随想录」是技术公众号里的一抹清流，值得介绍给身边的朋友同学们！
打算从头开始打卡的录友，可以在「算法汇总」这里找到历史文章，很多录友都在从头打卡，你并不孤单！
-------end-------
我将算法学习相关的资料已经整理到了Github ：https://github.com/youngyangyang04/leetcode-master，里面还有leetcode刷题攻略、各个类型经典题目刷题顺序、思维导图看一看一定会有所收获，如果给你有帮助给一个star支持一下吧！
我是程序员Carl，个人主页：https://github.com/youngyangyang04
更多精彩点击下方了解更多！