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

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

举一个生活中的例子

有几个人在柜台前排队，现在甲想知道他排到第几个了，所以他会问排在他前面的乙是第几个，然后加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) {

}
复制代码