MIT_6.031之递归

递归概念

递归定义：
- 递归是一种解决问题的方法，其中一个问题被分解为更小的相同类型的问题，通过重复调用自身的过程来解决。
基本案例 (Base Case)：
- 基本情况是递归中的终止条件，通常是问题的最简单实例。常见的基本情况包括空字符串、空列表、空集合、空树和数字零等。
递归步骤 (Recursive Step)：
- 将一个较大的问题实例分解为一个或多个可以通过递归调用解决的更简单或更小的实例。最终将这些子问题的结果组合以产生原始问题的解决方案。
辅助方法 (Helper Method)：
- 辅助方法用于支持递归步骤，可以使递归分解更简单或更优雅。一般不向客户公开辅助方法，以避免混淆。
不可变数据的使用：
- 在递归实现中，传入所有变量，使用不可变对象或避免可变对象的共享，确保递归的安全性。

实现子序列的递归示例

以下是一个实现字符串所有子序列的递归方法示例：

/**
 * Return all subsequences of word (as defined above) separated by commas,
 * with partialSubsequence prepended to each one.
 */
private static String subsequencesAfter(String partialSubsequence, String word) {
    if (word.isEmpty()) {
        // base case
        return partialSubsequence;
    } else {
        // recursive step
        return subsequencesAfter(partialSubsequence, word.substring(1))
             + "," 
             + subsequencesAfter(partialSubsequence + word.charAt(0), word.substring(1));
    }
}

public static String subsequences(String word) {
    return subsequencesAfter("", word);
}

解释：

该方法首先检查基本情况（字符串是否为空），然后递归调用，分别处理包含和不包含当前字符的子序列。

将整数转换为字符串的递归示例

以下是将整数转换为具有给定基数的字符串表示形式的递归方法示例：

/**
 * @param n integer to convert to string
 * @param base base for the representation. Requires 2<=base<=10.
 * @return n represented as a string of digits in the specified base, with 
 *           a minus sign if n<0.
 */
public static String stringValue(int n, int base) {
    if (n < 0) {
        return "-" + stringValue(-n, base);
    } else if (n < base) {
        return "" + n; 
    } else {
        return stringValue(n/base, base) + "0123456789".charAt(n%base);
    }
}

解释：

该方法首先处理负数，然后递归地除以基数并收集余数，以生成相应的字符串表示形式。

递归与文件系统示例

递归在自然数据结构中的应用，如文件系统的示例：

/**
 * @param f a file in the filesystem
 * @return the full pathname of f from the root of the filesystem
 */
public static String fullPathname(File f) {
    if (f.getParentFile() == null) {
        // base case: f is at the root of the filesystem
        return f.getName();  
    } else {
        // recursive step
        return fullPathname(f.getParentFile()) + "/" + f.getName();
    }
}

解释：

该方法递归查找文件的父文件夹，构建完整路径。

可重入代码 (Reentrant Code)

可重入性定义

可重入性是指程序中的代码可以安全地被多次调用而不会影响程序的状态或结果。这意味着即使代码在执行中被多次调用，所有的状态信息都保持在局部变量或参数中，而不会受到外部或全局状态的影响。

可重入代码的特性

局部性：
- 可重入代码中的所有状态都存储在局部变量和方法参数中。这使得每次调用该方法时，都能独立于其他调用而正常运行。
无副作用：
- 可重入代码不会修改外部状态或全局变量。任何需要存储的数据都在方法的上下文中，而不会被其他调用或线程影响。
线程安全：
- 在多线程环境中，可重入代码可以被多个线程安全地调用而不产生竞态条件。这是因为每个线程都拥有独立的执行环境。

递归与可重入性

递归作为可重入代码：
- 递归是可重入代码的一种特殊情况，因其自身的调用特性可以自然地保持状态。每次递归调用都使用独立的参数和局部变量，不会与其他调用干扰。
状态的保持：
- 在递归中，函数调用本身形成了一种上下文，递归调用的每一层都持有自己的参数、局部变量和返回地址。这保证了每层递归调用都能独立处理各自的计算，并在基本情况满足时返回。

以下是一个简单的递归函数示例，演示了可重入性：

public static int factorial(int n) {
    // 基本情况
    if (n == 0) {
        return 1;
    }
    // 递归步骤
    return n * factorial(n - 1);
}

可重入性分析：

局部变量：
- 在 factorial 方法中，所有的计算状态（例如，参数 n）都存储在局部作用域中。每次递归调用都会创建一个新的执行上下文。
无副作用：
- 该方法不会改变任何全局状态或外部变量的值。每次调用都会返回一个计算结果，而不影响其他调用。
线程安全：
- 如果在多线程环境中多个线程同时调用 factorial 方法，它们的调用将不会互相干扰，因每个线程都拥有自己的局部变量副本。

可重入性的重要性

错误避免：
- 可重入代码由于其独立性和无副作用的特性，通常更安全，降低了在并发和回调环境中出现错误的风险。
灵活性与重用：
- 可重入代码在设计上更加灵活，可以在更多情况下使用，如并发、异步调用或组合其他函数。它可以更容易地集成到大型系统中，而不会带来意想不到的行为。
代码维护：
- 可重入代码通常更容易理解和维护，因为它的行为是可预测的，且与外部环境的耦合度低。

何时使用递归而不是迭代

使用递归的原因：
1. 问题是自然递归的（例如斐波那契数列）。
2. 数据自然是递归的（例如文件系统）。
3. 利用不变性，递归方法通常为纯函数，没有副作用。
递归的优点：
- 对于自然递归问题，递归实现通常比迭代解决方案更短、更易于理解。
递归的缺点：
- 占用更多内存，递归调用堆栈的大小受到限制。
- 常见错误包括基本案例丢失、递归步骤没有减少到较小子问题等，可能导致 StackOverflowError。