递归
![本页使用了标题或全文手工转换](http://upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
递归(英语:Recursion),又译为递回,在数学与计算机科学中,是指在函数的定义中使用函数自身的方法。递归一词还较常用于描述以自相似方法重复事物的过程。例如,当两面镜子相互之间近似平行时,镜中嵌套的图像是以无限递归的形式出现的。也可以理解为自我复制的过程。
正式定义
[编辑]在数学和计算机科学中,递归指由一种(或多种)简单的基本情况定义的一类对象或方法,并规定其他所有情况都能被还原为其基本情况。
例如,下列为某人祖先的递归定义:
斐波那契数列是典型的递归案例:
- (初始值)
- (初始值)
- 对所有大于1的整数n:(递归定义)
尽管有许多数学函数均可以递归表示,但在实际应用中,递归定义的高开销往往会让人望而却步。例如:
- (初始值)
- 对所有大于0的整数n:(递归定义)
一种便于理解的心理模型,是认为递归定义对对象的定义是按照“先前定义的”同类对象来定义的。例如:你怎样才能移动100个箱子?答案:你首先移动一个箱子,并记下它移动到的位置,然后再去解决较小的问题:你怎样才能移动99个箱子?最终,你的问题将变为怎样移动一个箱子,而这时你已经知道该怎么做的。
如此的定义在数学中十分常见。例如,集合论对自然数的正式定义是:1是一个自然数,每个自然数都有一个后继,这一个后继也是自然数。
以下是另一个可能更有利于理解递归过程的解释:
- 我们已经完成了吗?如果完成了,返回结果。如果没有这样的终止条件,递归将会永远地继续下去。
- 如果没有,则简化问题,解决较容易的问题,并将结果组装成原始问题的解决办法。然后返回该解决办法。
这样就有一种更有趣的描述:“为了理解递归,则必须首先理解递归。”或者更准确地,按照安德鲁·普洛特金的解释:“如果你已经知道了什么是递归,只需记住答案。否则,找一个比你更接近侯世达的人;然后让他/她来告诉你什么是递归。”[1]
举例:编写一个程序使用递归求n的阶乘:
Haskell:
fac 0 = 1
fac n = n * fac (n-1)
main = print( fac 10 )
语言中的例子
[编辑]- 从前有座山,山里有座庙,庙里有个老和尚,正在给小和尚讲故事呢!故事是什么呢?“从前有座山,山里有座庙,庙里有个老和尚,正在给小和尚讲故事呢!故事是什么呢?‘从前有座山,山里有座庙,庙里有个老和尚,正在给小和尚讲故事呢!故事是什么呢?……’”
- 一只狗来到厨房,偷走一小块面包。厨子举起杓子,把那只狗打死了。于是所有的狗都跑来了,给那只狗掘了一个坟墓,还在墓碑上刻了墓志铭,让未来的狗可以看到:“一只狗来到厨房,偷走一小块面包。厨子举起杓子,把那只狗打死了。于是所有的狗都跑来了,给那只狗掘了一个坟墓,还在墓碑上刻了墓志铭,让未来的狗可以看到:‘一只狗来到厨房,偷走一小块面包。厨子举起杓子,把那只狗打死了。于是所有的狗都跑来了,给那只狗掘了一个坟墓,还在墓碑上刻了墓志铭,让未来的狗可以看到……’”
- 大雄在房里,用时光电视看着从前的情况。电视画面中的那个时候,他正在房里,用时光电视,看着从前的情况。电视画面中的电视画面的那个时候,他正在房里,用时光电视,看着从前的情况……
数学之应用
[编辑]![](http://upload.wikimedia.org/wikipedia/commons/thumb/4/45/Sierpinski_triangle.svg/250px-Sierpinski_triangle.svg.png)
递归定义集
实例:自然数
[编辑]关于递归定义集的经典示例,可透过自然数来说明:
- 若, 则
- 满足上述两个条件之最小集合,即为自然数集合
实例:可导出的命题集合
[编辑]另一个有趣示例为,公理系统中,所有可导出命题之集合
此集合称为,可导出之命题之集合,因为在数学基础方法中,依非建立性法构建的命题之集合,可能大于由公理系统及推理规则所递归构建出之集合,详细请参见 哥德尔不完备定理
有限次分割法
[编辑]有限次分割法为几何形式之递归,可用以创建类分形之图案。次分割原则的运作如后所述,从多个已被有限个标签标注的多边形开始,接着每个多边形仅根据其标签,继续细切到更小的多边形,此一细切的过程可不断重复。
参见
[编辑]参考文献
[编辑]脚注
[编辑]- ^ 原文:“If you already know what recursion is, just remember the answer. Otherwise, find someone who is standing closer to Douglas Hofstadter than you are; then ask him or her what recursion is.”
书目
[编辑]- Johnsonbaugh, Richard. Discrete Mathematics. Prentice Hall. 2004. ISBN 0-13-117686-2.
- Hofstadter, Douglas. Gödel, Escher, Bach: an Eternal Golden Braid. Basic Books. 1999. ISBN 0-465-02656-7.
- Shoenfield, Joseph R. Recursion Theory. A K Peters Ltd. 2000. ISBN 1-56881-149-7.
- Causey, Robert L. Logic, Sets, and Recursion. Jones & Bartlett. 2001. ISBN 0-7637-1695-2.
- Cori, Rene; Lascar, Daniel; Pelletier, Donald H. Recursion Theory, Godel's Theorems, Set Theory, Model Theory. Oxford University Press. 2001. ISBN 0-19-850050-5.
- Barwise, Jon; Moss, Lawrence S. Vicious Circles. Stanford Univ Center for the Study of Language and Information. 1996. ISBN 0-19-850050-5. - offers a treatment of corecursion.
- Rosen, Kenneth H. Discrete Mathematics and Its Applications. McGraw-Hill College. 2002. ISBN 0-07-293033-0.
- Cormen, Thomas H., Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms. Mit Pr. 2001. ISBN 0-262-03293-7.
- Kernighan, B.; Ritchie, D. The C programming Language. Prentice Hall. 1988. ISBN 0-13-110362-8.
- Stokey, Nancy,; Robert Lucas; Edward Prescott. Recursive Methods in Economic Dynamics. Harvard University Press. 1989. ISBN 0674750969.
外部链接
[编辑]- Recursion - tutorial by Alan Gauld
- A Primer on Recursion (页面存档备份,存于互联网档案馆)- contains pointers to recursion in Formal Languages, Linguistics, Math and Computer Science
- Google easter for recursion (页面存档备份,存于互联网档案馆)
|