java递归函数的例子,java递归讲解 收藏 0

解锁Java函数式编程的奇妙世界

在 Java 语言的庞大体系里，函数式编程正扮演着愈发重要的角色。它与传统编程方式有着诸多不同之处，传统编程往往更偏向于命令式编程，侧重于一步一步地告诉计算机要执行的具体步骤，比如通过各种赋值语句、控制语句等来操作变量，实现相应功能。

而函数式编程是一种强调不可变性、纯函数和递归的编程范式。它将函数提升到了 “一等公民” 的地位，意味着函数可以像普通变量一样被传递、赋值以及返回，这极大地增强了代码的灵活性。例如，在 Java 中我们可以利用高阶函数，轻松地把函数作为参数传递给其他函数，或者让函数返回另一个函数，以此实现更为复杂且巧妙的功能组合。

同时，函数式编程鼓励编写纯函数，也就是相同的输入总会得到相同的输出，并且不会产生副作用（不会依赖外部状态或数据，也不会对外部环境产生影响）的函数。这一特性使得代码的测试和调试变得更加容易，也更便于我们去推理和优化代码逻辑。

再者，Java 8 中引入了 Stream API，为函数式编程风格的流式处理提供了有力支持，能够便捷地处理大量的数据集，像对集合进行过滤、映射、排序等操作时，使用 Stream API 配合函数式编程的思维，可以让代码更加简洁明了。

不过，函数式编程也并非十全十美，它存在一定劣势。比如创建和管理不可变数据结构可能比可变数据结构开销更大，在对性能要求极高的应用程序中，这可能会成为一个不容忽视的问题。而且由于函数式代码通常缺乏明显的副作用，在调试时跟踪状态变化相对来说会更困难一些。另外，不可变性和纯函数原则有时会导致代码出现冗余情况，毕竟无法修改现有对象时，往往需要创建新对象来完成相应操作。同时，它与面向对象编程（OOP）范式之间的兼容性也是个挑战，毕竟函数式代码常常需要和 OOP 对象、类进行交互。

但即便存在这些劣势，也不能掩盖函数式编程在 Java 中所展现出的独特优势，它为 Java 开发者们提供了一种全新的、高效的编程思路，值得我们深入探究和学习，接下来就让我们一起详细了解其具体内容吧。

在编程的世界中，存在着多种编程范式，主要的编程范式有命令式编程、声明式编程和函数式编程这三种。

命令式编程侧重于详细地描述计算机执行的具体步骤，就像传统的通过各种赋值语句、控制语句（如 for 循环、if 判断等）来操作变量，一步一步地实现相应功能。例如，要对一个数组的每个元素进行平方操作，用命令式编程可能是这样的：

声明式编程则与之不同，它主要描述目标的性质，让计算机明白要达成的目标是什么，而不用去具体说明流程，是一种更偏向于说明 “做什么”，而非 “怎么做” 的编程方式，典型的如数据库查询语言 SQL，我们只需要指明需要的数据和条件，底层具体如何实现数据查询等操作则由数据库去完成。

而函数式编程，是将电脑运算视为函数的计算，它是声明式编程的一部分，思想上和声明式编程是一致的，同样聚焦于 “做什么”。它的重要基础是 λ 演算（lambda calculus），在函数式编程里，函数可以接受函数当作输入（参数）和输出（返回值），函数能够出现在任何地方，具有很高的灵活性。比如上述数组元素平方操作，用函数式编程可以这样写：

可以看到，函数式编程把运算过程尽量写成系列嵌套的函数调用，更强调程序执行的结果而非执行的过程，倡导利用若干简单的执行单元让计算结果不断渐进，逐层推导复杂的运算，而不是像命令式编程那样去设计一个复杂的执行过程。

Lambda 表达式是 Java 8 中的一个重要特性，它相当于一个没有名字的函数，基本格式是 “(参数) -> {执行代码块}”，主要包含三个部分：

• 圆括号内的参数：这就和正常定义方法时的参数部分类似，可以无参数（此时括号内为空，如 () -> { System.out.println(\”无参数示例\”); }），也可以接受多个参数（比如 (param1, param2) -> { System.out.println(param1 + param2); }）。参数的类型可以明确声明出来，也可以让 JVM 根据上下文来自动推断。

• 箭头符号：“->”，它起着将参数与代码块分隔开的关键作用，是 Lambda 表达式的核心标识。

• 代码块：代表着 Lambda 表达式需要实际执行的功能，可以是简单的一行代码（例如 param -> System.out.println(param)），这种情况下如果代码块只有一行语句且是返回语句，那么方法体前后的 {} 和 return 关键字均可省略；当然也可以是复杂的多行代码，需要用 {} 括起来。

Lambda 表达式相对于匿名内部类有着明显优势，它的语法格式更为简洁明了，能大大减少冗余的代码。例如，在 Java 7 及之前创建并启动一个新线程的代码通常是这样写的：

而在 Java 8 中借助 Lambda 表达式，就可以简洁地写成：

同时，Lambda 表达式的类型实质为函数接口，所谓函数接口，就是只有一个抽象方法的接口（可以添加 @FunctionalInterface 注解来让编译器确保这个接口只能包含一个抽象方法），Lambda 表达式就是对这种函数接口中抽象方法的一种实现方式。例如：

Predicate 接口位于 java.util.function 包中，它是一个函数接口，定义如下：

其主要目的是用于判断一个对象是否满足某个条件，如果满足则返回 true，否则返回 false。它只有一个输入参数，并且接口中还包含多种默认方法，可用于处理更复杂的逻辑判断。

例如，我们可以使用 Predicate 接口来检查一个数字是否为偶数，代码如下：

Predicate 接口与 Java 8 的流 API（Stream API）结合使用时，可以大大简化数据处理代码。比如有一个数字列表，要筛选出其中的所有偶数，可以这样操作：

Function 接口同样在 java.util.function 包下，用于表示接受一个输入参数 T，并返回一个结果 R 的函数，它里面有一个抽象方法 apply，定义如下：

该接口通常用于将数据进行转换（处理逻辑由 Lambda 表达式实现）、映射或者执行某种转换操作。

比如，将字符串转换为对应的整数，可以这样使用 Function 接口：

还可以组合多个函数来实现更复杂的功能，示例如下：

BinaryOperator 接口也是函数式接口，它接收两个参数，返回一个结果，并且要求这两个参数以及返回值的类型是一致的（即 T 类型），它其实是对 Function<T, T> 接口的一种特殊化，常用于对同类型的两个元素进行操作并返回同类型的结果，比如对两个数字进行求和、求乘积等操作。

以下是使用 BinaryOperator 进行两个整数相加的示例：

Supplier 接口存在于 java.util.function 包中，它仅包含一个无参的方法 get，定义如下：

其作用是用来获取一个泛型参数指定类型的对象数据，对应的 Lambda 表达式需要 “对外提供” 一个符合泛型类型的对象数据。例如，要获取一个随机数的示例代码如下：

Consumer 接口同样在 java.util.function 包内，它和 Supplier 接口相反，不是生产一个数据，而是消费一个数据，其数据类型由泛型决定，接口定义为：

代表了在一个输入参数上需要进行的操作，函数返回值为 void。比如可以使用它来输出一个字符串：

这些重要的函数接口在 Java 函数式编程中有着各自的功能和适用场景，合理运用它们可以让代码更加简洁高效，符合函数式编程的风格和要求，帮助我们更好地处理各种数据操作和逻辑判断等任务。

在 Java 中使用函数式编程，能显著提升代码的可读性与可维护性。这得益于函数式编程对不可变数据和纯函数的运用，它消除了副作用以及状态管理的复杂性，使得代码结构更加清晰易懂。

例如，传统的命令式编程在处理集合数据时，往往需要使用循环和大量的临时变量来实现功能，代码容易变得冗长且逻辑分散。而采用函数式编程，利用 Stream API 配合 Lambda 表达式，可以用链式调用的方式来处理集合元素。像对一个整数列表进行筛选出偶数并平方的操作，使用函数式编程可以这样写：

上述代码中，filter方法用于筛选出满足条件（偶数）的元素，map方法则对筛选后的元素进行转换（平方操作），整个过程一目了然，无需像传统方式那样去关注循环的起始、结束以及中间变量的变化等细节，阅读代码时能快速理解其意图。

再比如，当我们需要对多个不同的集合进行类似的操作时，函数式编程的这种风格使得代码的复用性也大大增强，只要功能逻辑一致，就可以轻松复用代码片段，而不用像命令式编程那样针对每个集合都去重写相似的循环和判断逻辑，极大地方便了后续代码的维护和扩展。

函数式编程的纯函数特性，即没有副作用，使得其在多核系统下更具优势，能更容易地实现并行执行，进而提升应用程序的性能。

在多线程环境中，传统编程方式如果要实现并行处理，需要谨慎处理共享变量以及各种锁机制，来避免数据竞争和不一致的情况。但函数式编程中的纯函数，其输出只依赖于输入参数，不依赖也不会修改外部状态，所以多个线程可以安全地并行执行这些纯函数，无需担心线程间的相互干扰。

例如，在处理一个大型数据集的统计任务时，假设有一个包含大量用户信息的列表，我们要分别统计不同年龄段用户的数量。使用函数式编程的并行流（parallelStream）可以这样做：

上述代码中，通过 parallelStream 方法将顺序流转换为并行流，然后利用 collect 方法配合 groupingBy 和 counting 函数式操作，就可以高效地在多核系统上并行统计各年龄段用户数量，而不用像传统多线程编程那样手动去创建线程、分配任务以及协调线程间的同步等复杂操作，让多核处理器的性能得到充分发挥，提高了整个应用程序在处理这类大数据量任务时的执行效率。

函数式编程中强调不可变的数据结构，这一特性在多线程环境下有着重要意义，它能够确保数据的完整性，大大简化调试过程，同时增强应用程序的健壮性。

在多线程并发访问数据时，可变的数据结构很容易出现数据被不同线程同时修改，导致数据不一致的问题，所以往往需要使用复杂的锁机制来保证数据的正确访问和修改。而不可变的数据结构一旦创建就不能被修改，例如 Java 中的 Collections.unmodifiableList 等方法创建的不可变集合，多个线程可以同时安全地读取这些数据，不会出现数据被意外篡改的情况。

比如，有一个场景是多个线程需要读取一个配置列表信息，使用不可变列表来存储配置数据：

在上述代码中，无论多少个线程去读取这个 configList，其数据都始终保持不变，不会出现因为线程间的并发修改而导致的错误，这使得调试程序时不用去追踪复杂的数据变化情况，代码的可靠性和稳定性也更高，即使在复杂的多线程应用场景下也能更健壮地运行。

高阶函数是函数式编程的一个重要特性，它允许将函数作为参数传递或者作为返回值返回，这一特点使得代码更加简洁且具备良好的可重用性。

例如，在数据处理中，我们常常需要对不同的数据集合进行相似的操作，比如先过滤再转换等。通过定义高阶函数，可以把这些通用的操作逻辑抽象出来，方便复用。假设有一个需求是对不同的整数列表分别进行先筛选出大于某个值的数，然后再将这些数乘以一个系数的操作，可以定义这样的高阶函数：

在上述代码中，processList 就是一个高阶函数，它接收一个整数列表、一个筛选条件谓词函数和一个转换函数作为参数，通过函数式编程的方式对输入列表进行处理并返回结果。这样，对于不同的具体需求，只要传入不同的筛选和转换函数，就能复用这个 processList 函数来完成相应的数据处理任务，避免了重复编写相似的循环和操作逻辑代码，让代码变得更加简洁高效。

Java 8 引入的 Stream API 为函数式风格的流式处理提供了强大支持，在处理大量数据集时展现出了极大的便利性。

Stream API 提供了一系列的中间操作（如 filter、map、sorted 等）和终端操作（如 collect、forEach、reduce 等），可以按照声明式的编程风格来操作数据集合。中间操作是惰性求值的，只有在遇到终端操作时才会真正执行，这有助于减少不必要的计算开销，提高性能。

例如，有一个包含大量员工信息的列表，要筛选出工资高于一定水平且年龄在某个区间内的员工，然后按照姓名进行排序并收集到一个新的列表中，可以这样使用 Stream API 进行流式处理：

在上述代码中，先是通过 stream 方法创建流，然后连续使用 filter 方法按照工资和年龄条件进行筛选，接着使用 sorted 方法按照姓名排序，最后用 collect 方法将符合条件的员工收集到新列表中。整个过程清晰简洁，代码的可读性好，并且在处理大量员工数据时能高效地完成复杂的数据筛选和整理任务，相比于传统的循环遍历和条件判断方式，代码更加优雅且性能也更优。

在实际开发场景中，我们常常需要对程序员进行排名，下面就来看一下如何通过函数式编程实现程序员排名这一功能。

假设我们有这样的要求：只有代码量大于 100 行的程序员才参加排名；根据单行代码行缺陷率进行排名，缺陷率越小，排名越高（缺陷率 = bug 数 / 代码行数）；缺陷率相同的情况下，按照代码行数进行排名，行数越多，排名越高；最后输出程序员排名列表，排名高的在后面。

以下是一种可能的函数式编程代码思路及示例：

首先，我们假设有一个 Programmer 类，里面包含 codeLines（代码行数）和 bugCount（缺陷数）等属性，并有对应的 getter 方法。

然后，我们使用函数式编程的方式来处理程序员列表进行排名，代码如下：

在上述代码中：

• filter 方法用于筛选出符合条件（代码量大于 100 行）的程序员，它接收一个 Predicate 类型的参数（这里使用 Lambda 表达式实现了该 Predicate），返回一个新的流，流中只包含满足条件的元素。

• sorted 方法按照我们定义的比较规则对程序员进行排序，这里使用了 Comparator 接口，先是通过 comparingDouble 方法按照缺陷率（通过 Lambda 表达式计算 bugCount 与 codeLines 的比值）进行排序，然后使用 thenComparing 方法在缺陷率相同的情况下按照代码行数进一步排序。

• 最后通过 collect 方法将处理后的结果收集到一个新的列表中，方便后续的使用或者展示。

通过这样的函数式编程方式，我们可以简洁明了地实现程序员排名的功能，而且代码逻辑清晰，易于理解和维护。

首先，我们来明确一下完美数的定义。如果一个自然数恰好等于它的真因子（即除了自身以外的约数）之和，那么就称该数为完美数。例如，第一个完美数是 6，它有约数 1、2、3、6，除去它本身 6 外，其余 3 个数相加，1 + 2 + 3 = 6；第二个完美数是 28，它有约数 1、2、4、7、14、28，除去它本身 28 外，其余 5 个数相加，1 + 2 + 4 + 7 + 14 = 28。

下面是使用函数式编程来判断一个数是否为完美数的代码实现方式：

在上述代码中：

• IntStream.rangeClosed(1, num / 2) 创建了一个从 1 到 num / 2（包含两端）的整数序列流，这个范围是因为一个数的真因子不会超过它的一半。

• filter 方法用于筛选出能整除 num 的数，也就是 num 的真因子，这里通过 Lambda 表达式 i -> num % i == 0 来定义筛选条件。

• 最后使用 sum 方法对筛选出来的真因子进行求和，并与原数 num 进行比较，如果相等则返回 true，表示该数是完美数，否则返回 false。

基于上述判断完美数的方法，我们可以进一步实现一个能生成无穷完美数序列的代码逻辑，如下所示：

在这段代码里：

• Stream.iterate(1, i -> i + 1) 创建了一个从 1 开始，每次递增 1 的无穷整数序列流。

• 接着使用 filter 方法结合之前定义的 isPerfectNumber 方法，对这个无穷序列中的每个数进行判断，筛选出完美数，这样就得到了一个只包含完美数的无穷序列流。

• 在 main 方法中，我们通过 limit(5) 方法取这个无穷完美数序列的前 5 个元素，并使用 forEach 方法进行输出，实际应用中可以根据需要调整获取的数量或者对这些完美数做其他处理。

通过这些代码示例，可以看到函数式编程在处理这类数学相关问题时，能以简洁且高效的方式实现相应功能，让代码更加优雅。

策略模式是一种常见的设计模式，它包含三部分内容：一个代表某个算法的接口、一个或多个接口的具体实现（它们代表了算法的多种实现方式）以及一个或多个使用策略对象的客户代码。

下面我们以一个简单的示例来说明如何通过函数式编程去解决策略模式相关问题。

首先，定义一个代表算法的接口，例如，我们有一个计算价格折扣的场景，接口如下：

这个接口中定义了一个方法 calculateDiscount，用于根据商品价格计算出折扣后的价格，它接收一个 price 参数（商品原价），并返回折扣后的价格。

接着，我们来创建该接口的具体实现，也就是不同的折扣策略，比如有一个八折策略和一个满减策略：

在上述代码中，EightDiscountStrategy 类实现了八折的折扣计算逻辑，直接返回原价乘以 0.8 的结果；而 FullReductionStrategy 类实现了满减策略，根据传入的满减条件（满多少减多少）来计算折扣后的价格，如果商品价格达到满减条件则减去相应金额，否则返回原价。

最后，来看一下如何使用这些策略对象进行价格计算，通过函数式编程的方式，代码如下：

在这段代码中：

• 我们先是将具体的策略实现类的折扣计算方法通过方法引用的方式（如 new EightDiscountStrategy()::calculateDiscount）转化为 Function 类型的函数对象，这样就可以方便地像调用函数一样去应用相应的折扣策略进行价格计算。

• 然后通过 apply 方法传入商品原价，得到折扣后的价格并输出。

• 同时，还展示了可以根据不同的条件（比如用户选择的折扣类型）动态地获取相应的策略对象，再应用该策略进行价格计算，体现了策略模式的灵活性以及函数式编程在其中的便捷应用。

通过函数式编程结合策略模式，我们可以轻松地实现算法的切换和复用，使代码结构更加清晰，易于扩展和维护。

在 Java 函数式编程中，有一些常用的函数接口，它们在不同的业务数据场景下有着广泛的应用，下面针对几个常用函数接口来举例说明如何运用它们进行函数式编程操作。

BiConsumer<T, U> 接口常用于需要对两个不同类型的数据进行操作的场景，例如记录员工评价的情况。

假设我们有一个 Employee 类，包含员工姓名和评价信息，代码如下：

现在要将员工姓名和对应的评价信息进行输出展示，就可以使用 BiConsumer 接口来实现，代码如下：

在上述代码中：

• 首先定义了 BiConsumer<Employee, String> 类型的 recordFeedback，它通过 Lambda 表达式实现了接受一个 Employee 对象和一个评价字符串，并将员工姓名和评价信息输出的操作。

• 然后使用 forEach 方法遍历员工列表，对于每个员工，调用 recordFeedback 的 accept 方法，传入员工对象和其对应的评价信息，从而实现了对所有员工评价信息的记录和展示。

BiFunction<T, U, R> 接口常用于根据两个不同类型的输入参数，经过一定的转换或计算后得到一个结果的场景，比如计算折扣后总价格的情况。

假设有一个 Product 类，包含产品名称和价格属性：

现在要根据产品列表和折扣率来计算折扣后的总价格，代码如下：

在这段代码里：

• 定义了 BiFunction<Product, Double, Double> 类型的 calculateDiscountedPrice，它通过 Lambda 表达式实现了根据产品对象和折扣率计算出该产品折扣后价格的逻辑。

• 接着使用 stream 方法将产品列表转换为流，通过 mapToDouble 方法结合 calculateDiscountedPrice 函数对每个产品应用折扣计算，得到每个产品折扣后的价格流，最后使用 sum 方法对这些折扣后价格进行求和，得到折扣后总价格并输出。

通过这些常用函数接口的应用案例可以看出，合理运用它们能够让我们在面对不同业务需求时，以函数式编程的风格高效地处理数据和实现相应功能，代码也更加简洁明了，易于理解和维护。

在这篇文章中，我们深入探讨了 Java 中函数式编程的相关内容。

首先了解了其核心概念，函数式编程是一种强调不可变性、纯函数和递归的编程范式，将函数提升到 “一等公民” 地位，函数可像普通变量般传递、赋值与返回。与传统命令式编程不同，它聚焦于 “做什么”，属于声明式编程的一部分，思想源于 λ 演算。

接着介绍了一些重要基础元素，像 Lambda 表达式，它相当于无名字的函数，格式为 “(参数) -> {执行代码块}”，相比匿名内部类更加简洁，其类型实质为函数接口。还有如 Predicate<T>、Function<T,R>、BinaryOperator<T>、Supplier<T>、Consumer<T> 等重要的函数接口，它们在判断、转换、操作数据等方面各有独特功能与适用场景。

然后阐述了 Java 函数式编程的诸多优势，例如在代码可读性与可维护性方面，利用不可变数据和纯函数，结合 Stream API 与 Lambda 表达式，能让代码逻辑清晰、便于复用；并发性上，纯函数特性使得在多核系统下更易并行执行，提升性能；不变性保证可确保多线程环境下数据完整性，简化调试且增强健壮性；高阶函数允许函数作为参数传递或返回，提高代码重用性；流式处理借助 Stream API，通过中间操作和终端操作实现对大量数据集的高效便捷处理。

在实际应用案例部分，展示了多个不同场景的示例，包括程序员排名案例，通过筛选、排序等函数式操作实现特定规则的排名功能；完美数相关案例，既能判断一个数是否为完美数，还能生成无穷完美数序列；策略模式案例，结合函数式编程实现了算法接口、具体策略及灵活应用策略进行价格计算；常用函数接口应用案例，如 BiConsumer<T, U> 用于处理两个不同类型数据的操作场景，BiFunction<T, U, R> 可根据两个输入参数进行转换计算得到结果等，展现了不同函数接口在具体业务数据场景下的高效运用。

函数式编程在 Java 中有着广阔的应用前景和巨大的潜力，希望读者们在自己的 Java 编程实践中积极尝试运用函数式编程。无论是处理简单的数据集合操作，还是应对复杂的业务逻辑和多线程并发场景，函数式编程都能为你提供一种简洁、高效且优雅的解决方案。

随着 Java 语言的不断发展和更新，函数式编程也势必会在未来的编程应用中展现出更多的可能性，比如更好地与新的框架、技术结合，进一步优化性能、提升开发效率等。相信通过不断探索学习，大家能够更加熟练地掌握。

递归回溯中的一些套路

本文来源于力扣圈子。作者：reedfan，（点击查看原文）

从一个题说起

39. 组合总和（点击查看题目）

题目描述

给定一个 无重复元素 的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明：

• 所有数字（包括 target）都是正整数。
• 解集不能包含重复的组合。

​

示例 1:

示例 2:

题目分析

题目给出的算法结构为：

首先题目要求返回的类型为 List<List<Integer>>，那么我们就新建一个 List<List<Integer>> 作为全局变量，最后将其返回。

再看看返回的结构，List<List<Integer>>。因此我们需要写一个包含 List<Integer> 的辅助函数，加上一些判断条件，此时结构变成了

重点就是如何进行递归。递归的第一步，当然是写递归的终止条件啦，没有终止条件的递归会进入死循环。那么有 哪些终止条件呢？由于条件中说了都是正整数。因此，如果 target<0,当然是要终止了，如果 target==0，说明此时找到了一组数的和为 target，将其加进去。此时代码结构变成了这样。

我们是要求组成 target 的组合。因此需要一个循环来进行遍历。每遍历一次，将此数加入 list，然后进行下一轮递归。代码结构如下。

似乎初具规模，测试一把结果如下

结果差距有点大，为何会出现如此大的反差。而且发现一个规律，后面的一个组合会包含前面一个组合的所有的数字，而且这些数加起来和 target 也不相等啊。原因出在哪呢？java 中除了几个基本类型，其他的类型可以算作引用传递。这就是导致 list 数字一直变多的原因。因此，在每次递归完成，我们要进行一次回溯。把最新加的那个数删除。此时代码结构变成这样。

再测一下，结果如下：

还是不对。这次加起来都等于 7 了，和上次结果相比算是一个很大的进步了。分析下测试结果。不难能看出，本次结果的主要问题包含了重复的组合。为什么会有重复的组合呢？因为每次递归我们都是从 0 开始，所有数字都遍历一遍。所以会出现重复的组合。改进一下，只需加一个 start 变量即可。talk is cheap, show me the code。

​代码如下：

最后再测一下。

代码通过，但是效率并不高。本题有效果更好的动态规划的解法。本文主要展示递归回溯，就不做具体介绍了。

是不是有点感觉了，那么再来一题。

（点击查看题目）

题目描述

给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。

示例:

题目给出的算法结构为

按照前面的套路，首先建一个 ArrayList<List<Integer>> res 作为全局变量。顺带建一个含有 List<Integer>list 的辅助函数。

此时结构变成如下所示。

对于辅助递归函数。第一步当然是列出终止条件，避免进入死循环。由于题目要求是所有 k 个数的组合。那么很容易知道递归的终止条件为 list.size() == k。

因此，代码结构可变为如下所示。

接下来要进入重头戏了，递归回溯的整个过程。整个递归过程不就是一直将数字加入 list 么。因此可以用一个循环。

在循环中主要做三件事

1.加此轮的数据加入 list。

2.递归进行下一步调用。

3.删除此轮加入的数据进行回溯。

此时代码结构如下：

代码大致结构以及形成，测试一下，结果如下。

通过是通过了，但是真的慢成狗啊。

分析一下原因所在。假设 n = 100, k= 90, i = 15，list 里面就 3 个数据。

按照上面的代码，我们还需要继续循环 85 次。但是想一下，即使后面的循环每次都加一个数据，最后也才 88 个数据。

不能形成一组解。也就是说这些循环都是在做无用功，因此引出一个很重要的知识点。 剪枝循环的终止条件不应该是 i<=n, 应该是 i-1 +(k-list.size()) <= n。

​因此代码如下:

最后运行结果如下。

本文作者：reedfan

声明：本文归作者版权所有，如需转载请联系。

本文作者及来源:Renderbus瑞云渲染农场https://www.renderbus.com