bir*_*lsh 6 recursion functional-programming sml
我突然处于一个递归语言类(sml)中,并且递归对我来说还不是很合理.我正在考虑方形瓷砖的地板有时是整数乘法的模型或隐喻的方式,或者Cuisenaire Rods是加法和减法的模型或模拟.有没有人可以分享任何这样的模型？
想象一下,你是一个真正的魔术师,可以复制自己.你创造了你的双倍靠近目标,给他(或她)与你给出的相同的命令.
你的双倍与他的副本相同.你看,他也是魔术师.
当最终副本发现自己在目标处创建时,它无处可去,因此它会向其创建者报告.哪个也一样.
最终,你得到你的回答 - 没有移动一英寸 - 现在可以轻松地从中创建最终结果.你假装不知道所有那些为你做实际辛勤工作的双打."嗯,"你对自己说,"如果我是一步步接近目标, 已经知道 结果呢？那岂不是 很容易 找到最终的答案 ,然后 ？" *
当然,如果你是双人,你必须向你的创作者报告你的发现.
更多这里.
(另外,我觉得我看到这个"双打"创造链事件在这里,虽然我不能完全肯定).
*这是问题解决的递归方法的本质.
我怎么知道我的手术是对的？如果我的简单的小组合步骤产生了一个有效的解决方案,假设它为较小的情况产生了正确的解决方案,我所需要的是确保它适用于最小的情况 - 基本情况 - 然后通过归纳证明有效性!
另一种可能性是分而治之,我们将问题分成两半,因此将更快地达到基本情况.只要组合步骤简单(当然保留解决方案的有效性),它就可以工作.在我们的魔术师比喻中,我创建了两个自己的副本,并在完成后将两个答案合并为一个.他们每个人都创建了两个自己的副本,因此这创建了一个魔术师的分支树,而不是像以前那样创建一个简单的行.
一个很好的例子是Sierpinski三角形,它是一个由三个四分之一大小的Sierpinski三角形构成的图形,通过在角落处堆叠它们.
三个组成三角形中的每一个都是根据相同的配方构建的.
虽然它没有基本情况,因此递归是无界的(无底的;无限的),ST的任何有限表示都可能只画一个点代替ST太小(作为基本情况,停止递归).
链接的维基百科文章中有一张很好的图片.
递归绘制没有大小限制的ST将永远不会在屏幕上绘制任何内容!对于数学家来说,递归可能很好,但工程师应该对它更加谨慎.:)
切换到corecursion/iteration(参见链接的答案),我们首先绘制轮廓,然后绘制内部; 因此,即使没有大小限制,图片也会很快出现.然后该程序将忙碌而没有任何明显的效果,但这比空屏幕更好.