专栏名称: 行人观学
公众号:行人观学
目录
相关文章推荐
51好读  ›  专栏  ›  行人观学

不知道怎样用递归?按步骤来!

行人观学  · 掘金  ·  · 2020-06-20 12:09

正文

阅读 1

不知道怎样用递归?按步骤来!

「递归」这个词语我们经常在很多地方看到,在很多地方用到。但是初学递归时可能会有些难以理解。本文从一些易懂、常见的例子中介绍一下「递归」。

当我们看到「递归」时,不要把它看成一个词语,而是分开看成两个字「递」和「归」。

举一个生活中的例子

有几个人在柜台前排队,现在甲想知道他排到第几个了,所以他会问排在他前面的乙是第几个,然后加1即可。

但是乙也不知道他是第几个,所以乙会问排在他前面的丙是第几个,然后加1即可。

这样一直向前问……

直到问到戊了,此时戊就站在柜台前,所以戊知道他是第1个,然后回答丁。

丁知道他前面的人是第1个,那么丁就知道他是第2个了,然后回答丙。

这样一直向后回答……

甲知道了他前面的人是第4个,那么甲就知道他是第5个了。

在这里插入图片描述
在这个例子中,大问题是「甲想知道他是第几个人」,但是这条队伍排的太长了一眼望不到头,或者甲忘记带眼镜了看不清。所以甲不能一下解决这个大问题,那么他只能问排在他前面的乙是第几个,这样就把这个大问题分解成一个小问题:「乙想知道他是第几个人」,当甲解决了小问题,那么大问题也就迎刃而解了。

那么乙是第几个人呢?这就不是甲操心的事了,因为甲也不知道乙是第几个人。不幸的是,乙也不知道他自己是第几个人,并且乙也懒得数,所以乙也直接问他前面的丙是第几个。那个小问题又被分解成更小的问题:「丙想知道他是第几个人」。

就这样你问我,我再问他,一直问下去,问题也变得越来越小。虽然越来越小,但是问题的本质并没有变:都是「某人想知道他自己是第几个人」。

当问题来到戊这里,问题被分解到足够小足够简单了:「戊站在柜台前,戊想知道他是第几个人」,戊不用数,也不用问其他人就知道自己是第1个人。为什么?因为他站在柜台前,也就是说,当他看到柜台时,就知道自己是第1个人了。

然后开始不断向后回答,最后甲知道自己是第5个人。

总结一下该例的几个要点:

  1. 后面的人在询问前面的人(人在问人)
  2. 每个人在做同样的动作
  3. 问题在不断变小(简单),但是不论多小,都与最初的大问题一样,目的不变
  4. 问题没有被无限地问下去,到柜台前,最简单的问题被解决
  5. 最简单的问题被解决后,开始向后解决问题,直到解决最初的大问题

将这个几个要点对应到具体的编程中就是:

  1. 方法自己调用自己
  2. 有重复的逻辑
  3. 问题在不断变小(简单),但是目的不变
  4. 方法没有无限的自己调用自己,当问题变为最简时(满足终止条件)停止调用。
  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) {

}
复制代码






请到「今天看啥」查看全文