语言例子

从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？“从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？‘从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？……’”

一只狗来到厨房，偷走一小块面包。厨子举起杓子，把那只狗打死了。于是所有的狗都跑来了，给那只狗掘了一个坟墓，还在墓碑上刻了墓志铭，让未来的狗可以看到：“一只狗来到厨房，偷走一小块面包。厨子举起杓子，把那只狗打死了。于是所有的狗都跑来了，给那只狗掘了一个坟墓，还在墓碑上刻了墓志铭，让未来的狗可以看到：‘一只狗来到厨房，偷走一小块面包。厨子举起杓子，把那只狗打死了。于是所有的狗都跑来了，给那只狗掘了一个坟墓，还在墓碑上刻了墓志铭，让未来的狗可以看到……’”

正式定义

在数学和计算机科学中，递归指由一种（或多种）简单的基本情况定义的一类对象或方法，并规定其他所有情况都能被还原为其基本情况。

例如，下列为某人祖先的递归定义：

某人的双亲是他的祖先（基本情况）。

某人祖先的双亲同样是某人的祖先（递归步骤）。

斐波那契数列是典型的递归案例：

F 0 = 0 {\displaystyle F_{0}=0} （初始值）

F 1 = 1 {\displaystyle F_{1}=1} （初始值）

对所有大于1的整数n： F n = F n − − --> 1 + F n − − --> 2 {\displaystyle F_{n}=F_{n-1}+F_{n-2}} （递归定义）

尽管有许多数学函数均可以递归表示，但在实际应用中，递归定义的高开销往往会让人望而却步。例如：

0 ! = 1 {\displaystyle 0!=1} （初始值）

对所有大于0的整数n： n ! = n × × --> ( n − − --> 1 ) ! {\displaystyle n!=n\times (n-1)!} （递归定义）

一种便于理解的心理模型，是认为递归定义对对象的定义是按照“先前定义的”同类对象来定义的。例如：你怎样才能移动100个箱子？答案：你首先移动一个箱子，并记下它移动到的位置，然后再去解决较小的问题：你怎样才能移动99个箱子？最终，你的问题将变为怎样移动一个箱子，而这是你已经知道该怎么做的。

如此的定义在数学中十分常见。例如，集合论对自然数的正式定义是：1是一个自然数，每个自然数都有一个后继，这一个后继也是自然数。

以下是另一个可能更有利于理解递归过程的解释：

我们已经完成了吗？如果完成了，返回结果。如果没有这样的 终止条件 ，递归将会永远地继续下去。

如果没有，则 简化 问题，解决较容易的问题，并将结果组装成原始问题的解决办法。然后返回该解决办法。

这样就有一种更有趣的描述：“为了理解递归，则必须首先理解递归。”或者更准确地，按照 安德鲁·普洛特金 （ 英语 ： Andrew Plotkin ） 的解释：“如果你已经知道了什么是递归，只需记住答案。否则，找一个比你更接近侯世达的人；然后让他／她来告诉你什么是递归。”

数学中常见的以递归形式定义的案例参见函数、集合以及分形等。

计算机科学之应用

递归经常被用于解决计算机科学的问题。在一些编程语言（如Scheme、Haskell中），递归是进行循环的一种方法。

举例： 编写一个程序使用递归求n的阶乘

fac0=1facn=n*fac(n-1)main=print(fac10)

数学之应用

谢尔宾斯基三角形-由封闭递归的三角形所形成之碎形

递归定义集

实例：自然数

关于递归定义集的经范型例，可通过自然数来说明

The canonical example of a recursively defined set is given by the natural numbers:

实例：可导出的命题集合

另一个有趣示例为，公理系统中，所有可导出命题之集合

若一个命题为公理，则其为可导出之命题

通过推理规则方式，若一个命题可以从可导出之命题所推论，则其为可导出之命题

满足上述条件之最小集合，为可导出之命题之集合

此集合称为，可导出之命题之集合，因为在数学基础方法中，依非创建性法构建的命题之集合，可能大于由公理系统及推理规则所递归构建出之集合，详细请参见哥德尔不完备定理

有限次分区法

有限次分区法为几何形式之递归，可用以创建类碎形之图案。次分区原则的运作如后所述，从多个已被有限个标签标注的多边形开始，接着每个多边形仅根据其标签，继续细切到更小的多边形，此一细切的过程可不断重复。

参见

分形

差分

递归关系式

塔珀自指公式

免责声明：以上内容版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。感谢每一位辛勤著写的作者，感谢每一位的分享。