Java 数据结构 - 递归

某些计算机编程语言允许模块或函数调用自身。这种技术称为递归。在递归中，函数α要么直接调用自身，要么调用一个函数β，而该函数β又反过来调用原始函数α。函数α称为递归函数。

int sampleMethod(int value) {
   if(value < 1) {
      return;
   }
   sampleMethod(value - 1);
   System.out.println(value);   
}

属性

递归函数可能会像循环一样无限运行。为了避免递归函数无限运行，递归函数必须具有以下两个属性：

• 基本条件 - 必须至少有一个基本条件，当满足此条件时，函数停止递归调用自身。

• 渐进方法 - 递归调用应该以这样的方式进行，即每次进行递归调用时，它都更接近基本条件。

实现

许多编程语言通过堆栈来实现递归。通常，每当一个函数（调用者）调用另一个函数（被调用者）或自身作为被调用者时，调用者函数将执行控制转移给被调用者。此转移过程可能还涉及将一些数据从调用者传递给被调用者。

这意味着，调用者函数必须暂时暂停其执行，并在执行控制从被调用者函数返回时恢复。在此，调用者函数需要从其暂停执行的点开始精确执行。它还需要它正在处理的完全相同的数据值。为此，将为调用者函数创建一个激活记录（或堆栈帧）。

此激活记录保存有关局部变量、形式参数、返回地址以及传递给调用者函数的所有信息。

递归分析

有人可能会质疑为什么要使用递归，因为可以使用迭代来完成相同的任务。第一个原因是，递归使程序更易于阅读，并且由于最新的增强型 CPU 系统，递归比迭代更高效。

时间复杂度

在迭代的情况下，我们采用迭代次数来计算时间复杂度。同样，在递归的情况下，假设所有内容都是恒定的，我们试图找出进行递归调用的次数。对函数的调用为 Ο(1)，因此进行 (n) 次递归调用使得递归函数为 Ο(n)。

空间复杂度

空间复杂度计算的是模块执行需要多少额外空间。在迭代的情况下，编译器几乎不需要任何额外空间。编译器不断更新迭代中使用的变量的值。但在递归的情况下，系统需要在每次进行递归调用时存储激活记录。因此，认为递归函数的空间复杂度可能高于使用迭代的函数。