recursion - 我可以要求递归的物理类比或隐喻吗？

Question

我突然进入了递归语言类(class)(sml)，对我而言，递归在 body 上还不明智。我在考虑方形瓷砖的地板有时是整数乘法的模型或隐喻的方式，还是Cuisenaire Rods是加减法的模型或类似物的方式。有人有您可以分享的任何此类模型吗？

Answer 1

假设您是一名现实生活中的魔术师，并且可以复制自己。您将目标加倍，使目标更接近目标，并给他(或她)相同的命令。

您的 double 和他的副本一样。你也知道他也是魔术师。

当最终副本发现自己已达到目标时，便无处可去，因此它会向其创建者报告。哪个做的一样。

最终，您无需移动英寸就可以得到答案，现在可以轻松地从中创建最终结果。您会假装不知道为您做实际努力的所有那些 double 。 “嗯，” ，你在自言自语，“如果我离目标更近一步，并且已经知道了吗？难道容易来找到最终答案然后吗？ ” *

当然，如果您是 double ，则必须将您的发现报告给创建者。

更多here。

(同样，我想我看到了这个“ double ”创建链事件here，尽管我不确定)。

*这就是解决问题的递归方法的本质。

我怎么知道我的程序是正确的？如果我的简单组合步骤能够得出有效的解决方案，那么在假定它为较小的情况提供了正确的解决方案的情况下，我所需要做的就是确保它适用于最小的情况(基础情况)，然后通过归纳证明有效性!

另一种可能性是divide-and-conquer，我们将问题分成两半，因此可以更快地到达基本情况。只要组合步骤很简单(并且当然保留了求解的有效性)，它就可以工作。在魔术师的比喻中，我可以创建自己的两个副本，并在完成后将两个答案合并为一个。他们每个人也创建自己的两个副本，因此这将创建魔术师的分支树，而不是像以前那样简单的一行。

一个很好的例子是Sierpinski triangle，它是通过简单地将三个四分之一大小的Sierpinski三角形堆叠在其角上而构建的。

三个组成三角形中的每一个都是根据相同的配方构建的。

尽管它没有基本情况，所以递归是无界的(无底的；无限的)，S.T。的任何有限表示形式都可以。大概只会在S.T.上画一个点太小了(用作基本情况，停止递归)。

链接的Wikipedia文章中对此有很好的描述。

递归绘制S.T.没有大小限制，将永远不会在屏幕上绘制任何内容!对于数学家来说，递归可能很棒，尽管工程师应该对此更为谨慎。 :)

切换到corecursion ⁄迭代(请参见链接的答案)，我们首先绘制轮廓，然后绘制内部轮廓；因此，即使没有尺寸限制，图片也会很快出现。然后，程序将忙碌而没有任何明显的效果，但这比空白屏幕要好。