4年前 (2020-10-02)  Java系列 |   抢沙发  781 
文章评分 0 次,平均分 0.0

在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程序是如何使用递归执行的。

Java递归编程

递归的优缺点

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

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

尾部递归编程

尾部递归函数只是一个函数,它的最后一个操作是对自身的调用。尾部调用优化(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()方法。

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

 

除特别注明外,本站所有文章均为老K的Java博客原创,转载请注明出处来自https://javakk.com/512.html

关于

发表评论

表情 格式

暂无评论

登录

忘记密码 ?

切换登录

注册