递归的定义

我们已经学习过方法，使用过方法了。方法体中是可以调用方法的，那么如果在方法体中调用方法自身呢？

特别的，在一个方法当中再次调用这个方法，就像故事里提到同样的故事一样，我们把方法在运行时调用自身的情况，称之为递归，又叫做递归调用。

使用递归的注意事项

递归的使用有很多限制，尤其要注意以下两点：

1. 合法的递归，除了要有递归体语句外，还要有递归出口。无限制的递归下去，会引发栈溢出错误（StackOverflowError）
2. 即便是有出口的递归，递归的深度也不能超过栈空间的大小，否则仍然会报错

案例1: 自然数求和

public static int sum(int n) {
    // 递归出口
    if (n == 1) {
        return 1;
    }
    return n+sum(n-1);
}

递归栈溢出问题

递归是方法自我调用的过程，但是**"只递不归"**的套娃会导致程序崩溃，报错递归栈溢出错误（StackOverflowError），是一个错误（Error），是比Exception要更加的严重的错误。

产生栈溢出错误的原因在于：

1. Java程序运行时，调用方法是有代价的：要占用栈（stack）中的内存空间
2. 方法执行结束后，方法出栈，释放内存，所以一般情况下，栈内存不会溢出，始终够用
3. 无限制的递归调用方法，会导致方法只进栈不出栈，很快栈内存空间就不够用了
4. 这种情况就是"栈溢出错误"，对程序而言是致命错误，程序必须停止执行。

热知识：StackOverflow.com 是全球最大的程序员问答平台。

百度 , CSDN(可能有错) , 掘金, V2ex , google , 知乎 , chatGpt

递归的思想与危险的递归

案例2：使用递归计算N（N>=1）的阶乘**（factorial）**

这个代码很好写，参考如下：

//求n的阶乘
public static long factorial(int n) {
     //建议写递归先写递归出口
     if (n == 1) return 1;
     return n * factorial(n - 1);
}

我们可以总结一下使用递归的两要素：

1. 递归体（方法中自身调用自身方法的那句语句）
2. 递归出口

以上两部分对于一个正常的递归而言都是必须的，在实际使用中，我们只要找到这两个部分就能够写出递归的代码了。

观察这样的一个代码，我们想求n的阶乘，就只需要知道（n - 1）的阶乘的值，（n - 1）阶乘的结果就需要知道（n - 2）阶乘的结果，最终我们知道1的阶乘就是1。

这种将大问题分解为小问题的思想就是递归的思想：

1. 把一个复杂的大规模的问题，分解成若干相似的小规模的子问题。
2. 当子问题规模足够小的时候，就可以直接得到小规模问题的解。
3. 然后把所有的小规模的子问题的解，组合起来，得到要求解的大规模问题的解。

---

对比一下，下面没有使用递归，正常使用for循环的代码：

循环求n的阶乘

public static long factorial2(int n) {
    // n! = n * (n-1) * (n-2) * ...* 1
    int temp = n;
    long result = 1;
    // temp的值会逐渐变小,只要还大于0就要一直乘下去
    while (temp > 0) {
        result *= temp;
        temp--;
    }
    return result;
}

不难发现递归的优点是：

1. 递归的代码会非常简洁，这是最直观的。
2. 人在解决问题的时候，都会下意识的分解问题。递归的思想很符合人的思维，用递归求解一个问题的思路很容易被人理解。
3. 接第二条，一旦能够找打分解问题的思路，递归会非常好用。

当然递归的缺点也非常明显：

1. 不用递归时，往往一个方法就能解决问题。而递归会调用多个方法，占用大量栈内存，且明显存在重复计算，效率低。也就是说，使用递归求解一个问题，时间和空间复杂度都不占优势，既占用空间效率还低。
2. 栈溢出错误警告！递归很危险，一旦栈溢出是严重错误！

---

综上，递归是一把伤人亦伤己的利器，实际开发中不要随意使用递归，使用递归要深思熟虑递归的深度和出口，避免栈溢出错误

经典案例

斐波那契(Feibonacci)数列

1, 1 , 2 , 3 , 5 , 8 , 13 , 21.....

求第n个位置的值是多少

    public static int faibonacci(int n) {
        // 递归出口
        if (n == 2) {
            return 2;
        }
        if (n == 1) {
            return 1;
        }

        return faibonacci(n - 2) + faibonacci(n - 1);
    }

青蛙跳台阶 一只青蛙一次可以跳上一层台阶，也可以跳上两层， 求该青蛙跳上n层的台阶总共有多少种跳法（先后次序不同算不同的结果)

    public static int jumpStep(int n) {
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        return jumpStep(n - 1) + jumpStep(n - 2);
    }