递归地实现一个equals方法

Question

基本上，我需要比较两个数组并检查它们是否在相同的位置具有相同的值（当然是递归的）。我的当前代码出错：数组超出索引 exception:20

我现在的代码如下所示：

    private boolean equalsHelper(int[] first, int[] second, int iStart, int iEnd){
    if (first[iStart] == second[iStart]){
        if (equalsHelper(first,second,(iStart+1),iEnd))
        {
            return true;
        }
    }
    if (iStart == iEnd){
        return first[iEnd] == second[iEnd];
    }
    return false;
}

Answer 1

撇开递归是否是正确解决方案的问题（它确实不是，这里的迭代是微不足道的并且会执行得更好），问题是没有检查终止条件（iStart == iEnd）直到递归调用之后。

任何递归算法都必须 a) 检查继续递归是否合适，以及 b) 在检查后进行递归调用。未能包含第一步，或乱序执行这些步骤，将导致无限递归，直到出现错误（WhosebugError 如果没有其他事情首先发生）。

您在递归调用之前确实进行了条件检查，但这是为了方法的总体目的，而不是为了结束递归。您还有结束递归的条件检查，但它是在递归调用之后完成的。解决方案是交换它们的顺序 - 将 if (iStart == iEnd) 块移动到 if (first[iStart] == second[iStart]) 块之前。

Answer 2

递归是一种强大的编程技术，但在 Java 语言中有一些缺点。如果 java 中的方法在返回之前递归调用自身的次数过多，将导致 WhosebugError。在这种情况下，几乎可以保证比较两个数组的相等性。

Scala 等其他语言允许您编写针对递归（尾递归）优化并在常量堆栈中执行的递归函数 space。

话虽如此，您应该考虑递归是否真的是这里的正确解决方案。它既不优化解决方案，也不增加代码清晰度。

注意：如果您只想比较 Java 中的两个数组，那么 java.util.Arrays 已经涵盖了您。

Answer 3

您只需将停止条件放在代码的开头即可。如果 iStart 一开始是 0 并且 iEnd 是数组长度 - 1，这将起作用。

private boolean equalsHelper(int[] first, int[] second, int iStart, int iEnd) {

    if (iStart == iEnd) { // you need to check this first
        return first[iEnd] == second[iEnd];
    }

    if (first[iStart] == second[iStart]) {
        if (equalsHelper(first, second, (iStart + 1), iEnd)) {
            return true;
        }
    }
    return false;
}

如果您想使用数组长度作为 iEnd 的输入，您只需要稍微更改一下代码

private boolean equalsHelper2(int[] first, int[] second, int iStart, int iEnd) {
    if (iStart == iEnd) {
        return true;
    }

    if (first[iStart] == second[iStart]) {
        if (equalsHelper2(first, second, (iStart + 1), iEnd)) {
            return true;
        }
    }
    return false;
}

既然提到了几次性能，我就说几句吧。堆栈包含有关局部变量和函数调用的信息。所以每次递归调用都会将这些信息保存在堆栈中，这将导致大量输入的堆栈溢出，因为堆栈只有有限的 space。由于与循环相比有更多的汇编程序命令，因此执行速度也较慢。

这可以通过使用尾递归函数来避免。尾递归调用仅意味着您的递归调用必须是在您的方法中执行的最后一条语句。编译器会将其翻译成一个循环。这更快并且在堆栈上使用更少 space。

equals 方法的尾递归版本如下所示：

private boolean equalsHelper2(int[] first, int[] second, int iStart, int iEnd)
{
    if (iStart == iEnd)
    {
        return true;
    }else{
        if(first[iStart] != second[iStart])
        {
            return false;
        } else
        {
            return equalsHelper2(first, second, iStart + 1, iEnd);
        }
    }
}

递归地实现一个equals方法

Implementing an equals method recursively

java

recursion

equals