Java 中不同类型的递归

一个函数或方法调用自身的进程称为递归。递归是 Java 中的一个重要主题。在本教程中，我们将讨论 Java 中不同类型的递归。

递归类型

递归主要有两种类型

1) 直接递归

直接递归意味着方法直接调用自身。直接递归可以进一步分为五个部分

a) 尾递归： 在尾递归中，函数调用自身，而负责递归的语句是方法的最后一条语句。换句话说，在递归语句之后，不应该有任何语句。如果递归函数调用自身，并且该递归调用是函数中的最后一条语句，那么它被称为尾递归。函数在调用时必须执行或处理任何操作，而在返回时则不执行任何操作。

文件名： TailRecursion.java

输出

The value is 4
The value is 3
The value is 2
The value is 1

复杂度分析： 程序的时间复杂度为 O(n)。这是因为负责递归的语句运行了 n 次。程序的空间复杂度为 O(n)。

让我们看看使用循环做同样的事情会发生什么。

文件名： TailRecursion1.java

输出

The value is 4
The value is 3
The value is 2
The value is 1

复杂度分析： 程序的时间复杂度为 O(n)。这是因为循环运行了 n 次。程序的空间复杂度为 O(1)。

从这两段程序可以看出，迭代（使用循环）的性能优于递归，因为迭代占用的空间更少。让我们探讨一下原因。

在循环的情况下，当函数“(void functn(int y))”执行时，在堆栈中只维护一个激活记录（变量“y”的激活记录）。因此，在堆栈中只创建了一个单位的内存，使得程序的空间复杂度为 O(1)。相比之下，在递归的情况下，每次函数调用自身时都会创建一个单独的激活记录，使得程序的空间复杂度为 O(n)，前提是递归持续 n 次。

b) 头递归： 在头递归中，负责递归的语句是函数的第一条语句。换句话说，在负责递归的语句之前不应有任何操作语句。

文件名： HeadRecursion.java

输出

The value is 1
The value is 2
The value is 3
The value is 4

复杂度分析： 程序的时间复杂度为 O(n)，空间复杂度也为 O(n)。

c) 线性递归： 当一个函数只调用自身一次时，就称为线性递归。观察其伪代码。

在头递归和尾递归中讨论的程序也是线性递归的示例。

d) 树递归： 当一个函数调用自身多次时，就称为树递归。观察以下示例。

文件名： TreeRecursion.java

输出

The value is 4
The value is 3
The value is 2
The value is 1
The value is 1
The value is 2
The value is 1
The value is 1
The value is 3
The value is 2
The value is 1
The value is 1
The value is 2
The value is 1
The value is 1

复杂度分析： 程序的时间复杂度为 O(2ⁿ)，空间复杂度也为 O(2ⁿ)。时间和空间复杂度呈指数级增长，因为一次递归调用会导致两次单独的递归调用。

e) 嵌套递归： 在这种递归中，一个函数会调用自身，而负责递归的语句是嵌套的，这意味着在递归调用的参数中有一个递归调用。换句话说，“递归内部有递归”。以下示例将使概念更清晰。

文件名： NestedRecursion.java

输出

The value is 4
The value is 3
The value is 2
The value is 1

复杂度分析： 程序的时间复杂度为 O(n)，空间复杂度也为 O(n)。

2) 间接递归

假设有一个名为 funA() 的函数，该函数调用另一个名为 funB() 的函数，该函数调用另一个名为 funC() 的函数，而 funC() 函数调用 funA() 函数，则此类型的递归称为间接递归。我们看到有一系列函数 funA() 调用函数 funB()，函数 funB() 调用函数 funC()，函数 funC() 调用函数 funA()。让我们看看它的实现。

文件名： IndirectRecursion.java

输出

In function A, the value is 10
In function B, the value is 9
In function C, the value is 8
In function A, the value is 7
In function B, the value is 6
In function C, the value is 5
In function A, the value is 4
In function B, the value is 3
In function C, the value is 2
In function A, the value is 1

复杂度分析： 程序的时间复杂度为 O(n)，空间复杂度也为 O(n)。