最全面的递归算法详解，一篇足矣（高手必备）

最全面的递归算法详解，一篇足矣（高手必备）

引用

CSDN

1.

https://blog.csdn.net/Broken_x/article/details/142143544

递归是编程中一种强大的技术，允许函数在其定义中调用自身。理解递归的特点和应用场景，对于编写高效、可读的代码至关重要。本文将从递归的基本概念、优缺点、具体实现、与循环的比较、多路递归的优化方法以及爆栈问题的解决方案等多个维度，全面解析递归算法。

什么是递归？

递归是一种强大的编程技术，允许函数在其定义中调用自身。递归通常涉及两个主要部分：

1. 基本情况：这是递归的终止条件，当满足此条件时，函数将不再调用自身。
2. 递归情况：这是函数调用自身的部分，通常会将问题规模缩小。

如何写出递归？

只需要做到下面两点
1.终止条件；
2.一般规律，也就是需要重复执行循环的部分。

递归的优点

• 简洁性：递归可以使代码更加简洁，尤其是在处理复杂数据结构（如树和图）时。
• 可读性：递归代码通常比迭代代码更易于理解，因为它直接反映了问题的定义。
• 解决复杂问题：许多算法（如排序和搜索）可以通过递归轻松实现。

递归的缺点

• 性能问题：递归可能导致大量的函数调用，消耗更多的内存和时间，特别是在没有优化的情况下。
• 栈溢出：深度递归可能导致栈溢出错误，因为每次函数调用都会占用栈空间。

Java中的递归实现

以下是一些简单的递归示例，展示了如何在Java中实现递归算法。

1. 计算阶乘

public static int factorial(int n) {
    if (n == 1) {
        return 1;
    } else {
        return n * factorial(n - 1);
    }
}

2. 斐波那契数列

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

3. 反向打印字符串

public static void reversePrint(String str) {
    if (str.length() == 0) {
        return;
    }
    reversePrint(str.substring(1));
    System.out.print(str.charAt(0));
}

4.1递归二分查找

//递归二分查找
public static int binarySearch(int[] arr,int i, int j,int target) {
    int m = (i+j) >> 1;
    if (i > j)
        return -1;
    if (arr[m] < target)
         return binarySearch(arr, m+1, j, target);
    else if (arr[m] > target)
         return binarySearch(arr, i, m-1, target);
    else
         return m;
}

4.2普通二分查找

如果想了解二分查找的可以去我的这一篇，传送门

public static int binarySearchIterative(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;
    while (left <= right) { // 终止条件
        int mid = left + (right - left) / 2; // 一般规律
        if (arr[mid] == target) {
            return mid; // 找到目标值
        } else if (arr[mid] < target) {
            left = mid + 1; // 在右半部分查找
        } else {
            right = mid - 1; // 在左半部分查找
        }
    }
    return -1; // 目标值未找到
}

5.1递归冒泡排序

//递归冒泡排序
public static void bubbleSort(int[] arr,int j) {
    if (j == 0) //j代表未排序区域的右边界
        return;
    int x = 0; //x代表最后一次交换的位置,可以认为是已排序区域和未排序区域的分界线
    for (int i = 0; i < j; i++) {
        if (arr[i] > arr[i+1]) {
            int temp = arr[i];
            arr[i] = arr[i+1];
            arr[i+1] = temp;
            x = i;
        }
    }
    bubbleSort(arr, x);
}

递归冒泡排序引入变量 x 的好处主要体现在以下几个方面：

1. 减少不必要的遍历：

• 在传统的冒泡排序中，每一轮遍历都会将最大的元素“冒泡”到未排序区域的末尾。然而，在某些情况下，未排序区域的前面部分可能已经是有序的。引入 x 变量后， x 记录了最后一次交换的位置，这意味着从 x 之后的元素已经是有序的。因此，下一轮递归只需要处理到 x 位置，而不需要再遍历整个未排序区域，从而减少了不必要的比较和交换操作。

2. 提高效率：

• 通过减少每一轮的遍历范围，递归冒泡排序的效率得到了提升。特别是在数组接近有序的情况下，这种优化尤为明显。

3. 简化代码逻辑：

• 引入 x 变量后，代码逻辑更加清晰。 x 作为已排序区域和未排序区域的分界线，使得递归调用的参数更加明确，便于理解和维护。
  总结来说，引入 x 变量使得递归冒泡排序在处理接近有序的数组时更加高效，减少了不必要的操作，提高了算法的性能。

5.2普通循环冒泡排序

public static void bubbleSortIterative(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

递归与循环的比较

多路递归

以斐波那契数列为例，让我们来了解一下什么是多路递归。斐波那契数列是一个经典的递归问题，定义如下：

• F(0) = 0
• F(1) = 1
• F(n) = F(n-1) + F(n-2) 对于 n >= 2

单路递归

单路递归是指函数在其定义中仅调用自身一次。换句话说，函数的递归调用只有一个分支。例如，计算阶乘的递归实现就是单路递归：

public static int factorial(int n) {
    if (n == 0 || n == 1) return 1; // 终止条件
    return n * factorial(n - 1); // 单路递归调用
}

多路递归

多路递归是指一个函数在递归调用时，同时调用多个子问题。在斐波那契数列的例子中， fibonacci(n) 同时调用了 fibonacci(n - 1) 和 fibonacci(n - 2)，这两个调用是并行的，即它们是同时进行的。

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

多路递归的特点

1. 并行调用：

• 在多路递归中，函数会同时调用多个子问题，这些子问题是并行进行的。

2. 重复计算：

• 由于多个子问题可能会重复计算相同的子问题，多路递归可能会导致大量的重复计算，效率较低。例如，在计算 fibonacci(5) 时， fibonacci(3) 会被计算多次。

3. 空间复杂度：

• 多路递归的空间复杂度较高，因为每次递归调用都会在调用栈中占用一定的空间。

可以看到，我们计算了f(5)时已经把f(4),f(3),f(2),f(1)计算过一遍了，而我们计算f(4)时又要重新计算，这就多了许多重复的执行步骤，我们可以考虑优化一下 。

优化多路递归

为了优化多路递归，可以使用记忆化技术（Memoization）或动态规划（Dynamic Programming）来避免重复计算。例如：

public static int fibonacci(int n, int[] memo) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    if (memo[n] != 0) return memo[n];
    memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
    return memo[n];
}

在这个优化版本中，我们使用了一个数组 memo 来存储已经计算过的斐波那契数，从而避免了重复计算，提高了效率。所谓记忆化就是，我们可以用一个数组来储存已经计算过的值，再次用到的时候直接拿出用即可，与没有优化前的进行对比，可以看得出分支明显减少了许多，大大提高了效率。

总结

多路递归是指一个函数在递归调用时，同时调用多个子问题。在斐波那契数列的例子中， fibonacci(n) 同时调用了 fibonacci(n - 1) 和 fibonacci(n - 2)，这种并行调用的方式就是多路递归。多路递归可能会导致重复计算和较高的空间复杂度，但可以通过记忆化或动态规划来优化。

递归-爆栈问题

递归中的爆栈问题（Stack Overflow）是指在递归调用过程中，由于递归深度过大，导致调用栈（Call Stack）空间耗尽，从而引发程序崩溃或异常。

调用栈的作用

调用栈是计算机程序在执行过程中用于管理函数调用的一种数据结构。每当一个函数被调用时，系统会在调用栈中为该函数分配一块内存空间，用于存储函数的局部变量、返回地址等信息。当函数执行完毕后，这块内存空间会被释放。

递归调用的特点

在递归调用中，函数会不断地调用自身，每次调用都会在调用栈中分配一块新的内存空间。如果递归深度过大，调用栈中的内存空间会不断累积，最终可能导致调用栈空间耗尽，引发爆栈问题。

爆栈问题的示例

以计算阶乘为例：

public static int factorial(int n) {
    if (n == 0) return 1;
    return n * factorial(n - 1);
}

在这个递归函数中， factorial(n) 会调用 factorial(n - 1)， factorial(n - 1) 会调用 factorial(n - 2)，依此类推，直到 n 减到 0。如果 n 非常大，递归深度会非常深，调用栈的空间会迅速累积，最终可能导致爆栈问题。

可以看到数字过大时，递归调用过深，内存空间不够，会爆出异常，这就是爆栈。

爆栈问题优化-尾递归

尾递归优化（Tail Recursion Optimization）是一种针对递归函数的优化技术，它通过将递归调用转换为迭代形式，从而避免在调用栈中累积大量的内存空间，避免爆栈问题。

尾递归的特点

尾递归是指递归调用是函数的最后一个操作。换句话说，递归调用返回的结果直接作为函数的返回值，不再进行任何其他操作。

尾递归优化的原理

尾递归优化的原理是通过编译器或解释器的优化，将尾递归函数转换为一个循环结构，从而避免在调用栈中累积大量的内存空间。

尾递归优化的示例

以计算阶乘为例，传统的递归实现如下：

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

在这个实现中， factorial(n, result) 调用 factorial(n - 1, n * result) 后，直接返回递归调用的结果，不再进行其他操作，因此这是尾递归。

尾递归优化的效果

尾递归优化可以显著减少调用栈的使用，避免爆栈问题。具体效果如下：

1. 减少调用栈空间：

• 由于尾递归调用是函数的最后一个操作，编译器或解释器可以将递归调用转换为迭代形式，从而避免在调用栈中累积大量的内存空间。

2. 提高性能：

• 尾递归优化可以减少函数调用的开销，提高程序的执行效率。

3. 避免爆栈问题：

• 尾递归优化可以有效避免递归深度过大导致的爆栈问题，提高程序的稳定性和可靠性。

支持尾递归优化的语言

并非所有编程语言都支持尾递归优化，很遗憾的是Java并不支持尾递归优化哈，以下是一些支持尾递归优化的编程语言：

• Scheme：Scheme 语言规范要求实现必须支持尾递归优化。
• Haskell：Haskell 通过惰性求值和尾递归优化来避免爆栈问题。
• Scala：Scala 编译器支持尾递归优化。
• Erlang：Erlang 虚拟机（BEAM）支持尾递归优化。
• C++：C++ 编译器通常支持尾递归优化，但这取决于具体的编译器和编译选项。尾递归优化通常是通过编译器的优化选项来实现的。

总结

爆栈问题就是由于递归调用深度过高，导致调用栈的内存空间不够用，从而引发的程序崩溃或异常。解决爆栈问题的方法包括尾递归优化、迭代替代递归和限制递归深度等。通过这些方法，可以有效避免递归中的爆栈问题，提高程序的稳定性和性能。