递归： 1. 执行时逐层递归调用，遇到边界条件停止递归，并逐层返回调用至最初层，系统资源消耗比循环大。 2. 递归必须要有边界条件，即停止递归的条件。 如 n ==0 or n ==1 3. 递归的代码更简洁，更符合自然逻辑，更易理解。 脚本示例： 递归 - 汉诺塔游戏 三个塔座A B C上各有一根针，通过B把n个盘子从A针移动到C针，且移动时必须遵循下列规则： 1）盘子可以插入在A B C塔座的针上 2）每次只能移动一个盘子 3）任何时刻都不能将一个较大的盘子压在较小的盘子之上
咱们可以聊聊 为什么叫 center 递归 ， 很多人不做区分。自然语言中 ， right branching 递归很常见，也常可以超过三层。说的人 ， 听的人，都不感觉是负担。道理就在 ， 虽然“左括号”在不确定的位置，但他们都归于统一的右边界。这样一来 就不需要栈（该死的栈！）结构的机制来对付它，有限状态就可以了。乔姆斯基没法拿这个常见的所谓递归来批判有限状态，因此他不得不举 center 递归 作为杀手锏。可问题是，自然语言几乎没有什么 center 递归。 雷 : The man who the woman who had lost all the keys was calling all day finally came 白 : 关于印发关于学习落实关于进一步深化改革的决定的若干意见的通知 …… center recursion 的中文例子 这些是人话吗？亏老乔是语言学祖师爷！乔老爷反复给我们洗脑：这不仅是人话，而且是人话的本质。 这就是牵强附会，登峰造极地牵强附会。 雷 : right branching 递归是线性的， 而 center embedding 不是线性的 这里面就形成了这么个 trap ， 信服他的人 ， 一个是源于他的权威性 , 另一方面是把常见的右递归当成了支持乔老爷的证据。乔形式上没有误导，因为他是严谨的、聪明的，但实际上达到了误导的效果。这就是“递归教”的 fallacy . 雷 : 这个是 right branching sentence ： The dog slept on the doorstep of the house in which it lived. 右递归太常见了 ， 而且一点也不牵强。典型的句式是 vp 的嵌套： t o ask sb to beg sb to order sb to … 雷 : 我来理解一下你的意思： center embedding recursive sentences 不存在，或不出三层，所以是 fina te state 的？ 不是不存在 ， 是如此罕见与牵强，而且也从来不超过三层，除非你是恶作剧，因此它绝非语言本性。 雷 : right branching 不足为道，本来就是线性的。 CFG 的 parsing 在理论上是 cubic ，就是因为这个 center embedding 白 : 这么多计算手段怎么会被 center recursion 憋死 ，自动机加几个计数器就可以线性了，只要计数器不爆表。 拿恶作剧和语言游戏作为语言能力的证据，是乔老爷的最大忽悠。 雷 : 我觉得这是数学家和哲学家的通例：形式上的完美。而我们做 NLU 的，从来就不把这个当真，是不是？ 既然最多不过三层 , 那么多层有限状态即可轻松应对，三层 就是 3x ， 当然还是线性 雷 : 语言学系的人不到计算机系串门 世界上有人把简单的问题复杂化，递归便是一例。 雷 : 呵呵，因为我们不是数学家出身？我同意你的说法：就只有几层，有方法可以对付，不必搬出递归来。 他那些理论真地是折磨人 ， 云山雾罩的。有时候感觉 ， 全世界语言学家被他玩得够苦。我还算幸运，我们系比较开通，学句法的时候躲开了乔姆斯基，拿 hpsg 来充数。 hpsg 至少比 gb 接地气，尽管它像个要争宠的小妾，每一个分析都要以乔老爷的主流作为假想对象，反复辩白，妾身清白。 雷 : 加州那边不受什么影响吧，走的是另一个路子，如， cognitive grammar , Fillmore Fillmore 了不起， 但过分细琐. F ramenet 很好的概念 但不实用， 以前写【 语义三巨人 】专门论过。 因为它处于语义和语用之间， 不尴不尬。 雷 : 我专门研究过 framenet ，觉得还是不够细 ， 同你的琐碎不是一回事。是每个动词的用法还不够全 ， 还有就是 Verbnet 。感觉是虎头蛇尾，后面都是学生做的，真正要用起来还不够全面。 我看法正相反。我也仔细研究过它。以后找机会展开与你辩论。 【相关博文】 乔姆斯基批判 《立委随笔：自然语言是递归的么？》 【 语义三巨人 】 【置顶：立委科学网博客NLP博文一览（定期更新版）】
你能将细绳从装置上解下来吗？不准剪断细绳。 维基百科中将这个在游戏作为连接为中文九连环的英文版本内容,其实是不完全恰当的。实际上，这个装置不仅与九连环有联系，它也可以解释为汉诺塔的另一个版本（详情在后续博文中介绍），十分有趣。 因为其名称在各国很不一致，在这里，我们尝试以其内涵的递归意义和形态，将其命名为“兄弟连（Band of brothers）”。
mirror 说： ”括号可以用几重？立委作为计算机的半拉专家，应该知道是有限的。问题是限在几重上。…… 比如｛［最（伟光正的）党］领导的｝是一个深度的例子。 没有抽象化，也就没有学问了。问题不在于可不可以。问题是出自一个什么样的考虑、取舍，定下的如此规矩。” 由镜子所说引申去：自然语言是递归的么？ (92201) Posted by: liwei999 Date: June 17, 2007 05:17PM 很多句法学家认为，自然语言的结构具有递归性 (recursion)。递归的表现是结构的嵌套，这就好像我们数学表达式中使用括号一样，理论上是括号的嵌套使用是无限的（无法预先规定嵌套的层数）。可是，语言的制约不仅仅是句法，还有语用上的限制。 自然语言中，括号的有限使用是语用学（pragmatics）的常识和可以观察到的语言现实。因为中间嵌套太深，不利于交流，也会超出人的短期记忆的承受范围。 中间嵌套的例子有主句套从句：主句的主语（S）和做谓语的动词短语(VP)中间又插入一个定语从句，修饰主句的主语： A guy who knows a girl also knows another girl. 其结构是： VP] 然而，右嵌套可以很深，在英语，这种例子屡见不鲜。 ［… ]]]]] 例如： I know a guy, who knows a girl, who knows another guy, who knows …… 其结构是： ]]]] 再如：有一类英语动词（a verb subcategy），其动词短语要求嵌套另一个动词短语作为其宾语补足语，如果被嵌套的动词短语恰好也是同类动词，这种嵌套就可以循环下去。 这类动词有：expect, tell, ask, force, … VP 的句型是：VP – （V是这类动词，NP 是名词短语做宾语） 譬如： I expected John to finish the homework. I expected John to tell Mary to finish the homework. I expected John to tell Mary to ask her students to finish the homework. …… 其结构是： ]]]] 由于语言结构的recursive nature, 受到”乔木司机“的形式语言理论的不良影响，很长一段时间，计算语言学界推崇能够反映recursion的上下文无关语法（CFG, Context Free Grammar），排斥有限状态语法（FSG, Finite State Grammar），认为后者不适合自然语言parsing。可是，研制实用系统的人对简单而高效的FSG情有独衷。 FSG 比起 CFG 不够 powerful，为什么也可以成功运用在自然语言的parsing上呢？ 诀窍就在，可以把很多个FSG叠加起来用（cascaded finite state device），一层一层地由里往外退括号。由于语用学的制约，人类实际的语言现象，表达中间recursion的括号数量是很有限的（很少超过三层，形象地说，只要大中小三种括号就够用了），而边缘嵌套难不住FSG (其实实际语料中边缘嵌套也很少超过五层)，所以线性叠加完全可行。 【置顶：立委科学网博客NLP博文一览（定期更新版）】
标签: 递归
