记录生活中的点点滴滴

0%

递归

递归

递归可能不算难,但是我现在也不敢说我掌握了它。所以,再学习记录一下。

递归说到底,就是自己调用自己,是一种无穷迭代思维方式,简单粗暴的罗列。

递归对程序员的修养要求极高,无穷递归、栈溢出,各种问题,安全性比较难把握。

我们最好少用递归,能™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
2
3
public static int fib(int n){//fib是求第n项的值

}

第二,找到递归结束的条件

显然,当我们n为1或2的时候,结果fib(1) = fib(2) = 1,所以,递归结束条件:

1
2
3
4
public static int fib(int n){
if(n<=2)
return 1;
}

第三,找到等价函数关系式

题目已经给我们了: f(n) = f(n-1) + f(n-2),用代码表示即可:

1
2
3
4
5
6
7
public static int fib(int n){
//递归结束的条件
if(n<=2)
return 1;
//等价函数关系式
return fib(n-1)+fib(n-2);
}
小青蛙跳台阶

一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法

第一,定义函数,明确我们要干什么?

1
2
3
public static void f(int n){//f即求该青蛙跳上一个n级的台阶总共有多少种跳法

}

第二,找到递归结束的条件

找递归结束的条件,我们把n压缩到最小,即如果当n为1时,那么只有1种跳法。但是别忘了,这道题它还可以跳两级。当n为2的时候也是一个结束条件,此时有几种跳法?2种呗。所以,上代码:

1
2
3
4
5
6
public static int f(int n){
if(n==1)//1个台阶的时候,只有1种方法
return 1;
if(n==2)
return 2;//2个台阶的时候,有2种方法
}

第三,找到等价函数关系式

青蛙跳了n阶,其实它有两种方法:

  • 跳1阶加f(n-1)
  • 跳2阶加f(n-2)

所以等价函数关系式就是:f(n) = f(n-1)+f(n-2)

所以总的代码就是:

1
2
3
4
5
6
7
public static int f(int n){
if(n==1)//1个台阶的时候,只有1种方法
return 1;
if(n==2)
return 2;//2个台阶的时候,有2种方法
return f(n-1)+f(n-2);//有两种选择:1.跳1阶加f(n-1)2.跳2阶加f(n-2)
}

有关递归的一些优化思路

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
2
3
4
5
6
7
8
9
10
static int[] a = new int[10000];//数组,默认全部为0
//小青蛙案例,V2.0,用数组保存
public static int f(int n){
if(n<=2)
return n;
if(a[n]!=0)
return a[n];
a[n] = f(n-1)+f(n-2);
return a[n];
}

main方法进行测试,我们让n从1开始到45,再多int就溢出了。我们顺便再看看耗时:

1
2
3
4
5
6
7
8
public static void main(String[] args) {
long start = System.currentTimeMillis();
for (int i = 1; i < 46; i++) {
System.out.println(f(i));
}
long end = System.currentTimeMillis();
System.out.println("耗时:"+(end-start));
}

运行结果如下:

这样肯定缩短时间了,你信不?不然我们用原来的递归测试一下,也是从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
2
3
4
5
6
7
8
9
10
11
12
13
14
//自底向上
public static int f(int n){
if(n<=2)
return 1;
int f1 = 1;
int f2 = 1;
int sum = 0;
for (int i = 3; i <= n; i++) {
sum = f1+f2;
f1 = f2;
f2 = sum;
}
return sum;
}

这个我们好像也可以用一个数组去避免重复计算,提高时间,但是感觉效果不是很明显。可能这个没有去用递归吧。可以看出,递归还是挺吓人的,太™磨叽了。

八皇后问题

八皇后问题(英文:Eight queens),是由国际西洋棋棋手马克斯·贝瑟尔于1848年提出的问题,是回溯算法的典型案例。

问题表述为:在8×8格的国际象棋上摆放8个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解,后来有人用图论的方法解出92种结果。如果经过±90度、±180度旋转,和对角线对称变换的摆法看成一类,共有42类。计算机发明后,有多种计算机语言可以编程解决此问题。

  1. 第一个皇后先放第一行第一列
  2. 第二个皇后放在第二行第一列、然后判断是否OK,如果不OK,继续放在第二列、第三列、依次把所有列都放完,找到一个合适
  3. 继续第三个皇后,还是第一列、第二列……直到第8个皇后也能放在一个不冲突的位置,算是找到了一个正确解
  4. 当得到一个正确解时,在栈回退到上一个栈时,就会开始回溯,即将第一个皇后,放到第一列的所有正确解,全部得到
  5. 然后回头继续第一个皇后放第二列,后面继续循环执行1,2,3,4的步骤

其实主要函数就两个,一个是放置第n个皇后的 check 方法,另外一个是判断当前我们放置的第n个皇后和前面的已经摆好的皇后是否冲突的 judge 方法。

我们先要写check方法,在这一行使用一个for循环测试每一列的情况,循环内进行judge判断,如果不冲突则递归进行下一个check方法,否则进行下一个for的遍历。

总的代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
//八皇后问题
public class EightQueue {
//定义一共多少个皇后
int max = 8;
//定义数组,保存皇后位置放置的结果,比如arr={0,4,7,5,2,6,1,3}
int[] arr = new int[max];
//定义总共的种类数
static int count = 0;
public static void main(String[] args) {
EightQueue eightQueue = new EightQueue();
eightQueue.check(0);
System.out.println("方案种类数:"+count);
}
//编写一个方法,放置第n个皇后
public void check(int n){
if(n==8){
print();
return;
}
//依次放入皇后,并判断是否冲突
for (int i = 0; i < max; i++) {
//先把当前这个皇后n,放到该行的第1列
arr[n] = i;
//判断是否冲突
if(!judge(n)){//不冲突
check(n+1);
}
//如果冲突就继续下一个循环
}
}
//查看当我们放置第n个皇后,就去检测该皇后是否和前面已经摆放的皇后冲突
public boolean judge(int n){
/**
* arr[i] == arr[n]表示在同一列
* n-i == Math.abs(arr[n]-arr[i])表示在同一斜线
*/
for (int i = 0; i < n; i++) {
if(arr[i]==arr[n] || Math.abs(n-i)==Math.abs(arr[n]-arr[i]))
return true;
}
return false;
}
//输出方法
private void print() {
count++;
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]+" ");
}
System.out.println();
}
}