用Java谈谈递归问题(有运用举例)_java代码递归和回溯的妙用

目录

前言

一、程序运行的结果？

二、计算机是怎么计算的？

1.代码分析

2.运行原理

三、实际例子

总结

递归→回溯算法

---

前言

什么是递归呢？递归是指 在函数或子过程的内部，直接或者间接地调用自己。来看这个例子：

public class Example {
    public static void main(String[] args) {
        Example(3);
    }
 
    public static void Example(int i) {
        if (i > 0) {
            Example(i - 1);
            System.out.println(i);
        }
    }
}

如代码所示，我们在调用Example函数的时候，Example内部也可以调用自身，调用了自己（没错就是套娃）。那接下来我们就一起来谈一谈递归。

---

一、程序运行的结果？

这里很多没接触过递归的读者就有疑问了，那么这样调用函数最后的结果是什么呢？我们首先来看看函数的运行结果：

如图所知，最后运行的结果是 先打印1，再打印2，最后打印3. 

二、计算机是怎么计算的？

1.代码分析

首先可以看到，我们调用Example(3)的时候，函数按顺序运行。

当函数执行到Example(2)时，调用自身：

 

同时，此时遇到了Example(1)，计算机继续向下运行，当运行到Example(0)时，不过if语句，此时函数执行完毕。

 执行完毕的函数会进行返回，由于这里Example(0)调用完毕，函数会返回到调用Example(0)的地方继续执行，所以这里就返回到了Example(1)处，计算机继续向下执行，走print语句，打印此时i的值1.以此类推，函数逐步返回，最后打印3，函数执行完毕（套娃操作，持续迭代）。

2.运行原理

在JVM虚拟机处理该函数的过程中，使用到了栈，我们知道，栈在处理数据的过程中，遵循先进后出，后进先出的原则。当JVM在处理函数的时候，栈是什么样子的呢？

第一步，计算机执行了Example(3)，将该函数压入了栈中，同理，当Example(3)中调用了Example(2)时，Example(2)也被压入了栈中，直到将Example(0)压入栈中。

当运行到Example(0)时，函数返回，此时JVM将从栈中pop出函数，从上到下，所以这里就从上到下依次执行完函数，直到将栈中的函数处理完毕。

---

三、实际例子

在这里，我们举出一个可以使用递归函数解决的例子：

（第十一届蓝桥杯JavaB组省赛真题）新冠疫情由新冠病毒引起，最近在 A 国蔓延，为了尽快控制疫情，A 国准备给大量民众进病毒核酸检测。然而，用于检测的试剂盒紧缺。为了解决这一困难，科学家想了一个办法：合并检测。即将从多个人（k个）采集的标本放到同一个试剂盒中进行检测。如果结果为阴性，则说明这 k个人都是阴性，用一个试剂盒完成了 k 个人的检测。如果结果为阳性，则说明至少有一个人为阳性，需要将这 k 个人的样本全部重新独立检测（从理论上看，如果检测前 k − 1 个人都是阴性可以推断出第 k 个人是阳性，但是在实际操作中不会利用此推断，而是将 k 个人独立检测），加上最开始的合并检测，一共使用了 k + 1 个试剂盒完成了 k 个人的检测。A 国估计被测的民众的感染率大概是 1%，呈均匀分布。请问 k 取多少能最节省试剂盒？

 问题没看懂？这个问题是这么一个意思：核酸检测，k个人用一个试剂盒，如果这k个人中有阳性，那么这k个人要重新检测，并且确诊率为0.1%，问k取多少用的试剂盒最少。

很多人就有疑问了：总数都不知道，我怎么知道最少取多少？不用慌张，这里我们可以假设总人数，看算出来的结果是怎么样的。仔细分析之后，他试剂盒实际使用的个数呈这样的趋势：

于是我们这样来分析：

我们从2开始，假设2个人用一个试剂盒，算出此时使用的试剂盒个数，然后检测3人一起，与用2人比较，如果3人一起比2人用的个数少，那么此时最少的试剂盒个数改为3人一起的盒数。此时继续判断4人，5人，6人...当检测到n个人时，发现n个人一起使用的还比上一个更多，则此时终止程序，返回上一个的人数，即为最终结果：

     //假设总人数
    static int AllPerson = 108915;
    //初始化AllBox为一盒一人检测的数量
    static double AllBox = AllPerson + AllPerson*0.01;
    static int EndPerson = 0;
    public static void main(String[] args) {
        //从一盒2人开始递归
        checkBox(2);
        if ((int)(AllBox*10) % 10 != 0) {
            AllBox++;
        }
        System.out.println("使用的盒子数为："+AllBox+ "     "+EndPerson);
    }
 
    public static void checkBox(int person) {
        //需要的盒子数
        int box = AllPerson/person + AllPerson/100*person;
        //如果当前的盒子数小于AllBox，则将本次的盒子数重新赋值，并且person+1进行递归
        if (box < AllBox) {
            AllBox = box;
            checkBox(person+1);
        } else {
            //当下一个盒子数比上一个大了则走else，说明已经最小了，此时记录EndPerson
            //注意这里是person-1！
            EndPerson = person-1;
            return;
        }
    }

最后运行结果为10，此时可以更改总人数，发现不管是多少人，k最小的取值都为10（是不是很奇妙~）。

总结

合理地使用递归可以解决很多实际问题，但是在使用递归的时候，有一个缺点，就是：占用内存，如果使用不当，会导致栈溢出，所以在实际使用的时候，要注意递归的优缺点，合理利用算法解决各种问题。

递归→回溯算法

了解了递归之后，就可以利用递归实现回溯算法了。

用递归实现回溯算法https://blog.csdn.net/qq_35813811/article/details/127194757