1- 递归 (Recursion)

递归的概念与模式

• 定义: 递归是一种解决问题的方法，其中问题的解决方案依赖于解决相同问题的较小实例。

• 关键思想: 函数调用自身来解决问题的较小版本，它允许一个方法调用自己来解决问题。递归的关键在于将问题分解成更小的、更容易管理的问题，直到达到一个简单的解决方案。

• 递归模式:

  • 基本情况（Base Case）: 最简单的情况，不需要继续进一步递归，它防止递归无限进行。
  • 递归情况（Recursive Case）: 是方法内部调用自己以解决问题的一部分，将问题分解为更小的子问题，并递归调用自身来解决子问题。它必须逐步逼近基础情况，否则递归可能会导致无限循环。

递归是一种强大的工具，但也需要谨慎使用，以避免栈溢出错误和效率问题。在实际应用中，我们需要平衡递归与迭代的使用。

阶乘函数的递归定义

• 数学定义: n! = n * (n-1) * (n-2) * ... * 2 * 1

• 递归定义:

  • 基本情况: 0! = 1
  • 递归情况: n! = n * (n-1)!

阶乘的递归实现：

public static int factorial(int n) {
    if (n == 0) {  // 基础情况
        return 1;
    } else {       // 递归调用
        return n * factorial(n - 1);
    }
}

使用递归跟踪可视化递归

递归跟踪是一种用来理解和分析递归方法执行过程的技巧。通过逐层跟踪每次方法调用和返回的值，可以直观地看到递归的工作过程。

例如，计算 factorial(3) 的递归跟踪：

• factorial(3) 需要计算 3 * factorial(2)

• factorial(2) 需要计算 2 * factorial(1)

• factorial(1) 需要计算 1 * factorial(0)

• factorial(0) 返回 1

• 然后依次返回，计算出 1, 2, 6 的结果。

• 递归的入口点：当我们调用 factorial(3) 时，这是递归的入口。在这里，递归还没有开始展开其过程。

• 递归的展开：

  • factorial(3) 调用自身计算 3 * factorial(2)。此时，factorial(3) 暂时搁置，等待 factorial(2) 的结果。

  • 接着，factorial(2) 继续调用 2 * factorial(1)。同样，factorial(2) 现在等待 factorial(1) 的结果。

  • 进一步地，factorial(1) 调用 1 * factorial(0)。由于已经接近基本情况，factorial(1) 等待 factorial(0) 的结果。

• 达到基本情况：

  • factorial(0) 是基本情况，按照函数定义，直接返回 1。这是递归调用的最底层，没有更多的递归发生。

• 递归的回溯：

  • 一旦 factorial(0) 返回 1，factorial(1) 能完成其计算：1 * 1 = 1，然后返回这个结果 1。

• 接下来，factorial(2) 接收到 factorial(1) 的结果 1，完成 2 * 1 = 2，并返回结果 2。

• 最后，factorial(3) 得到 factorial(2) 的结果 2，完成 3 * 2 = 6，并返回最终结果 6。

线性递归（Linear Recursion）

线性递归是指每次递归调用仅进行一次进一步的递归调用，递归深度与输入规模成正比。比如前面的阶乘计算就是线性递归的例子。

线性递归的特点： - 每个递归调用仅调用一次自身。 - 递归深度与输入规模成正比。

另一示例：计算数组的和

public int sum(int[] array, int n) {
    if (n == 0) {
        return 0;
    } else {
        return sum(array, n - 1) + array[n - 1];
    }
}

二分递归（Binary Recursion）

二分递归是指每次递归调用进行两次进一步的递归调用，常用于分治法（Divide and Conquer）中。

二分递归的特点： - 每个递归调用进行两次递归调用。 - 递归深度与输入规模的对数成正比。

示例：斐波那契数列

public int fibonacci(int n) {
    if (n <= 1) {
        return n;
    } else {
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

使用重复平方计算幂的递归方法

递归可以用于高效地计算幂，通过重复平方法（Repeated Squaring）。

重复平方法的特点： - 当 $n$ 是偶数时：$a^n = (a^{n/2})^2$ - 当 $n$ 是奇数时：$a^n = a \cdot a^{n-1}$

示例：递归计算幂

public double power(double x, int n) {
    if (n == 0) {
        return 1;
    } else if (n % 2 == 0) {
        double half = power(x, n / 2);
        return half * half;
    } else {
        return x * power(x, n - 1);
    }
}

尾递归及其转化为迭代方法

尾递归（Tail Recursion）

尾递归是指递归调用是函数中的最后一个操作，可以被编译器优化为迭代，从而避免栈溢出。

尾递归示例：计算阶乘

public int factorialTailRec(int n, int result) {
    if (n == 0) {
        return result;
    } else {
        return factorialTailRec(n - 1, n * result);
    }
}

// 调用时：factorialTailRec(5, 1)

转化为迭代方法

尾递归可以很容易地转化为迭代方法，因为其递归调用处于函数的最后。

迭代版阶乘

public int factorialIterative(int n) {
    int result = 1;
    while (n > 0) {
        result *= n;
        n--;
    }
    return result;
}

二分递归方法：drawTicks 和 BinarySum

drawTicks 方法

drawTicks 是一个典型的二分递归示例，用于绘制标尺上的刻度。

public void drawTicks(int tickLength) {
    if (tickLength > 0) {
        drawTicks(tickLength - 1);
        drawLine(tickLength);
        drawTicks(tickLength - 1);
    }
}

public void drawLine(int tickLength) {
    for (int i = 0; i < tickLength; i++) {
        System.out.print("-");
    }
    System.out.println();
}

BinarySum 方法

BinarySum 是另一个二分递归示例，用于计算数组一部分元素的和。

public int binarySum(int[] array, int low, int high) {
    if (low > high) {
        return 0;
    } else if (low == high) {
        return array[low];
    } else {
        int mid = (low + high) / 2;
        int leftSum = binarySum(array, low, mid);
        int rightSum = binarySum(array, mid + 1, high);
        return leftSum + rightSum;
    }
}

计算斐波那契数列的算法

-递归

二分递归

这是最直接的递归实现，也是最容易理解的方法。它直接根据斐波那契数列的定义来计算。

虽然斐波那契数列的直接递归实现可以被视为一种二分递归，因为每次调用会生成两个递归调用，但这种方法在效率上并不理想。然而，对于其他一些问题，如快速排序、归并排序或二叉树操作，二分递归是非常有效的。

实现代码：

public int fibonacci(int n) {
    if (n <= 1) {
        return n;
    } else {
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

• 时间复杂度：$O(2^n)$ . 这是因为每增加一层递归，调用次数几乎呈指数增长。非常低效，因为它会重复计算很多次相同的值。例如，计算 fibonacci(5) 时，fibonacci(2) 被计算了三次。
• 空间复杂度：$O(n)$ . 这主要是因为递归调用时，栈的深度最大可以达到n。

线性递归

数组线性递归

这个递归方法的主要特点是它使用一个数组 F 来存储每次递归调用的结果，并将其传递回上一个递归层级。这不仅仅是一个纯粹的线性递归，因为它试图通过保存中间结果来减少计算量，虽然它没有使用传统意义上的动态规划的备忘录方法。

方法定义：

public static int[] linearFib(int n) {
    if (n <= 1) {
        return new int[] {n, 0};
    } else {
        int[] F = linearFib(n-1);
        return new int[] {F[0] + F[1], F[0]};
    }
}

代码解释：

• 如果 n 小于或等于 1，函数返回一个数组，其中第一个元素是 n（即斐波那契数），第二个元素是 0。
• 如果 n 大于 1，函数递归调用 linearFib(n-1)。这个调用将返回一个包含前两个斐波那契数的数组 F。
• 函数接着返回一个新的数组，第一个元素是 F[0] + F[1]（即当前 n 的斐波那契数），第二个元素是 F[0]（即前一个斐波那契数）。

优点：

• 此方法通过传递一个包含两个斐波那契数的数组来避免重复计算，比传统的递归方法效率更高。
• 相比于直接的递归调用两次来求解 n-1 和 n-2 的值，此方法只进行一次递归调用，从而减少了计算量。

缺点：

• 尽管比简单递归高效，但相比于带备忘录的递归或迭代解法，此方法的空间效率较低，因为这种方法在每一层递归中都要创建一个新的数组来存储结果，因此它消耗更多的内存。

• 时间复杂度：$O(n)$ . 每个数字只计算一次，之后直接从数组中取用，减少了重复计算。

• 空间复杂度：$O(n)$ . 递归过程中需要保存所有计算过的斐波那契数到数组。

带备忘录的递归方法（自顶向下的动态规划）

这种方法通过数组存储已计算的斐波那契数，避免重复计算，从而显著提高效率。

实现代码：

public int fibonacciMemo(int n) {
    int[] memo = new int[n + 1];
    Arrays.fill(memo, -1);  // 初始化备忘录
    return fib(n, memo);
}

private int fib(int n, int[] memo) {
    if (memo[n] != -1) {
        return memo[n];
    }
    if (n <= 1) {
        memo[n] = n;
    } else {
        memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
    }
    return memo[n];
}

• 时间复杂度：$O(n)$ . 每个数字只计算一次，计算结果存储在备忘录中，后续直接使用。
• 空间复杂度：$O(n)$ . 需要一个数组来存储计算结果，数组的大小为n+1。

尾递归

尾递归是递归中的特殊情况，其中递归调用是函数中的最后一个操作。尾递归可能被编译器优化为循环，从而节省栈空间。

实现代码：

public int fibonacciTailRec(int n) {
    return fibTailRec(n, 0, 1);
}

private int fibTailRec(int n, int a, int b) {
    if (n == 0) {
        return a;
    } else {
        return fibTailRec(n - 1, b, a + b);
    }
}

• 时间复杂度：$O(n)$ . 递归的每次调用处理一个元素，直到基本案例。
• 空间复杂度：理论上应为 $O(1)$，因为可以通过优化转换为迭代形式，但在Java中，由于JVM通常不优化尾递归，实际空间复杂度仍为 $O(n)$ .

-迭代

迭代方法（动态规划）

一种常见的优化方法是将递归转化为迭代。这种方法不仅能保持 $O(n)$ 的时间复杂度，而且还可以减少递归调用的开销。

public int fibonacciIterative(int n) {
    if (n <= 1) {
        return n;
    }
    int[] dp = new int[n + 1];
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

• 时间复杂度：$O(n)$ . 逐个计算每个斐波那契数直到第n个。
• 空间复杂度：$O(n)$ . 需要一个数组来存储斐波那契序列的所有值。

空间优化（滚动数组）

尽管迭代方法高效，但我们仍然可以进一步减少空间复杂度。使用滚动数组的技术，我们可以将空间复杂度从 $O(n)$ 降低到 $O(1)$。

public int fibonacciOptimized(int n) {
    if (n <= 1) {
        return n;
    }
    int prev2 = 0;  // F(n-2)
    int prev1 = 1;  // F(n-1)
    int curr = 0;
    for (int i = 2; i <= n; i++) {
        curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }
    return curr;
}

• 时间复杂度：$O(n)$ . 仍然是逐个计算每个斐波那契数。
• 空间复杂度：$O(1)$ . 使用固定数量的变量来存储最近的两个斐波那契数，不需要额外的存储空间。

多重递归（Multiple Recursion）

多重递归（Multiple Recursion）是递归的一种形式，其中一个函数在每次递归调用中不止一次调用自己。这与最常见的线性递归（单一递归调用）或二分递归（每次递归进行两次调用）相区别，多重递归涉及每个递归实例可以产生多于两个递归调用的情况。

特点

• 多递归调用：在函数的一个递归过程中，会有多个递归调用发生，通常用于更复杂的问题解决，如图形分割、多分支树结构处理等。
• 结构复杂：多重递归的结构通常比单一递归或双重递归更为复杂，因为需要处理更多的递归分支。
• 计算成本高：由于每一层递归可能产生多个递归调用，多重递归通常具有较高的时间复杂度和潜在的空间复杂度。

示例：多叉树遍历

假设有一个多叉树，每个节点有多个子节点，遍历这种树结构是多重递归的一个典型例子。

class Node {
    int value;
    List<Node> children;

    Node(int value) {
        this.value = value;
        this.children = new ArrayList<>();
    }
}

public void traverse(Node node) {
    if (node == null) return;
    // 处理当前节点
    System.out.println(node.value);
    // 递归处理所有子节点
    for (Node child : node.children) {
        traverse(child);
    }
}

在这个例子中，traverse 方法对于每个节点会递归调用其所有子节点，这是多重递归的体现。

应用

多重递归常见于以下情景： - 计算图形或数学中的分形结构：例如计算科赫雪花或谢尔宾斯基三角形等。 - 处理具有多个可能分支的决策树：如棋类游戏的决策过程中模拟所有可能的移动。 - 复杂的数据结构操作：如多叉树遍历、图的深度优先搜索（DFS）等。

注意事项

由于多重递归的复杂性和高计算成本，它可能导致性能问题，特别是在深度大、分支多的情况下。因此，实现多重递归时，应特别注意其性能影响和潜在的栈溢出问题，适时考虑使用迭代、动态规划或其他优化技术来改进效率。

多重递归和二分递归的区别

在递归编程中，“多重递归”（Multiple Recursion）和“二分递归”（Binary Recursion）是两种常见的递归模式。它们的主要区别在于递归调用的次数和结构。我们来详细比较这两种递归模式：

二分递归（Binary Recursion）

二分递归指的是在每次递归的函数调用中，函数体内部发生两次递归调用。这种模式常常用于那些可以自然地被分成两个子问题的问题，如二叉树的遍历、快速排序、归并排序等。

特点：

• 递归分解：问题被分解为两个独立的子问题，每个子问题由一次递归调用处理。
• 结构：通常用于处理具有二分性质的数据结构，如二叉树。

示例：二叉树的高度计算

public int height(TreeNode root) {
    if (root == null) return -1;
    return 1 + Math.max(height(root.left), height(root.right));
}

在这个例子中，递归函数 height 调用自身两次，分别计算左子树和右子树的高度，然后取两者的最大值。

多重递归（Multiple Recursion）

多重递归是指在每次递归的函数调用中，函数体内发生多于两次的递归调用。这种模式适用于那些可以被分解成多个子问题的情况。

特点：

• 递归分解：问题被分解成多个子问题，每个子问题由一次递归调用处理。
• 结构：用于更复杂的问题或数据结构，比如图的遍历、多叉树的操作等。

示例：n-叉树的节点总数

public int totalNodes(NaryTreeNode root) {
    if (root == null) return 0;
    int count = 1; // 当前节点
    for (NaryTreeNode child : root.children) {
        count += totalNodes(child); // 对每个子节点递归
    }
    return count;
}

在这个例子中，totalNodes 函数对每个子节点进行递归调用，子节点的数量可以是任意多的，因此这是一个多重递归的例子。

区别总结

• 递归次数：二分递归恒定为两次递归调用，而多重递归可以有两次以上，具体取决于问题的性质。
• 适用问题：二分递归适用于问题自然分为两个部分的场景，而多重递归适用于可以分解成多个部分的更复杂或更广泛的问题。
• 实现复杂性：多重递归往往在实现上更复杂，需要处理更多的子问题和递归调用。

理解这两种递归模式的差异有助于选择合适的递归策略来解决具体问题，提高程序的效率和可读性。

迭代和递归方法实现数组反转

在实现数组反转的问题中，递归和迭代是两种常用的方法。这两种方法各有优缺点，适用于不同的情况。下面是关于如何使用递归和迭代来反转数组的详细笔记。

-迭代

迭代方法是实现数组反转的一种直观且常见的方式。它通过交换数组两端的元素逐步向中心靠拢，直至所有元素的位置都被反转。

实现代码：

public void reverseArrayIteratively(int[] array) {
    int start = 0;
    int end = array.length - 1;
    while (start < end) {
        // 交换两端元素
        int temp = array[start];
        array[start] = array[end];
        array[end] = temp;
        start++;
        end--;
    }
}

优点： - 易于理解和实现。 - 空间复杂度低（$O(1)$），因为只需要一个额外的临时变量用于交换。

缺点： - 迭代方法在代码层面上较为直观，但在大数组处理上可能相对递归方法更缺乏灵活性。

-递归

递归方法通过函数自调用实现数组两端元素的交换，逐步减少问题规模直到所有元素都被反转。递归方法在逻辑上更简洁，尤其适用于函数式编程语言。

实现代码：

public void reverseArrayRecursively(int[] array, int start, int end) {
    if (start >= end) {
        return;
    }
    // 交换两端元素
    int temp = array[start];
    array[start] = array[end];
    array[end] = temp;
    // 递归调用
    reverseArrayRecursively(array, start + 1, end - 1);
}

优点：

• 代码更加简洁，逻辑清晰。
• 易于实现嵌套结构的处理，比如多维数组的反转。

缺点：

• 空间复杂度较高（O(n)），因为每一次递归调用都会增加调用栈的深度。
• 在没有尾递归优化的编程环境中，递归方法可能导致栈溢出。

总结

• 适用性：如果问题规模较小或对性能要求不高，递归方法是一个优雅的解决方案。但在性能关键的应用中，或者数组非常大时，迭代方法更为合适。
• 选择考量：考虑到递归可能导致的栈溢出问题，迭代方法通常在工业级应用中更受欢迎。递归方法则更适合理论研究或者教学演示。
• 优化：对于递归方法，可以考虑是否可以转化为尾递归来减少空间复杂度，提升性能。