Java代码实现—函数递归

目录

1、前言

2、什么是递归

2.1 一则故事

2.2 递归的概念

2.3 递归策略

2.4 递归的两个必要条件

3、递归代码举例

3.1 n的阶乘（递归实现）

3.2 数字之和

3.3 斐波那契数

3.3.1 递归方法实现

3.3.2 迭代(循环)方式实现

4、总结

---

1、前言

本期我们共同来研究一下递归这一概念，如果你C语言有关这方面的知识已经学过了，那么建议跳过这一节，因为思想是一致的，只不过用Java的代码语言来实现而已。如果你没有听说过递归这个概念，那么你要好好看完这篇博客，相信你会有所收获的。

2、什么是递归 2.1 一则故事

那么在开始讲解之前，我们首先要明白，什么是递归，有这样一则故事：

"从前有坐山，山上有座庙，庙里有个老和尚给小和尚将故事，讲的就是：
"从前有座山，山上有座庙，庙里有个老和尚给小和尚讲故事，讲的就是：
"从前有座山，山上有座庙..."
"从前有座山……"

• 上面这个故事中：自身中又包含了自己，该种思想在数学和编程中非常有用，因为有些时候，我们遇到的问题直接并不好解决，但是发现将原问题拆分成其子问题之后，子问题与原问题有相同的解法，等子问题解决之后，原问题就迎刃而解了。

2.2 递归的概念

• 程序调用自身的编程技巧称为递归（ recursion）。
• 递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。

2.3 递归策略

• 只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。
• 递归的主要思考方式在于：把大事化小。

2.4 递归的两个必要条件

• 存在限制条件，当满足这个限制条件的时候，递归便不再继续。
• 每次递归调用之后越来越接近这个限制条件。
• 注意：其实在递推中，比较重要的是找到递推公式，这是递推实现的第一步，递推的代码逻辑很复杂，很难想象真正代码运行的逻辑。

3、递归代码举例 3.1 n的阶乘（递归实现）

• 在码代码之前，我们首先要想清楚这个功能的递推公式，如：3！= 3*2*1；5！= 5*4*3*2*1；依次类推，我们不难发现他的递推公式是： N！= N*(N-1)。
• 其次我们要给定一个限制条件，当满足这个限制条件的时候，递归便不再继续。在这个代码中种也很好想到，当N每次-1的，都在向着最终的条件：N = 1靠近，最终减到1的时候，就return 1即可，即代码不用在继续执行了，所以在这个代码中，N = 1就是限制条件，且每次代码运行，都能越来越接近这个限制条件。
• 递归的2个必要条件满足之后，代码如下：

public static void main(String[] args) {
    int n = 3;
    int ret = factor(n);
    System.out.println("ret = " + ret);
}
public static int factor(int n) {
    if (n == 1) {
    return 1;
}
    return n * factor(n - 1); // factor 调用函数自身
}
// 执行结果
ret = 6

• 鉴于这是本章第一个代码，我会详细分析一下它的代码运行逻辑，还是强调一下，递归的代码运行逻辑十分复杂，还请不要在意一些细节，能找到我上面所说的几点关键点即可。
• 递归分为两个步骤，分别是：递    和    归
• 递：递就是向后传递的过程，为方便大家理解，下图中红色的部分为递的过程，这里我们的N取3，也就是计算3！= 3*2*1这个过程。其中开始时N = 3，执行n*fac(n-1)的代码，这里面的n为3，但是我们发现后面再一次调用了fac函数，也就是自己函数内部调用自己，这就是递归，我们不会计算后面fac(n-1)的值，当然return这一行代码也同样不会执行，我们会在最后归的时候统一计算这两部分的内容；
• 此时n-1之后n = 2，带入到fac函数中去再次执行函数中的代码，会重复上一步递的内容。此时：n = 2；fac(1)，同样的fac和return不会被计算出数值；
• 直到计算完上一步的时候N = 1；此时代码执行到了限制条件的位置，那么递的步骤结束，马上进入归的部分，此时n = 1，代码执行return 1。
• 归：终于千辛万苦到了归的地方，为了方面理解，绿色的线条为归的部分。还记得我们在递的时候fac和return的值都没有计算出来吗，在归的部分，我们都要归回来；
• 上面已经说明了代码执行到了return 1 的部分，return 1 的值也就是第二张图fac(1)的值，这里我们计算tmp = n * fac(1) = 2 * 1;这个代码，return值为2，再执行return tmp的代码，即把return 2的值赋值给到了fac(2);
• 接着计算第一张图的tmp = n * fac(2) = 3 * 2；这回return的值为6，至此代码全部结束。

•  下面的流程图更加方便大家理解，递归是按照编号从1~8进行执行。

 注意：
在递归中，我们只需要找到递推的公式，以及满足递归的两个必要条件即可，代码是如何去运行的个人认为不在我们考虑的范围内。

• 接下来的代码我只会写明递推公式和限制条件，分析的逻辑大同小异，请参照代码1的分析逻辑，如果大家有不懂的地方，欢迎私信或者留言给我。

3.2 数字之和

• 写一个递归方法，输入一个非负整数，返回组成它的数字之和（如123  ：1+2+3）
• 递推公式：

(n % 10) + numSum(n/10)

• 限制条件：因为n < 10 的时候返回自己即可，不用每一位相加。

n < 10

• 代码实现：

  public static void main(String[] args) {
        System.out.println(numSum(12));
    }
    public static int numSum(int n){
        if(n < 10){
            return n;
        }else{
            int sum = (n % 10) + numSum(n/10);
            return sum;
        }
    }

3.3 斐波那契数 3.3.1 递归方法实现

• 这里关于什么是斐波那契数列就不过多介绍了，详情可以百度一下，斐波那契数列的递推公式是固定的。
• 递推公式：

fib(n-1) + fib(n-2)

• 限制条件：我们这里默认第一位和第二位都是1。

n == 1 || n == 2

• 代码实现：

 public static void main(String[] args) {
        System.out.println(fib(41));
    }
    public static int fibRec(int n){
        if(n == 1 || n == 2){
            return 1;
        }else{
            int tmp = fib(n-1) + fib(n-2);
            return tmp;
        }

    }

 注意：

• 当我们求 fib(40) 的时候发现, 程序执行速度极慢，原因是进行了大量的重复运算，即当我们计算fib(3)的时候就将fib(2)计算过了，但是fib(4)的时候我们又一次计算了fib(2)，这就出现了重复计算的情况，使代码效率大大降低。

• 所以我们发现并不是所有的代码都适合用递归的方式，那么上面的代码我们用普通循环的方式再来实现一遍。

3.3.2 迭代(循环)方式实现

• 我们用循环的方式实现斐波那契数，可以看到此时代码的效率大大增加了，不再存在重复计算的代码。

 public static void main3(String[] args) {
        System.out.println(fib(41));
    }
    public static int fib(int n){
        if(n == 1 || n == 2){
            return 1;
        }else{
            int fib1 = 1;
            int fib2 = 1;
            int fib3 = 0;
            for (int i = 3; i <= n ; i++) {
                fib3 = fib1 + fib2;
                fib1 = fib2;
                fib2 = fib3;
            }
            return fib3;
        }
    }

4、总结

1. 许多问题是以递归的形式进行解释的，这只是因为它比非递归的形式更为清晰。
2. 但是这些问题的迭代实现往往比递归实现效率更高，虽然代码的可读性稍微差些。
3. 当一个问题相当复杂，难以用迭代实现时，此时递归实现的简洁性便可以补偿它所带来的运行时开销。
4. 至此，我们的递归的介绍就结束了，如果大家有什么不明白的地方，欢迎大家私信或者留言给我，我会一一回复！