蓝桥杯备考随手记: 递归

2024-04-17 15:48:49

递归是一种解决问题的方法，通过将原问题分解为更小的、相同形式的子问题来解决。在递归中，函数会调用自身来解决这些子问题，直到达到基本情况（终止条件），然后逐层返回结果，最终得到整个问题的解。

1. 递归的特点

自相似性：递归是一种自相似的结构，原问题和子问题具有相同的形式，只是规模不同。
分治思想：递归将一个大问题分解为更小的子问题，通过解决这些子问题来解决原问题。
基本情况：递归函数必须包含一个或多个基本情况（终止条件），用于结束递归调用并返回结果，避免无限递归。

2. 递归的应用

树形结构：递归常用于处理树形结构，如二叉树的遍历、查找等操作。
分治算法：分治算法通常使用递归来将问题分解为更小的子问题，如归并排序、快速排序等。
动态规划：动态规划中的递归可以用来定义子问题之间的关系，实现状态转移方程。
回溯算法：回溯算法也是一种递归的应用，通过不断尝试可能的选择来解决问题。

3. 递归的优缺点

优点：递归通常代码简洁易懂，能够自然地表达问题的分解和解决过程。
缺点：递归可能会导致堆栈溢出（stack overflow）等问题，因为每次递归调用都会占用一定的内存空间。另外，递归的效率可能不如迭代，因为递归调用函数时会有一定的开销。

4. 执行过程

一个典型的例子是计算阶乘。阶乘的定义是n! = n * (n-1)!，其中0! = 1。可以看出，阶乘问题可以通过将其分解为更小的阶乘问题来解决，直到达到基本情况（0! = 1）。下面是一个使用递归实现计算阶乘的函数：

public static int factorial(int n) {
        // 基本情况
        if (n == 0) {
            return 1;
        }

        // 递归关系
        return n * factorial(n - 1);
    }

递归函数的调用过程如下：

当调用factorial(4)时，n的值为4，返回4 * factorial(3)；
当调用factorial(3)时，n的值为3，返回3 * factorial(2)；
当调用factorial(2)时，n的值为2，返回2 * factorial(1)；
当调用factorial(1)时，n的值为1，返回1 * factorial(0)；
当调用factorial(0)时，n的值为0，满足基本情况，返回1。

递归函数会一直调用自己，直到达到基本情况，然后逐层返回结果，最终得到所需的阶乘结果。

5. 数学应用

在数学中，递归通常用数学公式或方程来表示。一般来说，递归数学表达式包含两部分：基本情况和递归情况。

基本情况：基本情况是递归定义中的结束条件，通常是一个已知的值或表达式，用于终止递归过程。
递归情况：递归情况描述了如何通过递归调用来计算问题的解。递归情况通常包含一个或多个自身调用的表达式，用于将问题分解为更小的子问题。

数学中的递归定义通常使用数学符号和函数来表示。例如，斐波那契数列就是一个经典的递归数学定义，可以表示为：

基本情况：F(0)=0，F(1)=1
递归情况：F(n)=F(n−1)+F(n−2)，其中n≥2

这个定义说明斐波那契数列的第n个元素可以通过前两个元素的和来计算，直到达到基本情况。

以下是使用Java代码示范使用递归解决斐波那契数列的例子：

public class Fibonacci {
    public static int fibonacci(int n) {
        // 基本情况
        if (n <= 1) {
            return n;
        }
        // 递归情况
        return fibonacci(n - 1) + fibonacci(n - 2);
    }

    public static void main(String[] args) {
        int n = 10;
        System.out.println("斐波那契数列的第 " + n + " 个数是：" + fibonacci(n));
    }
}

6. 递归优化

记忆化递归是一种优化递归算法的方式，通过存储已计算的结果，避免重复计算相同的子问题。具体步骤包括：

定义存储结构：选择合适的数据结构（如数组、哈希表）存储计算结果。
编写递归函数：在递归函数中添加对存储结构的查询和更新操作，实现记忆化计算。
终止条件：定义递归的终止条件，确保正确结束递归过程。
使用存储结构：在递归函数中查询存储结构，避免重复计算，提高算法效率。

记忆化递归能够显著提高递归算法的效率，减少计算开销，特别适用于存在重复子问题的情况。通过记忆化递归优化，可以将指数级别的时间复杂度降低为多项式级别，提高算法的性能和效率。

以下是一个使用Java实现记忆化递归的示例，解决斐波那契数列问题：

import java.util.HashMap;
import java.util.Map;

public class MemoizationExample {

    // 创建一个Map用于存储已计算的结果
    private static Map<Integer, Integer> memo = new HashMap<>();

    // 计算斐波那契数列的方法
    public static int fibonacci(int n) {
        // 如果n小于等于1，直接返回n
        if (n <= 1) {
            return n;
        }

        // 如果已经计算过位置为n的结果，直接返回
        if (memo.containsKey(n)) {
            return memo.get(n);
        }

        // 否则进行递归计算，并将结果存储在memo中
        int result = fibonacci(n - 1) + fibonacci(n - 2);
        memo.put(n, result);
        return result;
    }

    public static void main(String[] args) {
        int n = 10;
        // 计算斐波那契数列第10个位置的值
        int result = fibonacci(n);
        System.out.println("斐波那契数列第" + n + "个位置的值为: " + result);
    }
}

码农公寓