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

我们探索一个方法可以做的最神奇的事情之一:调用自身来解决同一问题的较小版本。调用自身的方法称为递归方法

递归Void方法

考虑以下示例:

public static void countdown(int n) {
    if (n == 0) {
        System.out.println("Blastoff!");
    } else {
        System.out.println(n);
        countdown(n - 1);
    }
}

方法的名称是countdown;它接受单个整数作为参数。如果参数为0,则显示单词blatoff!。否则,它将显示数字,然后调用自己,并将n-1作为参数传递。

如果我们从main调用倒计时(3),会发生什么?

倒计时的执行从n==3开始,由于n不是0,它显示值3,然后调用自己。。。

	倒计时的执行从n==2开始,由于n不是0,它显示值2,然后调用自己。。。

		倒计时的执行从n==1开始,由于n不是0,它显示值1,然后调用自己。。。

			倒计时的执行从n==0开始,由于n是0,它显示单词Blastoff!然后回来。

		得到n==1的倒计时返回。

	得到n==2的倒计时返回。

得到n==3的倒计时返回。

然后你又回来了。总输出结果如下:

3
2
1
Blastoff!

第二个例子

public static void newLine() {
    System.out.println();
}

public static void threeLine() {
    newLine();
    newLine();
    newLine();
}

虽然这些方法有效,但是如果我们想显示两个换行符,或者可能是100个换行符,它们也没有帮助。更普遍的选择是:

public static void nLines(int n) {
    if (n > 0) {
        System.out.println();
        nLines(n - 1);
    }
}

此方法以整数n作为参数,并显示n个换行符。结构类似于倒计时。只要n大于0,它就会显示一个新行,然后调用自己来显示(n−1)个额外的新行。新行的总数是1+(n-1),这正是我们想要的:n。

递归堆栈

我们使用堆栈图来表示方法调用期间程序的状态。同样的图表可以使递归方法的解释更容易。

请记住,每次调用方法时,Java都会创建一个新的框架,其中包含该方法的参数和变量。图8.1是倒计时的堆栈图,用n==3调用。

Java递归方法Recursive详解

按照惯例,main的帧在顶部,其他帧的堆栈向下增长。这样,我们就可以在纸上绘制堆栈图,而无需猜测它们将增长到什么程度。main的框架为空,因为main没有任何变量。(它有参数args,但由于我们没有使用它,所以我们将其排除在图表之外。)

倒计时有四个帧,每个帧的参数n都有不同的值。最后一帧n==0,称为基本情况。它不进行递归调用,因此它下面没有更多的帧。

如果递归方法中没有基本情况,或者从未达到基本情况,堆栈将永远增长,至少在理论上是这样。实际上,堆栈的大小是有限的。如果超过限制,就会出现 stackoverflower

例如,下面是一个没有基本情况的递归方法:

public static void forever(String s) {
    System.out.println(s);
    forever(s);
}

此方法显示给定的字符串,直到堆栈溢出为止,此时它抛出一个错误。在你的计算机上试试这个例子,你可能会惊讶于错误消息的长度!

值返回方法

为了让您了解如何使用所学的工具进行操作,让我们看看对递归定义的数学函数求值的方法。

递归定义与“循环”定义类似,定义指的是被定义的事物。当然,真正的循环定义并不是很有用:

递归:

用于描述递归方法的形容词。

如果你在字典里看到这个定义,你可能会生气。再次,如果你在谷歌上搜索“递归”,它会显示“你的意思是:递归”是一个内部笑话。人们总是喜欢这种联系。

许多数学函数都是递归定义的,因为这通常是最简单的方法。例如,一个整数n的阶乘,它写为n!,定义如下:

0!=1

n!=n·(n−1)!

不要混淆数学符号!,表示阶乘,使用Java运算符!,意思是没有。这个定义表示阶乘(0)是1,阶乘(n)是n*阶乘(n-1)

所以阶乘(3)是3*阶乘(2);阶乘(2)是2*阶乘(1);阶乘(1)是1*阶乘(0);阶乘(0)是1。综合起来,我们得到3*2*1*1,就是6

如果您可以为某个事物制定递归定义,那么就可以轻松地编写一个Java方法来计算它。第一步是确定参数和返回类型。因为factorial是为整数定义的,所以该方法接受int作为参数并返回int:

public static int factorial(int n) {
    return 0;  // stub
}

接下来,我们考虑基本情况。如果参数恰好为0,则返回1:

public static int factorial(int n) {
    if (n == 0) {
        return 1;
    }
    return 0;  // stub
}

否则,这是有趣的部分,我们必须进行递归调用,找到n−1的阶乘,然后乘以n:

public static int factorial(int n) {
    if (n == 0) {
        return 1;
    }
    int recurse = factorial(n - 1);
    int result = n * recurse;
    return result;
}

为了说明发生了什么,我们将使用临时变量recurseresult。在每个方法调用中,recurse存储n−1的阶乘,result存储n的阶乘。

如果我们使用值3调用阶乘:

由于3不是0,我们跳过第一个分支,计算n−1的阶乘。。。

	因为2不是0,我们跳过第一个分支,计算n−1的阶乘。。。

		由于1不是0,我们跳过第一个分支,计算n−1的阶乘。。。

			因为0是0,所以我们获取第一个分支并立即返回值1。

		返回值(1)乘以n,即1,然后返回结果。

	返回值(1)乘以n,即2,然后返回结果。

返回值(2)乘以n,即3,结果6返回到调用的factorial(3)。

如下显示了这个方法调用序列的堆栈图。返回值显示为向上传递堆栈。请注意,recurseresult在最后一帧中不存在,因为当n==0时,声明它们的代码不会执行。

Java递归方法Recursive详解

信仰的飞跃

遵循执行流程是读取程序的一种方式,但它很快就会变得势不可挡。理解递归的另一种方法是信心的飞跃:当您进入方法调用时,而不是遵循执行流程,而是假定方法正常工作并返回适当的值。

事实上,当您在Java库中使用方法时,您已经在实践这种信念的飞跃。当你调用数学.cos或者System.out.println,您不会考虑这些方法的实现。你只是假设他们工作正常。

其他方法也是如此。例如,考虑确定整数是否只有一位的方法:

public static boolean isSingleDigit(int x) {
    return x > -10 && x < 10;
}

一旦您通过检查和测试代码来说服自己这个方法是正确的,那么您就可以使用这个方法,而不必再查看实现了。

递归方法也不例外。在进行递归调用时,不要考虑执行流程。生成递归调用,而不是假定所需的结果。

例如,“假设我可以找到n−1的阶乘,我可以计算n的阶乘吗?“是的,你可以用n乘以。下面是一个factorial的实现,去掉了临时变量:

public static int factorial(int n) {
    if (n == 0) {
        return 1;
    }
    return n * factorial(n - 1);
}

请注意,此版本与原始数学定义有多相似:

0!=1

n!=n·(n−1)!

当然,当您还没有写完这个方法时,假设它能正确工作是很奇怪的。但这就是为什么它被称为信仰的飞跃!

另一个常见的递归定义的数学函数是Fibonacci序列,其定义如下:

fibonacci(1) = 1 
fibonacci(2) = 1 
fibonacci(n) = fibonacci(n−1) + fibonacci(n−2)

注意,每个Fibonacci数都是前面两个Fibonacci数的和。这个函数翻译成Java,如下所示:

public static int fibonacci(int n) {
    if (n == 1 || n == 2) {
        return 1;
    }
    return fibonacci(n - 1) + fibonacci(n - 2);
}

如果你试图遵循这里的执行流程,即使是很小的n值,你的头也会爆炸。但是,如果我们相信这两个递归调用是正确的,那么从定义来看,我们的实现是正确的。

递归计数

在倒计时示例的代码有三个部分:

  1. 检查基本情况
  2. 显示某些内容
  3. 进行递归调用

如果您反转步骤2和3,在显示之前进行递归调用,您认为会发生什么情况?

public static void countup(int n) {
    if (n == 0) {
        System.out.println("Blastoff!");
    } else {
        countup(n - 1);
        System.out.println(n);
    }
}

堆栈图和以前一样,方法仍然被调用n次。但是现在System.out.println在每个递归调用返回之前发生。因此,它是递增而不是递减:

Blastoff!
1
2
3

更多示例可参考这篇文章:https://javakk.com/512.html

 

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

关于

发表评论

表情 格式

暂无评论

登录

忘记密码 ?

切换登录

注册