单路递归

二分查找

/*** 主函数：执行二分查找。* * @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;}
}