java - 在不断缩小的 LispList 中递归查找 INT 的索引

Question

这里是计算机科学专业的二年级学生，作为递归练习的一部分，我们得到了一些要用 LispLists 解决的任意问题。我中途卡住了，所以如果有人能在没有明确给我答案的情况下指出正确的方向，那就太好了。

我需要在 LispList listToCheck 中找到 intToFind 的每个实例的位置 - 唯一的条件是:

• 不能使用额外的参数
• 它必须递归地完成

对于所有没有接触过 LispLists 的人——它们没有索引，你可以调用它们的唯一方法是:

• .isEmpty() 返回 boolean 值
• .head() 返回第0个位置的元素
• .tail() 返回所有非头部元素的 LispList
• .cons(value) 为“头部”位置增加值(value) - 将其他所有位置向下移动

还有一个我之前写的方法叫:

• recursiveCountLength(list) 返回传递的 LispList 长度的整数。

我一直在测试的列表是:[2,3,4,2,5,12,2,5]，所以我要查找的结果是 [0,3,6] - 有了这个，这就是我到目前为止所得到的(解释我之后尝试的内容):

public static LispList<Integer>
  recursivePositions(LispList<Integer> listToCheck, int intToFind)
{
  if(listToCheck.isEmpty()) return listToCheck;
  else {
    // go through the array in its entirety once through,
    // do everything else 'on the way back up'
    LispList<Integer> positions = recursivePositions(listToCheck.tail(), intToFind);

    //get the current length and current head
    int currentInt      = listToCheck.head();
    int currentLength   = recursiveCountLength(listToCheck); 

    //if a match is found, add the current length of the list to the list 
    if(currentInt == intToFind) return positions.cons(currentLength);
    else return positions;
  }
}

我目前的理论是，每次遇到我们正在寻找的 int 时，数组的长度(在本例中为 2)从列表的原始长度(在本例中为 8)中减去即可得到索引。

• 2 首先出现的长度为 8(8-8 = 索引为 0，因此索引现在为 [0])，
• 2 接下来发生的长度为 5(8-5 = 索引为 3，因此索引现在为 [0, 3])，
• 2 最后出现在长度为 2 处(8-2 = 索引为 6，因此索引现在为 [0, 3, 6])。

唯一的问题是我无法弄清楚如何获得静态“8”——这让我得出结论，我正在以完全错误的方式处理这个问题。这里有人对我有什么建议吗？任何帮助将不胜感激。

Answer 1

澄清一下:LispList 只是一个单链表(以区别于 Java LinkedList，后者是双链表)。

通常，您会使用一个助手将信息携带到递归调用中，例如当前位置和已经找到的位置(当前部分结果)。

LispList<Integer> positions (final int item, final LispList<Integer> list) {
    return positionsAux( item, list, 0, new LispList<Integer>() );
}

private LispList<Integer> positionsAux (final int item,
                                        final LispList<Integer> list,
                                        final int position,
                                        final LispList<Integer> result) {
    if (list.isEmpty()) {
        return result.reverse();
    }
    if (list.head().intValue() == item) {
        result = result.cons(position);
    }
    return positionsAux( item, list.tail(), position + 1, result );
}

如果不允许，则需要将结果向后携带。如果您假设递归调用为您的 list.tail() 返回了正确的结果，您需要将每个找到的位置加 1 以获得您的 list 的正确结果>。然后，如果当前元素匹配，您cons 将 0 赋给结果。这个版本比第一个版本效率低，因为你遍历输入列表的每个元素的当前结果列表(所以它是 O(n·m) 而不是 O(n)，其中 n 是输入列表的长度，m 是结果列表的长度)。

LispList<Integer> positions (final int item, final LispList<Integer> list) {
    if (list.isEmpty()) {
        return new LispList<Integer>();
    }
    final LispList<Integer> tailResult = positions( item, list.tail() );
    final LispList<Integer> result = tailResult.addToEach( 1 );
    if (list.head().intValue() == item) {
        return result.cons( 0 );
    } else {
        return result;
    }
}

第一个版本的 reverse() 和第二个版本的 addToEach(int) 留给读者作为练习。