一、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!
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 的階乘）。
輸入示例
5
輸出示例
120
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?項。
輸入示例
6
輸出示例
8
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。
- 規則：
- 一次只能移動一個盤子
- 不能將大盤子放在小盤子上
輸入
3
輸出
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 代碼
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?個盤子從輔助柱子借助源柱子移動到目標柱子，這是遞歸條件。
? 考點
- 遞歸拆解：
- 移動 n-1?個盤子 A → B
- 移動第 n?個盤子 A → C
- 移動 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）：如何將問題分解為更小的子問題。
問題規模縮小：每次遞歸調用應使問題更接近終止條件。
