通过一道面试题目，讲一讲递归算法的时间复杂度！

（给算法爱好者加星标，修炼编程内功）来源：代码随想录相信很多同学对递归算法的时间复杂度都很模糊，那么这篇来给大家通透的讲一讲。「同一道题目，同样使用递归算法，有的同学会写出了O(n)的代码，有的同学就写出了O(logn)的代码」。这是为什么呢？如果对递归的时间复杂度理解的不够深入的话，就会这样！那么我通过一道简单的面试题，模拟面试的场景，来带大家逐步分析递归算法的时间复杂度，最后找出最优解，来看看同样是递归，怎么就写成了O(n)的代码。面试题：求x的n次方想一下这么简单的一道题目，代码应该如何写呢。最直观的方式应该就是，一个for循环求出结果，代码如下：int function1(int x, int n) {    int result = 1;  // 注意 任何数的0次 ………………………………