蓝桥杯 Java B 组之函数定义与递归入门

一、Java 函数（方法）基础

1. 什么是函数？

函数（方法）是 一段可复用的代码块，通过 函数调用 执行，并可返回值。在 Java 里，函数也被叫做方法，它是一段具有特定功能的、可重复使用的代码块。函数能够把复杂的问题分解成小的子问题，提升代码的可读性与可维护性。

Java 方法的格式：

修饰符返回值类型函数名(参数列表)

{ // 函数体 return 返回值; // 如果返回值类型是 void，则不需要 return 语句

}

修饰符：像 public、private、static 等，用于限定函数的访问权限和特性。
返回值类型：函数执行完毕后返回结果的数据类型，若不返回任何值，使用 void。
函数名：给函数起的名称，要遵循命名规范。
参数列表：传递给函数的参数，多个参数用逗号分隔。
函数体：实现具体功能的代码。
返回值：使用 return 语句返回函数的执行结果。

2. Java 方法定义

（1）无参数无返回值

public static void sayHello() {

System.out.println("Hello, 蓝桥杯!");

}

调用：

sayHello();

（2）有参数有返回值

public static int add(int a, int b) {

return a + b;

}

调用：

int sum = add(5, 3); // sum = 8

3. 递归函数

递归（Recursion）是函数自己调用自己

1. 递归的概念

递归是指在函数的定义中使用函数自身的方法。递归包含两个关键要素：

基线条件（终止条件）：能够直接得出结果，不再进行递归调用的条件，避免无限递归。

递归条件：函数调用自身来解决规模更小的子问题。

通常用于：

数学计算（如阶乘、斐波那契数列）
问题拆解（如汉诺塔、深度优先搜索）

二、递归的基本概念

1. 递归的两部分

✅ （1）基准情况（终止条件）：防止无限递归
✅ （2）递归关系（拆分问题）：将大问题分解成小问题

示例：递归求 n!

java">public static int factorial(int n) {if (n == 0 || n == 1) {  // 终止条件return 1;}return n * factorial(n - 1);  // 递归调用}调用：System.out.println(factorial(5));  // 5! = 120

三、练习 1：递归求阶乘

题目描述

输入 n，求 n!（n 的阶乘）。

输入示例

输出示例

120

Java 代码

java">import java.util.Scanner;public class Main {public static int factorial(int n) {if (n == 0 || n == 1) {return 1;}return n * factorial(n - 1);}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();System.out.println(factorial(n));}}

✅ 考点

递归终止条件：n == 0 || n == 1
递归调用：n * factorial(n - 1)
时间复杂度 O(n)

⚠️ 易错点

没有终止条件，导致无限递归
n 太大时可能导致栈溢出（StackOverflowError）

四、练习 2：递归求斐波那契数列

1. 斐波那契数列定义

F(n)=F(n−1)+F(n−2)

其中：

F(0) = 0
F(1) = 1

题目描述

输入 n，输出斐波那契数列的第 n 项。

输入示例

输出示例

Java 代码

java">import java.util.Scanner;public class Main {public static int fibonacci(int n) {if (n == 0) {return 0;} else if (n == 1) {return 1;}return fibonacci(n - 1) + fibonacci(n - 2);}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();System.out.println(fibonacci(n));}}

✅代码解释：

当 n 为 0 时返回 0，当 n 为 1 时返回 1，这是基线条件。

当 n 大于 1 时，函数调用自身 fibonacci(n - 1) 和 fibonacci(n - 2) 并将结果相加，这是递归条件。

考点

递归终止条件：n == 0 或 n == 1
递归公式：F(n) = F(n-1) + F(n-2)
时间复杂度 O(2^n)（指数级，效率低）

⚠️ 易错点

直接递归 O(2^n) 太慢，n 较大时严重超时
优化方案：使用数组存储已计算值（记忆化递归）

五、练习 3：汉诺塔问题

1. 题目介绍

汉诺塔问题：汉诺塔问题是一个经典的递归问题，目标是把所有盘子从一根柱子移动到另一根柱子，每次只能移动一个盘子，且大盘子不能放在小盘子上面。

有 n 个盘子，从 A 移到 C，借助 B。
规则：
- 一次只能移动一个盘子
- 不能将大盘子放在小盘子上

输入

输出

Move disk 1 from A to C

Move disk 2 from A to B

Move disk 1 from C to B

Move disk 3 from A to C

Move disk 1 from B to A

Move disk 2 from B to C

Move disk 1 from A to C

Java 代码

java">import java.util.Scanner;public class Main {public static void hanoi(int n, char from, char aux, char to) {if (n == 1) {System.out.println("Move disk 1 from " + from + " to " + to);return;}hanoi(n - 1, from, to, aux);System.out.println("Move disk " + n + " from " + from + " to " + to);hanoi(n - 1, aux, from, to);}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();hanoi(n, 'A', 'B', 'C');}}

代码解释：

当 n 为 1 时，直接将盘子从源柱子移动到目标柱子，这是基线条件。
当 n 大于 1 时，先把 n - 1 个盘子从源柱子借助目标柱子移动到辅助柱子，再把第 n 个盘子从源柱子移动到目标柱子，最后把 n - 1 个盘子从辅助柱子借助源柱子移动到目标柱子，这是递归条件。

✅ 考点

递归拆解：
1. 移动 n-1 个盘子 A → B
2. 移动第 n 个盘子 A → C
3. 移动 n-1 个盘子 B → C
时间复杂度 O(2^n)

⚠️ 易错点

if (n == 1) 不能少，否则死循环
hanoi(n - 1, from, to, aux) 和 hanoi(n - 1, aux, from, to) 位置不能搞错

六、蓝桥杯递归常考点

考点	典型题目	难点
递归求阶乘	n! = n * (n-1)!	终止条件 n == 1
递归求斐波那契	F(n) = F(n-1) + F(n-2)	优化记忆化递归
汉诺塔	递归移动盘子	移动顺序和 O(2^n)

七、递归的易错点总结

1. 基线条件缺失或错误

如果基线条件不正确或者缺失，会导致无限递归，最终引发栈溢出异常。

2. 重复计算问题

在递归过程中，可能会出现大量的重复计算，比如斐波那契数列递归实现，会使时间复杂度呈指数级增长。可以使用记忆化搜索或迭代方法来优化。

3. 递归深度过大

当递归深度过大时，会占用大量的栈空间，容易导致栈溢出。要注意递归深度的控制，必要时转换为迭代实现。

递归核心思想

1. 递归三要素

终止条件（Base Case）：递归何时结束。

递归步骤（Recursive Step）：如何将问题分解为更小的子问题。

问题规模缩小：每次递归调用应使问题更接近终止条件。