Java中的递归

什么是递归？

函数直接或间接调用自身的过程称为递归，而相应的函数称为递归函数。使用递归算法，可以很容易地解决某些问题。此类问题的示例包括河内塔（TOH），有序/预购/后继树遍历，图的DFS等。

递归的基本条件是什么？

在递归程序中，提供了对基本情况的解决方案，并且以较小的问题表示较大的问题的解决方案。

在上面的示例中，定义了n <= 1的基本情况，并且可以通过转换为较小的数值直到达到基本情况来解决较大的数值。

如何使用递归解决特定问题？

这个想法是用一个或多个较小的问题来表示一个问题，并添加一个或多个停止递归的基本条件。例如，如果我们知道（n-1）的阶乘，就可以计算阶乘n。阶乘的基本情况为n =0。当n = 0时，我们返回1。

为什么递归会发生堆栈溢出错误？

如果未达到或未定义基本情况，则可能会出现堆栈溢出问题。让我们以一个例子来理解这一点。

如果调用fact（10），它将调用fact（9），fact（8），fact（7）等，但数量永远不会达到100。因此，没有达到基本情况。如果堆栈上的这些功能耗尽了内存，则会导致堆栈溢出错误。

直接和间接递归有什么区别？

如果函数fun调用相同的函数fun，则称为直接递归。如果fun函数调用另一个函数，例如fun_new和fun_new直接或间接调用fun，则该函数称为间接递归。表1说明了直接和间接递归之间的区别。

直接递归：

间接递归：

尾递归和非尾递归之间有什么区别？

当递归调用是该函数执行的最后一件事时，递归函数就是尾部递归。有关详细信息，请参阅尾递归文章。

如何在递归中将内存分配给不同的函数调用？

从main（）调用任何函数时，都会在堆栈上为其分配内存。递归函数调用自身，被调用函数的内存分配在分配给调用函数的内存之上，并且为每个函数调用创建不同的局部变量副本。当达到基本情况时，该函数将其值返回给调用该函数的函数，并取消分配内存，过程继续进行。

让我们以简单函数为例，说明递归的工作原理。z

从main（）调用printFun（3）时，将内存分配给printFun（3），并将局部变量test初始化为3，并将语句1至4压入堆栈，如下图所示。它首先打印“ 3”。在语句2中，调用printFun（2）并将内存分配给printFun（2），并将局部变量test初始化为2，并将语句1至4压入堆栈。同样，printFun（2）调用printFun（1），而printFun（1）调用printFun（0）。 printFun（0）转到if语句，然后返回到printFun（1）。执行剩余的printFun（1）语句，并返回到printFun（2），依此类推。在输出中，从3到1的值被打印，然后从1到3的值被打印。内存堆栈如下图所示。

与迭代编程相比，递归编程有哪些缺点？

注意，递归程序和迭代程序都具有相同的解决问题的能力，即每个递归程序都可以迭代地编写，反之亦然。递归程序比迭代程序具有更大的空间要求，因为所有功能都将保留在堆栈中，直到达到基本情况为止。由于函数调用和返回开销，它也有更多的时间要求。

递归编程比迭代编程有什么优势？

递归提供了一种干净简单的代码编写方法。有些问题本质上是递归的，例如遍历树，河内塔等。对于此类问题，最好编写递归代码。我们还可以借助堆栈数据结构来迭代地编写此类代码。例如，参见河内迭代塔的无递归有序树遍历。