函数或方法调用自身的过程称为递归。递归是 Java 中的突出主题之一。在本教程中，我们将讨论 Java 中不同类型的递归。
递归类型
递归主要有两种类型：
1）直接递归
直接递归意味着方法直接调用自身。直接递归可以进一步分为五个部分：
a) 尾递归：在尾递归中，函数调用自身，负责递归的语句是方法的最后一条语句。也就是说，在递归语句之后，不能再写任何语句。如果递归函数正在调用自身，并且该递归调用是函数中的最后一个语句，则称为尾递归。该函数在调用时必须执行或处理任何操作，并且在返回时不执行任何操作。
// 演示尾递归的 Java 程序 ；
public class TailRecursion
{
// 递归函数 ；
static void functn(int y)
{
if (y > 0)
{
System.out.println("The value is " + y);
// 实现递归 ；
// 它是方法的最后一句；
functn(y - 1);
}
}
// main method
public static void main(String[] argvs)
{
int y = 4;
functn(y);
}
}
输出：
The value is 4
The value is 3
The value is 2
The value is 1
|
复杂性分析：程序的时间复杂度为 O(n)。这是因为负责递归的语句运行了 n 次。程序的空间复杂度为 O(n)。
使用循环
让我们看看使用循环做同样的事情会发生什么。
// Java program that demonstrates tail recursion
public class TailRecursion1
{
// function that uses iteration
static void functn(int y)
{
for(; y > 0; y--)
{
System.out.println("The value is " + y);
}
}
// main method
public static void main(String[] argvs)
{
int y = 4;
functn(y);
}
}
|
输出：
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) 头递归：在头部递归中，负责递归的语句是函数的第一条语句。换句话说，任何有关操作的语句都不应出现在负责递归的语句之前。
// Java program that demonstrates head recursion
public class HeadRecursion
{
// Recursion function
static void functn(int y)
{
if (y > 0)
{
// 实现递归 ；
// 它是方法的第一句；
functn(y - 1);
System.out.println("The value is " + y);
}
}
// main method
public static void main(String[] argvs)
{
int y = 4;
functn(y);
}
}
输出：
The value is 1
The value is 2
The value is 3
The value is 4
|
复杂性分析：程序的时间复杂度为 O(n)，程序的空间复杂度也是 O(n)。
c) 线性递归：当一个函数调用自身，但只调用一次时，称为线性递归。观察它的伪代码。
funtn(t)
{
// some code can be written here
if(t > 0)
{
fun(t - 1); // the function is calling itself only single time
}
// some code can be written here
}
|
在头部递归和尾部递归中讨论过的程序也是线性递归的例子。
d) 树递归：当一个函数不止一次调用自身时，就称为树递归。请看下面的例子。
// Java program that demonstrates tree recursion
public class TreeRecursion
{
// Recursion function
static void functn(int y)
{
if (y > 0)
{
System.out.println("The value is " + y);
functn(y - 1); // 函数首次调用自身 ；
functn(y - 1); // 函数第二次调用自身
}
}
// main method
public static void main(String[] argvs)
{
int y = 4;
functn(y);
}
}
|
输出：
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(2n)，空间复杂度也是 O(2n)。时间和空间复杂度都是指数级的，因为一次递归调用会导致两次单独的递归调用。
e) 嵌套递归：在这种递归中，函数会调用自身，负责递归的语句是嵌套的，这意味着在递归调用的参数内部有一个递归调用。换句话说，就是 "递归内部有递归"。下面的示例将使这一概念更加清晰。
// Java program that demonstrates tree recursion
public class NestedRecursion
{
// Recursion function
static int functn(int y)
{
// the base case
if(y == 0)
{
return 0;
}
System.out.println("The value is " + y);
// 递归调用内的递归调用 ；
return functn(functn(y - 1));
}
// main method
public static void main(String[] argvs)
{
int y = 4;
int a = functn(y);
}
}
|
输出：
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()。让我们看看它的实现。
// Java program that demonstrates indirect recursion
public class IndirectRecursion
{
// Recursion function
static void funA(int y)
{
if (y > 0)
{
System.out.println("In function A, the value is " + y);
// invoking function funB()
funB(y - 1);
}
}
// Recursion function
static void funB(int y)
{
if (y > 0)
{
System.out.println("In function B, the value is " + y);
// invoking function funC()
funC(y - 1);
}
}
// Recursion function
static void funC(int y)
{
if (y > 0)
{
System.out.println("In function C, the value is " + y);
// invoking function funA()
funA(y - 1);
}
}
// main method
public static void main(String[] argvs)
{
int y = 10;
funA(y);
}
}
|
输出：
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)。