之前的文章咱们已经聊过了 「 数组和链表 」 、 「 堆栈 」 和 「 队列 」 ,今天咱们来看看「 递归 」,当然「 递归 」并不是一种数据结构,它是很多算法都使用的一种编程方法。它太普遍了,并且用它来解决问题非常的优雅,但它又不是那么容易弄懂,所以我特意用一篇文章来介绍它。 一、「 递归 」是什么? 递归 就是指函数直接或间接的调用自己,递归是基于栈来实现的。递归的经典例子就是 斐波拉契数列(Fibonacci)。一般如果能用递归来实现的程序,那它也能用循环来实现。用递归来实现的话,代码看起来更清晰一些,但递归的性能并不占优势,时间复杂度甚至也会更大一些。 上图为 斐波拉契数列 图例。 要实现递归,必须满足2个条件:
下面还是以 斐波拉契数列(Fibonacci)为例,我们来理解一下递归: 斐波拉契数列就是由数字 1,1,2,3,5,8,13…… 组成的这么一组序列,特点是每位数字都是前面相邻两项之和。如果我们希望得出第N位的数字是多少?
int Fb(int n){ if(n<=1) return n==0?0:1; return Fb(n-1)+Fb(n-2); //这里就是函数自己调用自己}
二、「 递归 」的算法实践? 我们看看经常涉及到 递归 的 算法题(来源leetcode): 算法题:实现 pow(x, n) ,即计算 x 的 n 次幂函数。说明: -100.0 < x < 100.0 n 是 32 位有符号整数,其数值范围是 [−2^31, 2^31 − 1]示例:输入: 2.00000, 10输出: 1024.00000解题思路:方法一:暴力解法,直接写一个循环让n个x相乘嘛,当然了这种方式就没啥技术含量了,时间复杂度O(1),代码省略了。方法二:基于递归原理,很容易就找出递推公式 f(n)=x*f(n-1),再找出递归停止条件即n==0或1的情况就可以了。不过稍微需要注意的是,因为n的取值可以是负数,所以当n小于0的时候,就要取倒数计算。代码如下:class Solution { public double myPow(double x, int n) { if(n==0) return 1; if(n==1) return x; if(n<0) return 1/(x*myPow(x,Math.abs(n)-1)); return x*myPow(x,n-1); }}这个方法其实也有问题,当n的数值过大时,会堆栈溢出的,看来也是不最佳解,继续往下看。方法三:利用分治的思路,将n个x先分成左右两组,分别求每一组的值,然后再将两组的值相乘就是总值了。即 x的n次方 等于 x的n/2次方 乘以 x的n/2次方。以此类推,左右两组其实还可以分别各自继续往下分组,就是一个递推思想了。但是这里需要考虑一下当n是奇数的情况,做一个特殊处理即可,代码如下:class Solution { public double myPow(double x, int n) { //如果n是负数,则改为正数,但把x取倒数 if(n<0) { n = -n; x = 1/x; } return pow(x,n); } private double pow(double x, int n) { if(n==0) return 1; if(n==1) return x; double half = pow(x,n/2); //偶数个 if(n%2==0) { return half*half; } //奇数个 return half*half*x; }}这种方法的时间复杂度就是O(logN)了。 以上,就是对数据结构中「 递归 」的一些思考。 码字不易啊,喜欢的话不妨转发朋友,或点击文章右下角的“在看”吧。 |
|
来自: taotao_2016 > 《it》