把知识记在小本本上

将零散的知识点放在一个集中的地方,不断递归重构,形成一套为己所用的知识系统。

博客首页 | 小本本首页

如何理解递归

例:领导分配给你一个任务量为n的任务,你做了一部分,然后把剩下的n-1分配给别人,别人又做了一部分,把剩下的n-2分配给了另一个人,直到最后一个人,做了一部分,然后把任务完成返回给他上一个人。

这个任务下发的过程叫,任务返回的过程叫

基本上,所有的递归问题都可以用递推公式来表示,上面这个例子,递推公式表示为:f(n)=f(n-1)+1 其中,f(1)=1

上述递归问题的代码表示如下:

1
2
3
4
5
6
int f(int n) 
{
if (n == 1)
return 1;
return f(n-1) + 1;
}

递归需要满足的条件

1)一个问题可以分解为几个字问题的解

2)这个问题与分解之后的字问题,除了数据规模不同,求解思路完全一样

3)存在递归终止条件

举个栗子:

树的定义是一种递归形式的定义,对于树的前序遍历,有:

1
2
3
4
5
6
7
8
9
void PreOrder(struct TreeNode *root)
{
if (root == NULL) // 递归的终止条件
return;

/* 处理root */
PreOrder(root->left); // 递推,左子树
PreOrder(root->right); // 递推,右子树
}

在一些树的相关题目中,以这种递推的思想来处理问题还是比较方便的。

递归代码如何实现

写递归代码最关键的是写出递推公式,找到终止条件。

青蛙跳台阶问题:

假设有n个台阶,每次青蛙可以跳1个台阶或者2个台阶,请问走完这n个台阶有多少种走法?

例如:有7个台阶,可以2,2,2,1上去,也可以1,2,1,1,2这样上去,总之走法很多,如何编程实现呢?

分析:根据第一步走法把所有走法分为2类,第一类:第一步走了1个台阶,第二类:第一步走了2个台阶。所以n个台阶的走法 =(先走1个台阶后,n-1个台阶的走法)+(先走2个台阶后,n-2个台阶的走法)

用递推公式表示就是:

f(n) = f(n-1)+f(n-2)

递推的终止条件:

当有一个台阶时,不需要再继续递归,只有一中走法。

当有两个台阶时,可以每次走1个台阶,走两次,也可以一次两个。

当有三个台阶时,就分解为有一个台阶和两个台阶的问题了。

所以有:

1
2
3
4
5
6
7
8
int f(int n) 
{
if (n == 1)
return 1;
if (n == 2)
return 2;
return f(n-1) + f(n-2);
}

人脑几乎没办法把整个递归的过程一步一步想清楚,所以很多时候,我们只需要把它抽象成一个递推公式,不用想一层一层的调用关系,这些交给计算机来做就好了。

要注意栈溢出!

如果递归求解的数据规模很大,调用层次很深,就会有栈溢出的发生。

我的一次栈溢出的经历:在练习用递归模拟strlen函数功能时,如下代码:

1
2
3
4
5
6
int my_strlen(char *str)
{
if(*str == '\0')
return 0;
return 1 + my_strlen(str++);
}

这里传进去的始终是str,所以没有终止的一直压栈,导致栈溢出。

解决栈溢出的方法:

1)限制递归深度

这种做法并不能完全解决问题,因为最大允许的递归深度和当前线程剩余的栈空间大小有关,事先无法计算,如果实时计算,代码过于复杂,影响可读性。所以对于最大深度比较小的情况,如10、50,就可以用这种方法,否则这种方法并不是很实用。

2)在堆区模拟系统的工作栈

如果需要可以采用这种方法。

警惕重复计算

以青蛙跳台阶的问题为例:

图片引用自极客时间

从图中可以看到:想要计算f(5),需要先计算f(4)和f(3),而f(4)还需要计算f(3),因此,f(3)被重复计算了多次,这就是重复计算问题!

还有个例子:递归方法求第n个斐波那契数,也会有同一n重复计算多次的现象。

当计算第50个斐波那契数时,f(3)被计算了上亿次,这个计算花了10分钟左右!

重复计算的解决方法:

为了避免这种重复计算带来的负面开销,可以通过引入散列表来保存已经求过的f(k)。当递归调用到f(k)时,先看下是否求解过了,如果是直接从散列表中取这个值,就不需要再次计算了。

递归代码改写为非递归代码

递归有利有弊,递归的问题不仅仅就上面说的重复计算和栈溢出,递归的空间复杂度有时也比较高。

如果用递归方法求第n个斐波那契数,时间开销比较大,还是用循环比较好。

对于上文中两个例子改写如下:

1
2
3
4
5
6
7
8
9
10
/* 领导分配工作 */
int f(int n)
{
int ret = 1;
for (int i = 2; i <= n; ++i)
{
ret = ret + 1;
}
return ret;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/* 青蛙跳台阶问题 */
int f(int n)
{
if (n == 1)
return 1;
if (n == 2)
return 2;

int ret = 0;
int pre = 2;
int prepre = 1;
for (int i = 3; i <= n; ++i)
{
ret = pre + prepre;
prepre = pre;
pre = ret;
}
return ret;
}

这种思路其实是将递归改成了“手动”递归,本质没有变,增加了实现难度。

经典递归问题

  • 在n个球中,任意取m个(不放回),求有多少种取法
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
#include <stdio.h>

int f(int n, int m)
{
if (n<m) // 3个球取4个出来 显然是0种取法
{
return 0;
}
if (m==0) // 3个球取0个出来 有1种取法
{
return 1;
}
if (n==m) // 3个球取3个出来 有1种取法
{
return 1;
}
return f(n-1, m-1) + f(n-1, m);
}

int main(int argc, const char * argv[])
{
int k = f(5, 3);
printf("%d\n", k);

return 0;
}
  • 求n个元素的全排列
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
// abc acb bac bca cab cba
#include <stdio.h>

void f(char data[], int length, int cur)
{
if(cur==length)
printf("%s\n", data);
for(int i=cur; i<length; i++)
{
{ // 试探
char tmp = data[i];
data[i] = data[cur];
data[cur] = tmp;
}

f(data, length, cur+1);

{ // 回溯
char tmp = data[i];
data[i] = data[cur];
data[cur] = tmp;
}
}
}

int main()
{
char data[] = "abcd";
int length = sizeof(data)/sizeof(data[0]) - 1;
//printf("%d\n",length);
f(data, length, 0);
return 0;
}
  • 两个串的最大公共子序列的长度
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
// 可解!

#include <stdio.h>
#include <string.h>

int MAX(int a, int b)
{
return a>b?a:b;
}

int f(char *s1, char *s2)
{
if (strlen(s1)*strlen(s2) == 0)
{
return 0;
}
if (s1[0] == s2[0])
{
return f(s1+1, s2+1) + 1;
}
else
{
return MAX(f(s1+1, s2), f(s1, s2+1));
}
}

int main(int argc, const char * argv[])
{
char *s1 = "abc";
char *s2 = "xbacd";

int ret = f(s1, s2);
printf("%d\n", ret);

return 0;
}
  • 字符串反转
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
// 反转串
// 例如:abc -> cba

#include <stdio.h>
#include <string.h>

void ReverseString(char *p)
{
int length = strlen(p);
if(length <= 1)
{
return;
}
else
{
char tmp = p[0];
p[0] = p[length-1];
p[length-1] = '\0';
ReverseString(p+1);
p[length-1] = tmp;
}
}

int main()
{
char p[] = "abcd";
ReverseString(p);
printf("%s\n", p);
return 0;
}
  • 组合问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 组合问题
// 3个A 2个B可以组成多少 种 排列
// 如:AAABB AABBA等

#include <stdio.h>

// m个A n个B
int f(int m, int n)
{
if(m == 0 || n == 0)
{
return 1;
}
// 假设首位置为A,则剩下m-1个A和n个B的组合问题 + 首位置为B...
return f(m-1, n) + f(m, n-1);
}

int main()
{
printf("%d\n", f(3, 1));
return 0;
}
  • 杨辉三角
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
// 杨辉三角
// 计算第m层第n个元素

/*
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
*/

#include <stdio.h>

int f(int m, int n)
{
if(n == 0)
{
return 1;
}
if(m == n)
{
return 1;
}
return f(m-1, n) + f(m-1, n-1);
}

int main()
{
int leval = 5; // 第5行 0-5共6个元素
for(int i=0; i<=leval; i++)
{
printf("%d ", f(leval, i));
}
printf("\n");
return 0;
}
  • 整数划分问题
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
// 整数划分问题
// n = 6
/*
6
5+1
4+2,4+1+1
3+3,3+2+1,3+1+1+1
2+2+2,2+2+1+1,2+1+1+1+1
1+1+1+1+1+1
*/

#include <stdio.h>

#define MAXSIZE 1024

// arr->缓冲,cur->当前位置
void f(int n, int arr[], int cur)
{
if(n<=0)
{
for(int i=0; i<cur; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
return;
}

for(int i=n; i>0; i--)
{
if(cur>0 && i>arr[cur-1])
{
continue;
}
arr[cur] = i;
f(n-i, arr, cur+1);
}
}

int main()
{
int arr[MAXSIZE] = {0};
f(6, arr, 0);
return 0;
}

参考文章:《数据结构与算法之美》