数据结构与算法(6)_递归

发表于 | 分类于

如何理解递归

通常是把一个大型复杂问题层层转化为一个与原问题相似的规模较小的问题来求解.

例如,假如你在电影院中不知道自己是第几排,于是你问前一排的人他是第几排,然后加1,就是你的排数.但是前面的人也不知道,所以他也问前一排的人.就这样一排排的往前问.知道第1排,然后在一排一排的把数字传回来.基本上所有递归问题都可以用递推公式来表示.

刚刚这个例子的递推公式以及代码是:

1
2
3
4
5
//递推公式: fn(n) = f(n-1) + 1  其中 f(1) = 1;
int f(int n){
	if (n == 1) return 1;
	return f(n - 1) + 1;
}

递归需要满足三个条件

  • 一个问题的解,可以分解为几个问题的解.
  • 这个问题与分解之后的子问题,除了数据规模不同,求解思路完全一样
  • 存在递归终止条件

如何编写递归代码

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

假如现在有n个台阶,每次你可以跨1个台阶或者2个台阶,请问n个台阶有多少种走法.

实际上我们可以根据第一步的走法把所有走法分为两类.第一类是第一步走了1个台阶.第二类是第一步走了2个台阶.所以n个台阶的走法就等于先走1个台阶后n-1个台阶走法加上先走2个台阶后n-2个台阶走法.

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

然后找终止条件.当n=1时,就只有一种走法,即f(1) = 1.但这个递归条件足够吗?

此时我们用n=2,n=3来验证一下.当n=2时,f(2) = f(1) + f(0),如果递归终止条件只有f(1) = 1,此时f(0)是没有解的,所以此外还需要有f(0)=1这个终止条件,但是这样不符合逻辑.所以我们直接把f(2)=2来作为一个终止条件,然后我们继续用n=3,n=4来验证,发现是可以的.

我们把终止条件和递推公式放到一起

1
2
3
4
5
6
7
8
9
10
f(1) = 1;
f(2) = 2;
f(n) = f(n-1)+f(n-2)

//代码实现
int f(int n){
	if(n == 1) return 1;
	if(n == 2) return 2;
	return f(n-1) + f(n-2);
}

上面的过程就是: 分解问题找到递推公式->找到终止条件->验证->验证通过代码实现.

写递归代码的关键就是找到如何将大问题分解为小问题的规律,并且基于此写出递推公式,然后再推敲终止条件,最后将递推公式和终止条件翻译成代码

另外编写递归代码应该屏蔽掉递归细节,不要一层一层思考子问题与子子问题的关系,子子问题与子子子问题的关系.只要遇到递归问题,我们就把它抽象成一个递推公式,不用想一层一层的调用关系,不要视图用人脑去分解递归的每个步骤

递归代码要警惕堆栈溢出

函数调用会使用栈来保存临时变量.每调用一个函数,都会将临时变量封装为栈帧压入内存栈,等函数执行完返回时,才出栈.系统或虚拟机的栈空间一般都不大,如果递归求解的数据规模很大,调用层次很深,一直压入栈,就会有堆栈溢出的风险.

我们可以通过在代码中限制递归调用的最大深度的方式来解决这个问题

递归代码要警惕重复计算

在台阶那个例子中,如果我们把递归的过程分解一下:

//TODO img

从图中我们可以直观的看到,要计算f(5),需要先计算f(4),f(3),而计算f(4)还需要计算f(3),因此,f(3)被计算了多次,这就是重复计算.

为了避免重复计算,我们可以通过一个数据结构(例如散列表),来保存已经求解过的f(k).