Java递归方法Recursive详解二

二进制数系统

你可能知道计算机只能存储1和0，这是因为处理器和内存是由数十亿个微小的开关组成的。

值1表示开关打开；值0表示开关关闭。所有类型的数据，无论是整数、浮点、文本、音频、视频或其他数据，都用1和0表示。

幸运的是，我们可以将任何整数表示为二进制数。下表显示了前8个二进制和十进制数字。

十进制有10位数字，数字的书面表示是以10的幂为基础的。例如，456在100位有4位，10位有5位，1位有6位。所以值是400+50+6：

二进制中有两个数字，数字的书面表示是基于2的幂。例如，10111在16位有1，8位有0，4位有1，2位有1，1在1位。所以这个值是16+0+4+2+1，十进制数是23。

为了得到十进制数的位数，我们可以使用重复除法。例如，如果我们用456除以10，那么余数为6得到45。余数是456的最右边的数字。

如果我们再除以结果，我们得到4和余数5。余数是456的第二个最右边的数字。如果我们再除以一次，余数为4得到0。余数是456的第三个最右边的数字，结果是0，告诉我们完成了。

如果我们除以2，在二进制中也可以做同样的事情。除以2时，余数是最右边的数字，可以是0或1。如果你再除以结果，你得到第二个最右边的数字。如果你继续写下余数，你就会得到二进制数：

23 / 2 is 11 remainder 1
11 / 2 is  5 remainder 1
 5 / 2 is  2 remainder 1
 2 / 2 is  1 remainder 0
 1 / 2 is  0 remainder 1

从下至上读这些余数，二进制中的23等于10111。

递归二进制法

现在，为了以二进制形式显示一个数字，我们可以结合上一节的算法和这一篇中的的“向上计数”模式：https://javakk.com/517.html

以下是一个递归方法，它以二进制形式显示任何正整数：

public static void displayBinary(int value) {
    if (value > 0) {
        displayBinary(value / 2);
        System.out.print(value % 2);
    }
}

如果value为0，displayBinary不执行任何操作（这是基本情况）。如果参数为正，则该方法将其除以2并递归调用displayBinary。当递归调用返回时，该方法显示结果的一位数并返回（再次）。下图说明了这一过程。

最左边的数字在堆栈的底部附近，所以它首先显示出来。最右边的数字，靠近栈顶，最后显示。在调用displayBinary之后，我们使用println来完成输出：

displayBinary(23);      // output is 10111
System.out.println();

CodingBat问题

在过去的几章中，您已经看到了方法、条件、循环、字符串、数组和递归。实践所有这些概念的一个很好的资源是：http://codingbat.com/

斯坦福大学的一个免费编程网站是由尼克·兰特开发的。当您处理这些问题时，CodingBat会保存您的进度（如果您创建了一个帐户）。

为了结束这一章，我们考虑了CodingBat的递归-1部分中的两个问题。其中一个处理字符串，另一个处理数组。它们都有相同的递归思想：检查基本情况，查看当前索引，然后递归地处理其余的内容。

第一个问题在 http://codingbat.com/prob/p118230 :

递归-1 noX

给定一个字符串，递归地计算一个新字符串，其中所有的“x”字符都已删除。

noX("xaxb") → "ab"

noX("abc") → "abc"

noX("xx") → ""

在解决递归问题时，首先考虑基本情况是有帮助的。基本情况是问题的最简单版本；对于noX，它是空字符串。如果参数是空字符串，则没有要删除的x：

if (str.length() == 0) {
    return "";
}

接下来是更困难的部分。要递归地解决问题，您需要考虑同一问题的一个更简单的实例。对于noX，它是从一个较短的字符串中去掉所有的x。

所以让我们把字符串分成两部分，第一个字母和其余的字母：

char first = str.charAt(0);
String rest = str.substring(1);

现在我们可以通过递归调用从rest中删除x：

String recurse = noX(rest);

如果第一个正好是x，我们就完成了；我们只需要返回recurse。否则，我们必须首先连接并递归。下面是我们需要的if语句：

if (first == 'x') {
    return recurse;
} else {
    return first + recurse;
}

通过将这些代码片段粘贴到提供的方法定义中，可以在CodingBat上运行此解决方案。

递归-1数组11

给定一个整数数组，递归计算值11在数组中出现的次数。

array11([1, 2, 11], 0) → 1
array11([11, 11], 0) → 2
array11([1, 2, 3, 4], 0) → 0

这个问题使用传递索引作为参数的约定。所以基本情况是当我们到达数组的末尾时。在那一点上，我们知道没有更多的11：

if (index >= nums.length) {
    return 0;
}

接下来我们查看当前的数字（基于给定的索引），并检查它是否是11。之后，我们可以递归地检查数组的其余部分。与noX问题类似，每个方法调用只查看一个整数：

int recurse = array11(nums, index + 1);
if (nums[index] == 11) {
    return recurse + 1;
} else {
    return recurse;
}

同样，通过将代码片段粘贴到方法定义中，可以在CodingBat上运行此解决方案。

学习递归思维是学习像计算机科学家一样思考的一个重要部分。许多算法可以用递归方法简洁地编写，递归方法在向下、向上或同时执行计算。

递归练习题

使用堆栈图来理解以下递归方法的执行：

public static void main(String[] args) {
    System.out.println(prod(1, 4));
}

public static int prod(int m, int n) {
    if (m == n) {
        return n;
    } else {
        int recurse = prod(m, n - 1);
        int result = n * recurse;
        return result;
    }
}

1. 绘制一个堆栈图，显示最后一次prod调用完成之前程序的状态。
2. 这个程序的输出是什么？（请先在纸上回答这个问题；然后运行代码检查您的答案。）
3. 用几句话解释一下prod是做什么的（没有详细说明它是如何工作的）。
4. 重写prod而不使用递归和结果临时变量。提示：else分支只需要一行。

本练习的目标是将递归定义转换为Java方法。Ackermann函数为非负整数定义如下：

编写一个名为ack的递归方法，它以两个int作为参数，计算并返回Ackermann函数的值。

测试Ackermann的实现，方法是从main调用它并显示返回值。注意，返回值很快就会变得非常大。您应该只对m和n的较小值（不大于3）进行尝试。

创建一个名为递归.java并键入以下方法：

/**
 * Returns the first character of the given String.
 */
public static char first(String s) {
    return s.charAt(0);
}

/**
 * Returns all but the first letter of the given String.
 */
public static String rest(String s) {
    return s.substring(1);
}

/**
 * Returns all but the first and last letter of the String.
 */
public static String middle(String s) {
    return s.substring(1, s.length() - 1);
}

/**
 * Returns the length of the given String.
 */
public static int length(String s) {
    return s.length();
}

1. 在main中编写一些测试这些方法的代码。确保它们能起作用，你也能理解它们的作用。
2. 使用这些方法，在不使用任何其他字符串方法的情况下，编写一个名为printString的方法，该方法以字符串为参数并显示字符串的字母，每行一个。它应该是一个无效的方法。
3. 同样，只使用这些方法，编写一个名为printback的方法，它执行与printString相同的操作，但是向后显示字符串（同样，每行一个字符）。
4. 现在编写一个名为reverseString的方法，它将字符串作为参数，并返回一个新字符串作为返回值。新字符串应包含与参数相同的字母，但顺序相反：

String backwards = reverseString("coffee");
System.out.println(backwards);

此示例代码的输出应如下所示：

eeffoc