Java递归编程

在Java中，调用自身的方法称为递归方法。这个过程被称为递归。

一个物理世界的例子是将两个平行的镜子相对放置。它们之间的任何对象都将被递归地反射。

递归是如何工作的？

在上面的示例中，我们从main方法内部调用了recurse（）方法。（普通方法调用）。在recurse（）方法中，我们再次调用相同的recurse方法。这是一个递归调用。

为了停止递归调用，我们需要在方法内部提供一些条件。否则，方法将被无限调用。

因此，我们使用if…else语句（或类似方法）来终止方法内部的递归调用。

示例：使用递归对一个数进行阶乘

class Factorial {

    static int factorial( int n ) {
        if (n != 0)  // termination condition
            return n * factorial(n-1); // recursive call
        else
            return 1;
    }

    public static void main(String[] args) {
        int number = 4, result;
        result = factorial(number);
        System.out.println(number + " factorial = " + result);
    }
}

输出：

4 factorial = 24

在上面的示例中，我们有一个名为factorial（）的方法。factorial（）是从main（）方法调用的。将数字变量作为参数传递。

注意这个声明，

return n * factorial(n-1);

factorial（）方法正在调用自身。最初，在factorial（）中n的值是4。在下一个递归调用期间，3传递给factorial（）方法。这个过程一直持续到n等于0。

当n等于0时，if语句返回false，因此返回1。最后，将累积的结果传递给main（）方法。

阶乘程序的工作原理

下面的图像将使您更好地了解factorial程序是如何使用递归执行的。

递归的优缺点

当进行递归调用时，将在堆栈上为变量分配新的存储位置。由于每次递归调用都会返回，旧的变量和参数将从堆栈中移除。因此，递归通常使用更多的内存，并且通常速度较慢。

另一方面，递归解决方案要简单得多，编写、调试和维护所需的时间更少。

尾部递归编程

尾部递归函数只是一个函数，它的最后一个操作是对自身的调用。尾部调用优化（Tail Call optimization，TCO）允许我们将常规递归调用转换为尾部调用，从而使递归对于大型输入变得实用，这在正常递归场景中早期会导致堆栈溢出错误。

使用Scala，生成尾部递归函数很容易。Scala编译器检测尾部递归，并在用新值更新函数参数后用跳回函数开头来替换它。

Java在编译器级别不直接支持TCO，但是随着Java8中引入了lambda表达式和函数接口，我们可以用几行代码实现这个概念。

尾部递归代码示例：

我们将在新的递归版本中使用这两个方法来计算factorial，factorialRec（）方法。

public class Factorial{
    public static TailCall factorialTailRec(final int factorial, final int number) {
        if (number == 1)
            return TailCalls.done(factorial);
        else
            return call(() -> factorialTailRec(factorial * number, number - 1));
    }
}

当我们调用factoriatalrec（）方法时，它会立即返回TailCall的实例。这里的关键思想是，如果我们调用done（）方法，则发出递归终止的信号。另一方面，如果我们要执行call（）方法，我们将要求递归继续，但必须在我们从当前堆栈级别退出之后。

让我们看看TailCall接口

@FunctionalInterface
public interface TailCall {
    TailCall apply();
    default boolean isComplete() {
        return false;
    }
    default T result() {
        throw new Error("not implemented");
    }
    default T invoke() {
        return Stream.iterate(this, TailCall::apply)
                .filter(TailCall::isComplete)
                .findFirst()
                .get()
                .result();
    }
}

isComplete（）方法只返回一个假值。它与apply（）方法协作，该方法将返回下一个等待执行的TailCall实例。invoke（）必须反复迭代挂起的TailCall递归，直到到达递归的末尾。然后，它必须返回最终结果（在终端TailCall实例的result（）方法中可用）。为了创建挂起的TailCall实例的延迟列表，我们使用Stream接口的iterate（）静态方法。该方法采用初始种子值和生成器。为了让生成器返回下一个挂起的TailCall实例，它可以使用当前TailCall的apply（）方法。

让我们来感受下尾部调用的便利吧

public class TailCalls {
    public static  TailCall call(final TailCall nextCall) {
        return nextCall;
    }

    public static  TailCall done(final T value) {
        return new TailCall() {
            @Override
            public boolean isComplete() {
                return true;
            }

            @Override
            public T result() {
                return value;
            }

            @Override
            public TailCall apply() {
                throw new Error("not implemented");
            }
        };
    }
}

在这个类中，我们实现了两个静态方法，call（）和done（）。call（）方法只接收TailCall实例并将其传递。

在done（）方法中，我们返回TailCall的专用版本，以指示递归的终止。在这个方法中，我们将接收到的值包装到专用实例的重写result（）方法中。专用版本的isComplete（）将通过返回真值来报告递归的结束。最后，apply（）方法抛出一个异常，因为在TailCall的这个终端实现上永远不会调用这个方法，TailCall发出递归结束的信号。

让我们运行代码

System.out.println(Factorial.factorialTailRec(1, 20).invoke());

我们用初始阶乘值1和数字20为factorialRec（）设定种子。这个调用的结果是一个TailCall实例，我们对它调用invoke（）方法。

有了尾部调用优化技术，我们可以大胆地实现递归解决方案，只需稍微重新设计就可以将其转换为尾部调用。