「递归」这个词语我们经常在很多地方看到,在很多地方用到。但是初学递归时可能会有些难以理解。本文从一些易懂、常见的例子中介绍一下「递归」。
当我们看到「递归」时,不要把它看成一个词语,而是分开看成两个字「递」和「归」。
举一个生活中的例子
有几个人在柜台前排队,现在甲想知道他排到第几个了,所以他会问排在他前面的乙是第几个,然后加1即可。
但是乙也不知道他是第几个,所以乙会问排在他前面的丙是第几个,然后加1即可。
这样一直向前问……
直到问到戊了,此时戊就站在柜台前,所以戊知道他是第1个,然后回答丁。
丁知道他前面的人是第1个,那么丁就知道他是第2个了,然后回答丙。
这样一直向后回答……
甲知道了他前面的人是第4个,那么甲就知道他是第5个了。
那么乙是第几个人呢?这就不是甲操心的事了,因为甲也不知道乙是第几个人。不幸的是,乙也不知道他自己是第几个人,并且乙也懒得数,所以乙也直接问他前面的丙是第几个。那个小问题又被分解成更小的问题:「丙想知道他是第几个人」。
就这样你问我,我再问他,一直问下去,问题也变得越来越小。虽然越来越小,但是问题的本质并没有变:都是「某人想知道他自己是第几个人」。
当问题来到戊这里,问题被分解到足够小足够简单了:「戊站在柜台前,戊想知道他是第几个人」,戊不用数,也不用问其他人就知道自己是第1个人。为什么?因为他站在柜台前,也就是说,当他看到柜台时,就知道自己是第1个人了。
然后开始不断向后回答,最后甲知道自己是第5个人。
总结一下该例的几个要点:
- 后面的人在询问前面的人(人在问人)
- 每个人在做同样的动作
- 问题在不断变小(简单),但是不论多小,都与最初的大问题一样,目的不变
- 问题没有被无限地问下去,到柜台前,最简单的问题被解决
- 最简单的问题被解决后,开始向后解决问题,直到解决最初的大问题
将这个几个要点对应到具体的编程中就是:
- 方法自己调用自己
- 有重复的逻辑
- 问题在不断变小(简单),但是目的不变
- 方法没有无限的自己调用自己,当问题变为最简时(满足终止条件)停止调用。
- 执行完终止条件(if语句)后,开始返回
根据以上要点得出了一个普遍流程:(这里先写出来,详细解释在文末总结中)
第一步:找到「大问题」是什么?
第二步:找到「最简单的问题」是什么?满足最简单问题时应该做什么?
第三步:找到「重复逻辑」是什么?
第四步:自己调用自己
第五步:返回
下面看几个简单的例子:
例1:给定数字n,打印数字从n至1
第一步:找到大问题是什么?
打印数字从n至1
public static void print(int n) {
}
复制代码
第二步:找到最简单的问题是什么?满足最简单问题时应该做什么?
当数字为0时,不需要打印,所以「打印数字0」是最简单的问题,满足时停止打印
//打印数字从n至1
public static void print(int n) {
if (n == 0)//最简单问题
return;
}
复制代码
第三步:找到重复逻辑是什么?
打印每个数字
//打印数字从n至1
public static void print(int n) {
if (n == 0)//最简单问题
return;
System.out.println(n);//重复逻辑
}
复制代码
第四步:自己调用自己
//打印数字从n至1
public static void print(int n) {
if (n == 0)//最简单问题
return;
System.out.println(n);//重复逻辑
print(n - 1);//自己调用自己
}
复制代码
第五步:返回
方法没有返回值,所以不返回
例2:等差数列,给定第一项为a,公差为d,求第n项的值
如,第一项为1,公差为2的等差数列为:1,3,5,7,9,11……
第一步:找到大问题是什么?
求第n项的值
//已知a:第一项,d:公差,n:求第几项
public static int f(int a, int d, int n) {
}
复制代码
第二步:找到最简单的问题是什么?满足最简单问题时应该做什么?
第1项是已知的,不需要计算,所以「求第1项的值」是最简单的问题,满足时直接返回值
//a:第一项,d:公差,n:求第几项
public static int f(int a, int d, int n) {
if (n == 1)//最简单问题
return a;
}
复制代码
第三步:找到重复逻辑是什么?
第n-1项 + 公差d = 第n项
//a:第一项,d:公差,n:求第几项
public static int f(int a, int d, int n) {
if (n == 1)//最简单问题
return a;
return f(a, d, n - 1) + d;//重复逻辑
}
复制代码
第四步:自己调用自己
//a:第一项,d:公差,n:求第几项
public static int f(int a, int d, int n) {
if (n == 1)//最简单问题
return a;
return f(a, d, n - 1) + d;//重复逻辑、自己调用自己
}
复制代码
第五步:返回
//a:第一项,d:公差,n:求第几项
public static int f(int a, int d, int n) {
if (n == 1)//最简单问题
return a;
return f(a, d, n - 1) + d;//重复逻辑、自己调用自己、返回
}
复制代码
例3:斐波那契数列(1,1,2,3,5,8,13……),求第n项的值
第一步:找到大问题是什么?
求第n项的值
//求第n项
public static int f(int n) {
}
复制代码