我可以要求递归的物理类比或隐喻吗? [英] Could I ask for physical analogies or metaphors for recursion?

问题描述

我突然进入了递归语言课程 (sml) 并且递归对我来说在物理上还不合理.我在想，一块方形瓷砖有时是整数乘法的模型或隐喻，或者 Cuisenaire Rods 是加法和减法的模型或类似物.有没有人有这样的模型可以分享?

I am suddenly in a recursive language class (sml) and recursion is not yet physically sensible for me. I'm thinking about the way a floor of square tiles is sometimes a model or metaphor for integer multiplication, or Cuisenaire Rods are a model or analogue for addition and subtraction. Does anyone have any such models you could share?

推荐答案

想象一下你是一个现实生活中的魔术师，并且可以复制你自己.你创造你的替身离目标更近了一步，并给他(或她)同样的命令.

Imagine you're a real life magician, and can make a copy of yourself. You create your double a step closer to the goal and give him (or her) the same orders as you were given.

你的替身对他的副本做同样的事情.他也是个魔术师，你看.

Your double does the same to his copy. He's a magician too, you see.

当最终副本发现自己创建目标时，它无处可去，因此它会向其创建者报告.哪个也一样.

When the final copy finds itself created at the goal, it has nowhere more to go, so it reports back to its creator. Which does the same.

最终，您会得到答案–没有移动一英寸 –现在可以轻松地从中创建最终结果.你可以假装不知道那些替你做实际工作的双打.嗯，"你在对自己说，如果我离目标更近了一步并且 已经知道 结果是不是 容易 找到最终答案 然后 ?" ^*

Eventually, you get your answer back – without having moved an inch – and can now create the final result from it, easily. You get to pretend not knowing about all those doubles doing the actual hard work for you. "Hmm," you're saying to yourself, "what if I were one step closer to the goal and already knew the result? Wouldn't it be easy to find the final answer then ?" ^*

当然，如果你是替身，你必须向你的创作者报告你的发现.

Of course, if you were a double, you'd have to report your findings to your creator.

更多此处.

(另外，我想我看到了这个双打"创建链事件 此处，虽然我不完全确定).

(also, I think I saw this "doubles" creation chain event here, though I'm not entirely sure).

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

^* and that is the essence of the recursion method of problem solving.

我怎么知道我的程序是正确的?如果我简单的小组合步骤产生了一个有效的解决方案，假设它为较小的情况产生了正确的解决方案，我所需要的就是确保它适用于最小的情况 -ndash;基本情况然后通过归纳证明有效性！

How do I know my procedure is right? If my simple little combination step produces a valid solution, under assumption it produced the correct solution for the smaller case, all I need is to make sure it works for the smallest case – the base case – and then by induction the validity is proven!

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

Another possibility is divide-and-conquer, where we split our problem in two halves, so will get to the base case much much faster. As long as the combination step is simple (and preserves validity of solution of course), it works. In our magician metaphor, I get to create two copies of myself, and combine their two answers into one when they are finished. Each of them creates two copies of themselves as well, so this creates a branching tree of magicians, instead of a simple line as before.

一个很好的例子是 谢尔宾斯基三角形，它是由三个四分之一大小的谢尔宾斯基三角形，只需将它们堆叠在角落即可.

A good example is the Sierpinski triangle which is a figure that is built from three quarter-sized Sierpinski triangles simply, by stacking them up at their corners.

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

Each of the three component triangles is built according to the same recipe.

尽管它没有基本情况，因此递归是无界的(无底的；无限的)，但 S.T. 的任何有限表示大概只会画一个点来代替 S.T.太小了(作为基本情况，停止递归).

Although it doesn't have the base case, and so the recursion is unbounded (bottomless; infinite), any finite representation of S.T. will presumably draw just a dot in place of the S.T. which is too small (serving as the base case, stopping the recursion).

链接的维基百科文章中有一张很好的图片.

There's a nice picture of it in the linked Wikipedia article.

递归绘制 S.T.没有大小限制将永远不会在屏幕上绘制任何东西！对于数学家来说，递归可能很棒，但工程师应该对此更加谨慎.:)

Recursively drawing an S.T. without the size limit will never draw anything on screen! For mathematicians recursion may be great, engineers though should be more cautious about it. :)

切换到corecursion ⁄迭代(请参阅相关的答案)，我们将首先绘制轮廓，然后绘制内部结构；所以即使没有大小限制，图片也会很快出现.然后程序会很忙，没有任何明显的影响，但这比空屏幕要好.

Switching to corecursion ⁄ iteration (see the linked answer for that), we would first draw the outlines, and the interiors after that; so even without the size limit the picture would appear pretty quickly. The program would then be busy without any noticeable effect, but that's better than the empty screen.

这篇关于我可以要求递归的物理类比或隐喻吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！