【JavaSE专栏36】函数递归算法

我就是我 2023-10-13 14:33 18阅读 0赞

> **作者主页**：[Designer 小郑][Designer]  
> **作者简介**：Java全栈软件工程师一枚，来自浙江宁波，负责开发管理公司OA项目，专注软件前后端开发（Vue、SpringBoot和微信小程序）、系统定制、远程技术指导。CSDN学院、蓝桥云课认证讲师，全栈领域优质创作者。热爱技术、专注业务、开放合作、乐于分享，期待你我共同成长！  
> **主打方向**：Vue、SpringBoot、微信小程序

本文讲解了 Java 中函数递归语法和使用场景，并给出了样例代码。

#### 目录 ####

*  一、什么是递归
 *  二、递归实现斐波那契数列
 *  三 递归算法的优势和应用场景
 *  四、递归算法面试题
 *  五、总结

--------------------

## 一、什么是递归 ##

**递归是指在方法的定义中调用方法本身的过程**。

在递归中，方法会**不断地调用自身，直到满足某个条件才停止调用**。递归可以解决一些问题，特别是那些可以被分解为同样的子问题的问题。

递归的具体概念是：

1.  **递归终止条件**：递归必须包含一个终止条件，当满足这个条件时，递归停止。
2.  **递归调用**：在方法内部，通过调用自身来解决子问题。

下面是一个简单的递归方法示例，计算一个正整数的阶乘。

public class RecursionExample {
        
        public static int factorial(int n) {
        
            // 递归终止条件
            if (n == 0 || n == 1) {
        
                return 1;
            }
            // 递归调用
            return n * factorial(n - 1);
        }
    
        public static void main(String[] args) {
        
            int result = factorial(5); // 调用递归方法计算5的阶乘
            System.out.println("5的阶乘为: " + result);
        }
    }

在上述代码中，`factorial`方法是一个递归方法，用于计算一个正整数的阶乘。它通过调用自身来解决子问题，即计算  n − 1 n-1 n−1 的阶乘。当  n n n 等于  0 0 0 或  1 1 1 时，递归终止，直接返回  1 1 1。在 `main` 方法中，通过调用 `factorial(5)` 来计算  5 5 5 的阶乘，并输出结果。

> 递归的优点是可以简化问题的解决方案，使代码更加清晰、优雅。

> 然而，递归也要小心使用，因为在处理大量数据或者深度嵌套的情况下，递归可能导致堆栈溢出或者性能下降。因此，**在使用递归时，需要注意终止条件的设置和递归调用的层数控制**。

![在这里插入图片描述][b72066d58c284968a2482db96d3640aa.png_pic_center]

--------------------

## 二、递归实现斐波那契数列 ##

下面是使用递归算法实现**斐波那契数列**求解的 Java 代码示例。

public class FibonacciExample {
        
        public static int fibonacci(int n) {
        
            if (n <= 1) {
        
                return n;
            } else {
        
                return fibonacci(n - 1) + fibonacci(n - 2);
            }
        }
    
        public static void main(String[] args) {
        
            int n = 10; // 求解斐波那契数列的第n个数
            int result = fibonacci(n);
            System.out.println("斐波那契数列的第" + n + "个数是：" + result);
        }
    }

在上述代码中，`fibonacci` 方法使用递归算法来计算斐波那契数列的第  n n n 个数。当  n n n 小于等于  1 1 1 时，即为终止条件，直接返回  n n n。当  n n n 大于  1 1 1 时，递归调用 `fibonacci(n - 1) + fibonacci(n - 2)`，将问题拆分为求解第  n − 1 n-1 n−1 和  n − 2 n-2 n−2 个数的斐波那契数，然后将它们相加得到结果。

在 `main` 方法中，我们通过调用 `fibonacci(10)` 来求解斐波那契数列的第  10 10 10 个数，并将结果输出。

需要注意的是，使用递归算法解决斐波那契数列的问题时，随着  n n n 的增大，递归调用的次数会呈指数级增长，效率较低。因此，在实际应用中，可以考虑使用迭代或动态规划等其他方法来提高效率。

![在这里插入图片描述][b2e21f8e28524435a4d53408bd3c7059.png_pic_center]

--------------------

## 三 递归算法的优势和应用场景 ##

递归算法的优势和应用场景如下。

1.  **简洁性**：递归算法通常具有简洁、清晰的代码结构，能够以更直观的方式表达问题的解决思路。
2.  **问题分解**：递归算法能够将复杂的问题分解为相同或类似的子问题，使问题的解决过程更加简单和可理解。
3.  **适用于规模不确定的问题**：递归算法适用于解决规模不确定或者可变化的问题，它可以不断迭代地调用自身来处理子问题，而不需要固定参数数量。
4.  **处理树形结构或图形结构**：递归算法特别适合处理树形结构或者图形结构的问题，例如遍历树的节点、搜索图的路径等。
5.  **数学问题和算法设计**：递归算法在解决数学问题和算法设计中具有广泛的应用，例如计算阶乘、斐波那契数列、快速幂等等。
6.  **数据结构的操作**：递归算法在对一些数据结构进行操作时也经常使用，例如链表的反转、二叉树的遍历等。

需要注意的是，递归算法也存在一些局限性，例如**性能问题**（递归调用可能导致堆栈溢出）、**空间占用问题**（递归需要额外的函数调用开销）等。在实际应用中，需要根据具体问题的特点和需求来选择合适的算法和数据结构，综合考虑效率和可读性等因素。

![在这里插入图片描述][f42e340672294ff4b9a86b43f7dedc49.png_pic_center]

--------------------

## 四、递归算法面试题 ##

1.  **什么是函数递归**？

函数递归是指在函数的定义中调用函数本身的过程。通过递归调用，函数可以反复执行相同的操作，直到满足某个条件才停止递归。

1.  **函数递归的基本原理是什么？**

函数递归的基本原理是将一个大问题分解为规模较小的子问题，然后通过不断调用函数本身来解决子问题，最终得到大问题的解决方案。

1.  **函数递归需要满足哪些条件？**

函数递归需要满足以下两个条件：

*  基本情况：函数需要定义一个或多个基本情况，当满足这些情况时，递归停止，不再调用自身。
 *  递归调用：函数需要调用自身来解决规模较小的子问题，直到达到基本情况。

1.  **函数递归的优点和缺点是什么？**

*  函数递归的优点：

简洁性：递归能够用更简洁的代码实现某些复杂的问题。

可读性：递归能够将问题的解决过程直接表达，易于理解。

*  函数递归的缺点：

性能开销：递归调用会增加函数调用的开销，可能导致性能下降。

内存消耗：递归过程中可能会生成大量的中间结果，占用较多的内存空间。

1.  **可以讲一下斐波那契数列中函数递归的实现吗？**

计算斐波那契数列的第n项：

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

在上述代码中，函数 `fibonacci()` 通过递归调用自身来计算斐波那契数列的第  n n n 项。

当  n n n 小于等于  1 1 1 时，递归停止，返回  n n n。

否则，递归调用 `fibonacci(n - 1)` 和 `fibonacci(n - 2)` 来计算前两项的和。

--------------------

## 五、总结 ##

本文讲解了 Java 中函数递归语法和使用场景，并给出了样例代码。在下一篇博客中，将讲解 Java 中可变参数的知识。

![在这里插入图片描述][3a01dc60e62c415b812015851343f1c0.png_pic_center]

[Designer]: https://blog.csdn.net/qq_41464123
[b72066d58c284968a2482db96d3640aa.png_pic_center]: https://img-blog.csdnimg.cn/b72066d58c284968a2482db96d3640aa.png#pic_center
[b2e21f8e28524435a4d53408bd3c7059.png_pic_center]: https://img-blog.csdnimg.cn/b2e21f8e28524435a4d53408bd3c7059.png#pic_center
[f42e340672294ff4b9a86b43f7dedc49.png_pic_center]: https://img-blog.csdnimg.cn/f42e340672294ff4b9a86b43f7dedc49.png#pic_center
[3a01dc60e62c415b812015851343f1c0.png_pic_center]: https://img-blog.csdnimg.cn/3a01dc60e62c415b812015851343f1c0.png#pic_center