Java 中什么是递归？如何使用递归？

矫情吗；* 2024-03-22 16:46 63阅读 0赞

Java 中什么是递归？如何使用递归？

递归是一种常用的算法，在Java中也得到了广泛的应用。递归是指一个方法调用自身的过程，递归可以使代码更加简洁、易于理解，但同时也要注意递归深度过大可能会导致栈溢出等问题。本文将介绍Java中的递归是什么，如何使用递归。

![在这里插入图片描述][a48f04a657dd447eb92b04be92ed4073.png]

### 什么是递归？ ###

递归是指一个方法调用自身的过程，通常递归函数有两个部分：基本情况和递归情况。基本情况是递归函数可以直接返回结果的情况，递归情况是递归函数需要调用自身的情况。递归函数通过不断地调用自身，将问题分解成更小的子问题，并最终解决问题。

递归分为直接递归和间接递归。直接递归是指递归函数直接调用自身，间接递归是指递归函数通过调用其他函数间接调用自身。递归需要避免死循环，即递归函数没有基本情况或者基本情况不满足的情况下，会不断地递归调用自身，导致程序无法正常结束。

### 如何使用递归？ ###

在Java中，递归可以用于解决一些问题，例如计算阶乘、斐波那契数列、二叉树的遍历等等。下面将介绍如何使用递归来计算阶乘、斐波那契数列、二叉树的遍历。

#### 计算阶乘 ####

计算n的阶乘可以使用递归来实现，代码如下：

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

在递归情况中，将问题分解成n-1的阶乘，递归调用factorial函数。

#### 斐波那契数列 ####

斐波那契数列是指每个数字都是前两个数字之和的数列，例如0、1、1、2、3、5、8、13、21、34等等。斐波那契数列可以使用递归来实现，代码如下：

public static int fibonacci(int n) {
        if (n == 0) { // 基本情况
            return 0;
        } else if (n == 1) { // 基本情况
            return 1;
        } else { // 递归情况
            return fibonacci(n - 1) + fibonacci(n - 2);
        }
    }

在递归情况中，将问题分解成n-1和n-2的斐波那契数列，递归调用fibonacci函数。

#### 二叉树遍历 ####

二叉树是一种常见的数据结构，在Java中可以使用递归来遍历二叉树。二叉树的遍历分为前序遍历、中序遍历和后序遍历。前序遍历是指先遍历根节点，然后遍历左子树，最后遍历右子树；中序遍历是指先遍历左子树，然后遍历根节点，最后遍历右子树；后序遍历是指先遍历左子树，然后遍历右子树，最后遍历根节点。代码如下：

public void preOrder(TreeNode root) {
        if (root != null) {
            System.out.print(root.val + " "); // 先输出根节点
            preOrder(root.left); // 遍历左子树
            preOrder(root.right); // 遍历右子树
        }
    }
    
    public void inOrder(TreeNode root) {
        if (root != null) {
            inOrder(root.left); // 遍历左子树
            System.out.print(root.val + " "); // 输出根节点
            inOrder(root.right); // 遍历右子树
        }
    }
    
    public void postOrder(TreeNode root) {
        if (root != null) {
            postOrder(root.left); // 遍历左子树
            postOrder(root.right); // 遍历右子树
            System.out.print(root.val + " "); // 输出根节点
        }
    }

### 总结 ###

递归是一种常用的算法，在Java中也得到了广泛的应用。递归是指一个方法调用自身的过程，递归函数通过不断地调用自身，将问题分解成更小的子问题，并最终解决问题。递归可以用于解决一些问题，例如计算阶乘、斐波那契数列、二叉树的遍历等等。在使用递归时需要注意递归深度过大可能会导致栈溢出等问题。

[a48f04a657dd447eb92b04be92ed4073.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/ffe864010eb34db98bddce81e5099a76.png