algorithm - 这是考虑编程中递归性的正确方法吗？ (例子)

Question

我一直在努力学习编程中的递归是什么，我需要有人来确认我是否已经完全理解它是什么。

我尝试考虑的方式是通过对象之间的碰撞检测。

假设我们有一个函数。当确定发生碰撞时调用该函数，并使用对象列表调用它以确定哪个对象发生碰撞，以及它与哪个对象发生碰撞。它首先确认列表中的第一个对象是否与其他任何对象发生碰撞。如果为真，该函数将返回列表中发生碰撞的对象。如果为 false，该函数将使用排除第一个对象的缩短列表调用自身，然后重复该过程以确定它是否是列表中发生碰撞的下一个对象。

这是一个有限递归函数，因为如果不满足所需条件，它会使用越来越短的列表调用自身，直到它演绎地满足所需条件。这与潜在的无限递归函数形成对比，在递归函数中，例如，它调用自身的列表不会缩短，但列表的顺序是随机的。

所以...这是正确的吗？或者这只是迭代的另一个例子？

谢谢!

编辑: 我很幸运得到@rici、@Evan 和@Jack 的三个非常好的答案。他们都从不同的角度在技术和实践方面给了我宝贵的见解。谢谢!

Answer 1

任何迭代都可以递归表示。 (并且，使用辅助数据结构，反之亦然，但并不那么容易。)

我会说您正在思考 迭代。那不是坏事；我不是说批评。简单地说，您的解释形式为“做这个，然后做那个，一直持续到最后”。

递归是一种稍微不同的思维方式。我遇到了一些问题，目前还不清楚如何解决。但我观察到，如果我知道一个更简单问题的答案，我就可以轻松解决手头的问题。而且，还有一些非常简单的问题我可以直接解决。

递归解决方案是基于使用更简单(更小、更少、随便什么)的问题来解决手头的问题。如何找出一组对象中的哪些对象对发生碰撞？

1. 如果集合中的元素少于 2 个，则没有对。这是最简单的问题，它有一个显而易见的解决方案:空集。

2. 否则，我选择一些对象。所有碰撞对要么包含此对象，要么不包含。所以这给了我两个子问题。

3. 不涉及所选对象的碰撞集显然与我开始时遇到的问题相同，但碰撞集较小。所以我用一个更小的问题替换了这部分问题。这是一个递归。

4. 但我还需要所选对象与之碰撞的对象集(可能是空集)。这是一个更简单的问题，因为现在每对中的一个元素是已知的。我也可以递归地解决这个问题:

   • 我需要包含对象 X 和一组对象 S 的成对集合。

     1. 如果集合为空，则没有对。简单。

     2. 否则，我从集合中选择一些元素。然后我找到 X 和集合的其余部分之间的所有冲突(一个更简单但其他方面相同的问题)。

     3. 如果 X 和所选元素之间存在碰撞，我会将其添加到我刚刚找到的集合中。

     4. 然后我把套装还回去。