数据结构与算法-递归

单路递归

二分查找

/**
 * 主函数：执行二分查找。
 * 
 * @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] > t
        a[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时，返回0
    if (n == 0) {
        return 0;
    }
    
    // 基本情况2：当n为1时，返回1
    if (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);
            
            // 每一行的第一个和最后一个元素总是 1
            for (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;
    }
}