單路遞歸

二分查找

/*** 主函數：執行二分查找。* * @param a 要搜索的數組（必須是已排序的）* @param target 目標值* @return 返回目標值在數組中的索引；如果未找到，則返回 -1*/
public static int binarySearch(int[] a, int target) {// 從數組的第一個元素到最后一個元素開始查找return recursion(a, target, 0, a.length - 1);
}/*** 輔助遞歸函數：執行實際的二分查找操作。* * @param a 要搜索的數組* @param target 目標值* @param i 左邊界索引* @param j 右邊界索引* @return 返回目標值在數組中的索引；如果未找到，則返回 -1*/
public static int recursion(int[] a, int target, int i, int j) {// 如果左邊界索引大于右邊界索引，說明沒有找到目標值if (i > j) {return -1;}// 計算中間點，使用無符號右移避免溢出int m = (i + j) >>> 1;// 檢查中間點的值是否等于目標值if (target < a[m]) {// 如果目標值小于中間點的值，在左半部分繼續查找return recursion(a, target, i, m - 1);} else if (a[m] < target) {// 如果目標值大于中間點的值，在右半部分繼續查找return recursion(a, target, m + 1, j);} else {// 找到目標值，返回其索引return m;}
}

冒泡排序

/*** 優化版冒泡排序的遞歸實現。* * @param a 要排序的數組* @param low 排序范圍的起始索引（包含）* @param high 排序范圍的結束索引（包含）*/
private static void bubble(int[] a, int low, int high) {// 如果起始索引等于結束索引，說明已經沒有需要排序的部分了，直接返回if(low == high) {return;}int j = low; // 初始化j為low，用于記錄最后一次交換的位置// 遍歷從low到high-1的元素for (int i = low; i < high; i++) {// 如果當前元素大于下一個元素，則交換它們的位置if (a[i] > a[i + 1]) {swap(a, i, i + 1); // 調用swap方法交換元素j = i; // 更新最后一次交換的位置}}// 遞歸調用bubble方法，繼續對未排序部分進行排序// 注意：這里使用j而不是high作為新的high值，因為j之后的元素已經是有序的bubble(a, low, j);
}/*** 交換數組中兩個元素的位置。* * @param a 要操作的數組* @param i 第一個元素的索引* @param j 第二個元素的索引*/
private static void swap(int[] a, int i, int j) {int t = a[i]; // 暫存第一個元素a[i] = a[j];  // 將第二個元素賦值給第一個位置a[j] = t;     // 將暫存的第一個元素賦值給第二個位置
}

插入排序

/*** 插入排序的遞歸實現。* * @param a 要排序的數組* @param low 排序范圍的起始索引（包含）* @param high 排序范圍的結束索引（包含）*/
private static void insertion(int[] a, int low, int high) {// 基本情況：如果low大于high，說明已經沒有需要排序的部分了，直接返回if (low > high) {return;}// 保存當前元素值，并從low-1位置開始向前遍歷int t = a[low];int i = low - 1;// 向前遍歷數組，找到t應該插入的位置while (i >= 0 && a[i] > t) {  // 修正比較條件為a[i] > ta[i + 1] = a[i];           // 將較大的元素向后移動i--;}// 如果找到了一個比t小的位置，或者已經到達數組開頭，則將t插入到正確位置if (i + 1 != low) {a[i + 1] = t;}// 遞歸調用insertion方法，處理下一個元素insertion(a, low + 1, high);
}

?多路遞歸

斐波那契數列-Leetcode 509

斐波那契數?（通常用?F(n)?表示）形成的序列稱為?斐波那契數列?。該數列由?0?和?1?開始，后面的每一項數字都是前面兩項數字的和。也就是：

F(0) = 0，F(1)?= 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1

給定?n?，請計算?F(n)?。

示例 1：

輸入：n = 2
輸出：1
解釋：F(2) = F(1) + F(0) = 1 + 0 = 1

示例 2：

輸入：n = 3
輸出：2
解釋：F(3) = F(2) + F(1) = 1 + 1 = 2

示例 3：

輸入：n = 4
輸出：3
解釋：F(4) = F(3) + F(2) = 2 + 1 = 3

?

/*** 計算第n個斐波那契數。* * @param n 斐波那契數列中的位置（從0開始）* @return 第n個斐波那契數*/
public static int fib(int n) {// 基本情況1：當n為0時，返回0if (n == 0) {return 0;}// 基本情況2：當n為1時，返回1if (n == 1) {return 1;}// 遞歸調用：計算第n個斐波那契數，它是前兩個斐波那契數之和return fib(n - 1) + fib(n - 2);  // 修正方法名從f改為fib
}

楊輝三角-Leetcode 118

給定一個非負整數?numRows，生成「楊輝三角」的前?numRows?行。

在「楊輝三角」中，每個數是它左上方和右上方的數的和。

示例 1:

輸入: numRows = 5
輸出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

示例?2:

輸入: numRows = 1
輸出: [[1]]

?

import java.util.ArrayList;
import java.util.List;class Solution {/*** 生成帕斯卡三角形的前 numRows 行。** @param numRows 帕斯卡三角形的行數* @return 包含帕斯卡三角形各行的列表*/public List<List<Integer>> generate(int numRows) {List<List<Integer>> triangle = new ArrayList<>();if (numRows <= 0) {return triangle;}// 逐行構建帕斯卡三角形for (int i = 0; i < numRows; i++) {List<Integer> row = new ArrayList<>(i + 1);// 每一行的第一個和最后一個元素總是 1for (int j = 0; j <= i; j++) {if (j == 0 || j == i) {row.add(1);} else {// 當前行的元素是上一行相鄰兩個元素之和row.add(triangle.get(i - 1).get(j - 1) + triangle.get(i - 1).get(j));}}triangle.add(row);}return triangle;}
}

?