递归
递归可能不算难,但是我现在也不敢说我掌握了它。所以,再学习记录一下。
递归说到底,就是自己调用自己,是一种无穷迭代思维方式,简单粗暴的罗列。
递归对程序员的修养要求极高,无穷递归、栈溢出,各种问题,安全性比较难把握。
我们最好少用递归,能™for循环、堆栈什么数据结构解决的,别用递归这破玩意,墨迹。
递归的三大要素
第一要素:明确你这个函数想要干什么
第二要素:寻找递归结束条件
第三要素:找到函数的等价关系式
几个案例
我们通过下面的一些案例,再巩固一下:
斐波那契数列
斐波那契数列的是这样一个数列:1、1、2、3、5、8、13、21、34…,即第一项 f(1) = 1,第二项 f(2) = 1…,第 n 项目为 f(n) = f(n-1) + f(n-2)。求第 n 项的值是多少
第一,定义函数,明确我们要干什么?
1 | public static int fib(int n){//fib是求第n项的值 |
第二,找到递归结束的条件
显然,当我们n为1或2的时候,结果fib(1) = fib(2) = 1,所以,递归结束条件:
1 | public static int fib(int n){ |
第三,找到等价函数关系式
题目已经给我们了: f(n) = f(n-1) + f(n-2),用代码表示即可:
1 | public static int fib(int n){ |
小青蛙跳台阶
一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法
第一,定义函数,明确我们要干什么?
1 | public static void f(int n){//f即求该青蛙跳上一个n级的台阶总共有多少种跳法 |
第二,找到递归结束的条件
找递归结束的条件,我们把n压缩到最小,即如果当n为1时,那么只有1种跳法。但是别忘了,这道题它还可以跳两级。当n为2的时候也是一个结束条件,此时有几种跳法?2种呗。所以,上代码:
1 | public static int f(int n){ |
第三,找到等价函数关系式
青蛙跳了n阶,其实它有两种方法:
- 跳1阶加f(n-1)
- 跳2阶加f(n-2)
所以等价函数关系式就是:f(n) = f(n-1)+f(n-2)
所以总的代码就是:
1 | public static int f(int n){ |
有关递归的一些优化思路
1、考虑是否重复计算
如果你使用递归的时候不进行优化,是有非常非常非常多的子问题被重复计算的。
啥是子问题? f(n-1),f(n-2)…就是 f(n) 的子问题了。
例如对于小青蛙那道题,f(n) = f(n-1) + f(n-2)。递归调用的状态图如下:
看到没有,递归计算的时候,重复计算了两次 f(5),五次 f(4)。。。。这是非常恐怖的,n 越大,重复计算的就越多,所以我们必须进行优化。
如何优化?一般我们可以把我们计算的结果保证起来,例如把 f(4) 的计算结果保证起来,当再次要计算 f(4) 的时候,我们先判断一下,之前是否计算过,如果计算过,直接把 f(4) 的结果取出来就可以了,没有计算过的话,再递归计算。
用什么保存呢?可以用数组或者 HashMap 保存,我们用数组来保存把,把 n 作为我们的数组下标,f(n) 作为值,例如 arr[n] = f(n)。f(n) 还没有计算过的时候,默认a[n]为0。
当我们要判断的时候,如果 a[n] = 0,则证明 f(n) 没有计算过,否则, f(n) 就已经计算过了,且 f(n) = a[n]。直接把值取出来就行了。代码如下:
1 | static int[] a = new int[10000];//数组,默认全部为0 |
main方法进行测试,我们让n从1开始到45,再多int就溢出了。我们顺便再看看耗时:
1 | public static void main(String[] args) { |
运行结果如下:
这样肯定缩短时间了,你信不?不然我们用原来的递归测试一下,也是从1到45,看看运行时间:
太™狠了,我点开始之后,它运行 了5s才停下来,哈哈哈。
斐波那契数列那个例子和小青蛙好像一样,我们也可以用这种方式去优化它。
2、考虑是否可以自底向上
对于递归的问题,我们一般都是从上往下递归的,直到递归到最底,再一层一层着把值返回。
不过,有时候当 n 比较大的时候,例如当 n = 10000 时,那么必须要往下递归10000层直到 n <=1 才将结果慢慢返回,如果n太大的话,可能栈空间会不够用。
对于这种情况,其实我们是可以考虑自底向上的做法的。例如我知道
f(1) = 1;
f(2) = 2;
那么我们就可以推出 f(3) = f(2) + f(1) = 3。从而可以推出f(4),f(5)等直到f(n)。因此,我们可以考虑使用自底向上的方法来取代递归,代码如下:
1 | //自底向上 |
这个我们好像也可以用一个数组去避免重复计算,提高时间,但是感觉效果不是很明显。可能这个没有去用递归吧。可以看出,递归还是挺吓人的,太™磨叽了。
八皇后问题
八皇后问题(英文:Eight queens),是由国际西洋棋棋手马克斯·贝瑟尔于1848年提出的问题,是回溯算法的典型案例。
问题表述为:在8×8格的国际象棋上摆放8个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解,后来有人用图论的方法解出92种结果。如果经过±90度、±180度旋转,和对角线对称变换的摆法看成一类,共有42类。计算机发明后,有多种计算机语言可以编程解决此问题。
- 第一个皇后先放第一行第一列
- 第二个皇后放在第二行第一列、然后判断是否OK,如果不OK,继续放在第二列、第三列、依次把所有列都放完,找到一个合适
- 继续第三个皇后,还是第一列、第二列……直到第8个皇后也能放在一个不冲突的位置,算是找到了一个正确解
- 当得到一个正确解时,在栈回退到上一个栈时,就会开始回溯,即将第一个皇后,放到第一列的所有正确解,全部得到
- 然后回头继续第一个皇后放第二列,后面继续循环执行1,2,3,4的步骤
其实主要函数就两个,一个是放置第n个皇后的 check
方法,另外一个是判断当前我们放置的第n个皇后和前面的已经摆好的皇后是否冲突的 judge
方法。
我们先要写check方法,在这一行使用一个for循环测试每一列的情况,循环内进行judge判断,如果不冲突则递归进行下一个check方法,否则进行下一个for的遍历。
总的代码如下:
1 | //八皇后问题 |