递归返回一个位置数组，其中包含i在j中出现的位置。

Question

我不擅长Java，所以提前声明“这是我的作业”，请“不要帮我完成作业”，这是递归的第一项作业，我第一次做。话虽如此，以下是我的作业要求，但我不确定需要采取哪些步骤来实现目标。我只需要一个聪明的人给我提供关于如何完成作业的详细信息，比如步骤等。我已经阅读了书籍，查看了一些有关递归的网站，但我觉得我需要更多的帮助。

编写一个递归静态方法，给定两个字符串s和t，返回一个包含t在s中出现位置的数组。例如，findLocations（“Frances ran and ran”，“ran”）返回[1，8，16]。

- Bart g

---

这不幸的是不是递归算法的好例子，使用迭代来实现结果会更加直接。如果要返回一个链表，递归会更加合适，因为与数组连接相比，链表的连接是相当自然的。 - Daniel Fischer

如果你说不想让我们为你做作业，那么我们会给你点赞。但是我们不是约会网站，“我只需要一个好男人/女人”... = P 无论如何，如果任何答案帮助了你解决问题，你应该点击该答案下面的勾号（或者最有帮助的答案），以标记答案为已接受/获得更多声望。 - blahman

哈哈哈，那很有趣。我不确定是否应该将其标记为冒犯性内容。 - Bart g

Answer 1

我会这样处理：

1. 给定参数inputString 和 substring，调用index = inputString.indexOf(substring)。

2. 如果substring未被找到（index = -1），则应返回空数组（new int[0]），因为在inputString中不存在substring的出现。

3. 否则，substring存在，您应该执行以下操作：

   1. 使用类似arr = findLocations(inputString.substring(index+1), substring)的方法获取剩余字符串的索引数组。

   2. 通过将每个元素添加index来调整arr中的索引。

   3. return index与arr连接后的结果。

- aioobe

---

好的，这看起来就是我想要的帮助。谢谢您，先生。 - Bart g

Answer 2

由于您将通过第一个字符串进行递归并积极添加索引，因此我建议使用可变的东西，例如List。

至于您的递归方法，以下是一些提示：

// Initialize results list first
// Start the search using index = 0 and your empty results list.
ArrayList<Integer> recurSearch(String input, String search, int index, ArrayList<Integer> results)

// Inside recurSearch() 
int index = inputString.indexOf(search string, index);
// Here check the index. If it equals -1, no more matches. Return your result List.
// If does not equal -1, add to result list and return findLocations() using index + 1.

希望这个有意义。由于您显然想自己解决大部分问题，因此我尽量少包含代码。我包含了我的方法签名，希望这会指引您朝正确的方向。

- ggrigery

---

谢谢，非常感谢你的时间和帮助。 - Bart g

Answer 3

递归的工作方式通常是通过控制方法和操作方法来完成的。控制方法保存递归调用（这称为尾递归）。使用尾递归来解决这个问题很可能涉及到滑动窗口。这个网站有一些关于Java中递归的好信息：http://www.danzig.us/java_class/recursion.html 注意：抱歉，但在编写一些伪代码时，我产生了这段代码。我真的很喜欢递归。我把它留在这里，以便您稍后可以格式化它进行检查。

- Travis J

---

是的，我已经阅读了那个网站，因为我在等待回复。谢谢你提供的链接和当然还有代码，这将帮助我更好地理解这个主题，为考试做准备。 - Bart g