递归算法/斐波那契数列

图片来源网络，侵权联系可删。

一百减一是零

1704人浏览 · 2024-04-25 17:04:59

一百减一是零 · 2024-04-25 17:04:59 发布

图片来源网络，侵权联系可删

递归

递归（Recursion）是一种编程技术，其中函数或方法直接或间接地调用自身。递归通常用于解决可以分解为更小、更简单的子问题的问题。递归的基本思想是将大问题分解为小问题，然后解决小问题，最后通过组合小问题的解来得到大问题的解。

递归有两种主要的形式：直接递归和间接递归。

直接递归

直接递归：函数直接调用自身。

/**
 * 计算阶乘
 */
public class Factorial {

    /**
     * 递归实现阶乘
     *
     * @param n
     * @return
     */
    public static int factorial(int n) {
        if (n == 0) {
            return 1;
        } else {
            return n * factorial(n - 1);
        }
    }

    /**
     * 普通实现
     *
     * @param n
     * @return
     */
    public static int factorialTwo(int n) {
        if (n == 0) {
            return 1;
        }
        int ret = 1;
        for (int j = n; j >= 1; j--) {
            ret *= j;
        }
        return ret;
    }

    public static void main(String[] args) {
        System.out.println(factorial(5));  // 输出: 120
        System.out.println(factorialTwo(5));  // 输出: 120
    }
}

间接递归

public class IndirectRecursionFactorial {
  
    // 主函数，用于计算阶乘  
    public static long factorial(int n) {  
        if (n < 0) {  
            throw new IllegalArgumentException("Factorial is not defined for negative numbers.");  
        } else if (n == 0 || n == 1) {  
            return 1;  
        } else {  
            // 调用辅助函数来计算阶乘  
            return factorialHelper(n, 1);  
        }  
    }  
  
    // 辅助函数，用于递归计算阶乘  
    private static long factorialHelper(int n, long result) {  
        if (n == 1) {  
            return result;  
        } else {  
            // 递归调用自身，将n减1，并将当前数与之前的结果相乘  
            return factorialHelper(n - 1, n * result);  
        }  
    }  
  
    public static void main(String[] args) {  
        // 测试代码，计算5的阶乘  
        long factorialOf5 = factorial(5);  
        System.out.println(factorialOf5);  
    }  
}

注：间接递归更是可以作为记忆化（也称为动态规划）来更优秀的实现很多，在辅助函数中处理记录已经计算过的数值，用于下次递归不需要再进行代码逻辑处理

思想沿用

有没有发现很多算法思想都是沿用的递归。递归思想的核心是将一个大问题或复杂任务分解为若干个小问题或子任务，然后逐个解决这些小问题或子任务，最终将它们的解决方案组合起来，得到原问题的解。这种分解和组合的过程通常通过函数或方法自身的调用来实现，即方法或函数直接或间接地调用自身。递归思想在很多算法和数据结构中都有应用，例如树的遍历、图的搜索等。

排序和搜索算法：递归常用于实现排序和搜索算法。例如，快速排序和归并排序都是基于递归的排序算法。它们通过将问题分解为更小的问题来排序数据，然后再将结果合并起来。此外，二分搜索也使用了递归思想。
树的遍历：在数据结构如树和图的遍历中，递归是一种非常自然和有效的解决方案。例如，二叉树的前序、中序和后序遍历，以及图的深度优先搜索（DFS）和广度优先搜索（BFS，尽管BFS通常使用队列实现而非递归）都可以使用递归来实现。
分治算法：分治算法是一种典型的递归思想的应用，它将一个大问题划分为若干个相对独立的子问题，递归地解决这些子问题，然后将子问题的解合并起来，得到原问题的解。除了快速排序和归并排序，其他如棋盘覆盖问题、旅行商问题等也可以通过分治算法和递归来解决。
动态规划：动态规划问题通常也可以使用递归来表达其状态转移方程。然而，为了避免重复计算，通常会结合记忆化搜索或迭代的方式来优化递归解法。递归为动态规划提供了一种自然的建模方式。
数学归纳法：递归与数学归纳法的思想密切相关。当问题的解决方案基于其更小规模的情况时，递归是一种自然的选择。例如，斐波那契数列和阶乘问题都可以通过数学归纳法建模，并用递归解决。
游戏开发和计算机图形学：在游戏开发和计算机图形学领域，递归也常用于解决一些复杂的路径查找和图形渲染问题。例如，迷宫寻路算法就经常采用递归实现。
表达式求值：在编译器和解释器设计中，递归常用于解析和求值复杂的数学表达式或编程语言的语法结构。

注：虽然递归思想在许多情况下都很有用，但它也可能导致性能问题，特别是当递归深度很大时，可能会导致栈溢出。

斐波那契数列

既然说到了递归，必然想到了斐波那契数列，斐波那契数列是一个经典的递归问题，其定义本身就是递归的：每个数字是前两个数字的和。

斐波那契数列是这样定义的：

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2)，对于所有n > 1

这个定义中的 F(n) = F(n-1) + F(n-2) 是一个递归公式，它表示第 n 个斐波那契数是通过前两个斐波那契数计算得到的。这种自我引用的特性正是递归的核心。

使用递归方法来实现斐波那契数列是非常直观的。

/**
 * 斐波那契
 * 斐波那契数列（Fibonacci sequence），又称黄金分割数列，是由意大利数学家列昂纳多·斐波那契提出的。
 * 这个数列从第三项开始，每一项都等于前两项之和。具体数值为：1、1、2、3、5、8、13、21、34……以此类推。
 *
 * 在数学上，斐波那契数列可以用递推的方式定义：F(1)=1，F(2)=1，F(n)=F(n - 1)+F(n - 2)（n ≥ 3，n ∈ N*）。
 * 这意味着第三项是前两项的和，第四项是第三项和第二项的和，以此类推。
 */
public class MutualRecursion {
    public static int fibonacciA(int n) {  
        if (n <= 1) {  
            return n; // 基本情况，终止条件  
        } else {  
            return fibonacciB(n - 1) + fibonacciB(n - 2); // 调用funcB  
        }  
    }  
  
    public static int fibonacciB(int n) {  
        if (n <= 1) {  
            return n; // 基本情况，终止条件  
        } else {  
            return fibonacciA(n - 1) + fibonacciA(n - 2); // 调用funcA  
        }  
    }  
  
    public static void main(String[] args) {  
        System.out.println(fibonacciA(8)); // 输出斐波那契数列的第5项
    }

这种直接的递归实现方式在计算较大的斐波那契数时效率非常低，因为它会重复计算很多相同的子问题。例如，为了计算 F(5)，它会计算 F(4) 和 F(3)，而计算 F(4) 时又会计算 F(3) 和 F(2)，这样就重复计算了 F(3)。这种重复计算随着 n 的增大而急剧增加，导致算法的时间复杂度呈指数级增长。

为了提高效率，我们可以使用记忆化（也称为动态规划）或迭代方法来避免重复计算。记忆化是通过将已经计算过的子问题的结果存储起来，在需要时直接查找而不是重新计算。迭代方法则是通过循环来逐步计算斐波那契数列的每一项，而不是使用递归调用。

总之，递归是计算斐波那契数列的一种直观方法，但需要注意其效率问题。在实际应用中，我们通常会选择更高效的算法来计算斐波那契数列。