2,443
个编辑
更改
跳到导航
跳到搜索
第116行：
第116行： − Recursion that only contains a single self-reference is known as '''{{visible anchor|single recursion}}''', while recursion that contains multiple self-references is known as '''{{visible anchor|multiple recursion}}'''. Standard examples of single recursion include list traversal, such as in a linear search, or computing the factorial function, while standard examples of multiple recursion include [[tree traversal]], such as in a depth-first search. − − Recursion that only contains a single self-reference is known as , while recursion that contains multiple self-references is known as . Standard examples of single recursion include list traversal, such as in a linear search, or computing the factorial function, while standard examples of multiple recursion include tree traversal, such as in a depth-first search. − − Single recursion is often much more efficient than multiple recursion, and can generally be replaced by an iterative computation, running in linear time and requiring constant space. Multiple recursion, by contrast, may require exponential time and space, and is more fundamentally recursive, not being able to be replaced by iteration without an explicit stack. − − Single recursion is often much more efficient than multiple recursion, and can generally be replaced by an iterative computation, running in linear time and requiring constant space. Multiple recursion, by contrast, may require exponential time and space, and is more fundamentally recursive, not being able to be replaced by iteration without an explicit stack. − − Multiple recursion can sometimes be converted to single recursion (and, if desired, thence to iteration). For example, while computing the Fibonacci sequence naively is multiple iteration, as each value requires two previous values, it can be computed by single recursion by passing two successive values as parameters. This is more naturally framed as corecursion, building up from the initial values, tracking at each step two successive values – see [[Corecursion#Examples|corecursion: examples]]. A more sophisticated example is using a [[threaded binary tree]], which allows iterative tree traversal, rather than multiple recursion. − − Multiple recursion can sometimes be converted to single recursion (and, if desired, thence to iteration). For example, while computing the Fibonacci sequence naively is multiple iteration, as each value requires two previous values, it can be computed by single recursion by passing two successive values as parameters. This is more naturally framed as corecursion, building up from the initial values, tracking at each step two successive values – see corecursion: examples. A more sophisticated example is using a threaded binary tree, which allows iterative tree traversal, rather than multiple recursion. 第182行：
第171行： − {{main|Mutual recursion}} − − Most basic examples of recursion, and most of the examples presented here, demonstrate {{anchor|direct recursion}}'''''direct'' recursion''', in which a function calls itself. ''Indirect'' recursion occurs when a function is called not by itself but by another function that it called (either directly or indirectly). For example, if ''f'' calls ''f,'' that is direct recursion, but if ''f'' calls ''g'' which calls ''f,'' then that is indirect recursion of ''f.'' Chains of three or more functions are possible; for example, function 1 calls function 2, function 2 calls function 3, and function 3 calls function 1 again. − − Most basic examples of recursion, and most of the examples presented here, demonstrate direct recursion, in which a function calls itself. Indirect recursion occurs when a function is called not by itself but by another function that it called (either directly or indirectly). For example, if f calls f, that is direct recursion, but if f calls g which calls f, then that is indirect recursion of f. Chains of three or more functions are possible; for example, function 1 calls function 2, function 2 calls function 3, and function 3 calls function 1 again. − − Indirect recursion is also called [[mutual recursion]], which is a more symmetric term, though this is simply a difference of emphasis, not a different notion. That is, if ''f'' calls ''g'' and then ''g'' calls ''f,'' which in turn calls ''g'' again, from the point of view of ''f'' alone, ''f'' is indirectly recursing, while from the point of view of ''g'' alone, it is indirectly recursing, while from the point of view of both, ''f'' and ''g'' are mutually recursing on each other. Similarly a set of three or more functions that call each other can be called a set of mutually recursive functions. − − Indirect recursion is also called mutual recursion, which is a more symmetric term, though this is simply a difference of emphasis, not a different notion. That is, if f calls g and then g calls f, which in turn calls g again, from the point of view of f alone, f is indirectly recursing, while from the point of view of g alone, it is indirectly recursing, while from the point of view of both, f and g are mutually recursing on each other. Similarly a set of three or more functions that call each other can be called a set of mutually recursive functions. 第198行：
第178行： − {{main|Anonymous recursion}} − − Recursion is usually done by explicitly calling a function by name. However, recursion can also be done via implicitly calling a function based on the current context, which is particularly useful for [[anonymous function]]s, and is known as [[anonymous recursion]]. − − Recursion is usually done by explicitly calling a function by name. However, recursion can also be done via implicitly calling a function based on the current context, which is particularly useful for anonymous functions, and is known as anonymous recursion. 第227行：
第202行： − {{see also|Structural recursion}} − Some authors classify recursion as either "structural" or "generative". The distinction is related to where a recursive procedure gets the data that it works on, and how it processes that data:+ − − Some authors classify recursion as either "structural" or "generative". The distinction is related to where a recursive procedure gets the data that it works on, and how it processes that data: − − − + − {{quote|text= 消耗结构化数据的函数通常会将其参数分解为其直接的结构组件，然后对这些组件进行处理。如果其中一个直接组件与输入的数据属于同一类数据，那么这个函数就是递归的。出于这个原因，我们将这些函数称为结构递归函数。|author=Felleisen, Findler, Flatt, and Krishnaurthi|source=''[[How to Design Programs]]'', 2001<ref name="Felleisen HtDP 2001">{{harvnb|Felleisen|Findler|Flatt|Krishnamurthi|2001|loc= [http://www.htdp.org/2003-09-26/Book/curriculum-Z-H-31.html art V "Generative Recursion]}}+ − -- [[用户:Qige96|Ricky]]：这里缺了一个quote模板。正确的显示应该是一段文摘引用：消耗结构化数据的函数通常会将其参数分解为其直接的结构组件，然后对这些组件进行处理。如果其中一个直接组件与输入的数据属于同一类数据，那么这个函数就是递归的。出于这个原因，我们将这些函数称为结构递归函数。 − − Thus, the defining characteristic of a structurally recursive function is that the argument to each recursive call is the content of a field of the original input. Structural recursion includes nearly all tree traversals, including XML processing, binary tree creation and search, etc. By considering the algebraic structure of the natural numbers (that is, a natural number is either zero or the successor of a natural number), functions such as factorial may also be regarded as structural recursion. − − Thus, the defining characteristic of a structurally recursive function is that the argument to each recursive call is the content of a field of the original input. Structural recursion includes nearly all tree traversals, including XML processing, binary tree creation and search, etc. By considering the algebraic structure of the natural numbers (that is, a natural number is either zero or the successor of a natural number), functions such as factorial may also be regarded as structural recursion. 第253行：
第218行： − + − {{quote|text=Many well-known recursive algorithms generate an entirely new piece of data from the given data and recur on it. [[How to Design Programs|''HtDP'' (''How to Design Programs'')]] refers to this kind as generative recursion. Examples of generative recursion include: [[Euclidean algorithm|gcd]], [[quicksort]], [[binary search]], [[mergesort]], [[Newton's method]], [[fractal]]s, and [[adaptive quadrature|adaptive integration]].|author=Matthias Felleisen|source=''Advanced Functional Programming'', 2002<ref name="Felleisen 2002 108">{{Cite book+ − | last = Felleisen − | first = Matthias − | chapter = Developing Interactive Web Programs |chapterurl=https://books.google.com/books?id=Y3GqCAAAQBAJ&pg=PA108 − | date = 2002 − | title = Advanced Functional Programming: 4th International School − | editor-last = Jeuring − | editor-first = Johan − | volume = − | page = 108 − | publisher = Springer − | isbn = 9783540448334 − | url = ftp://nozdr.ru/biblio/kolxo3/Cs/CsLn/Advanced%20Functional%20Programming%204%20conf.,%20AFP%202002%20(LNCS2638,%20Springer,%202003)(ISBN%203540401326)(O)(222s).pdf#page=109 − }} − </ref> − }} − − {{quote|text=许多著名的递归算法都是从给定的数据中生成一个全新的数据，并对其进行递归。HtDP（How to Design Programs）把这种称为生成式递归。生成递归的例子包括：最大公约数、快速排序、二进制搜索、归并排序、牛顿法、分形和自适应集成。|author=Matthias Felleisen|source=''Advanced Functional Programming'', 2002<ref name="Felleisen 2002 108">{{Cite book 第288行：
第236行： − -- [[用户:Qige96|Ricky]]：这里缺了一个quote模板。正确的显示应该是一段文摘引用：许多著名的递归算法都是从给定的数据中生成一个全新的数据，并对其进行递归。HtDP（How to Design Programs）把这种称为生成式递归。生成递归的例子包括：gcd、quicksort、二进制搜索、mergesort、牛顿法、分形和自适应集成。 − − This distinction is important in [[Termination analysis#Termination proof|proving termination]] of a function. − − This distinction is important in proving termination of a function. − − − * All structurally recursive functions on finite ([[Recursive data type|inductively defined]]) data structures can easily be shown to terminate, via [[structural induction]]: intuitively, each recursive call receives a smaller piece of input data, until a base case is reached. − * Generatively recursive functions, in contrast, do not necessarily feed smaller input to their recursive calls, so proof of their termination is not necessarily as simple, and avoiding [[infinite loops]] requires greater care. These generatively recursive functions can often be interpreted as corecursive functions – each step generates the new data, such as successive approximation in Newton's method – and terminating this corecursion requires that the data eventually satisfy some condition, which is not necessarily guaranteed. − * In terms of [[loop variant]]s, structural recursion is when there is an obvious loop variant, namely size or complexity, which starts off finite and decreases at each recursive step. − * By contrast, generative recursion is when there is not such an obvious loop variant, and termination depends on a function, such as "error of approximation" that does not necessarily decrease to zero, and thus termination is not guaranteed without further analysis. −
→递归的类型
===单重递归和多重递归===
===单重递归和多重递归===
只包含单个自引用的递归称为'''<font color="#ff8000"> 单重递归 single recursion</font>'''，而包含多个自引用的递归称为'''<font color="#ff8000"> 多重递归 multiple recursion</font>'''。单重递归的标准例子包括列表遍历，如线性搜索，或计算阶乘函数，而多重递归的标准例子包括'''<font color="#ff8000"> 树遍历tree traversal</font>'''，如深度优先搜索。
只包含单个自引用的递归称为'''<font color="#ff8000"> 单重递归 single recursion</font>'''，而包含多个自引用的递归称为'''<font color="#ff8000"> 多重递归 multiple recursion</font>'''。单重递归的标准例子包括列表遍历，如线性搜索，或计算阶乘函数，而多重递归的标准例子包括'''<font color="#ff8000"> 树遍历tree traversal</font>'''，如深度优先搜索。
单重递归的效率往往比多重递归高得多，一般可以用迭代计算代替，以线性时间运行，需要恒定的空间。而多重递归则可能需要指数级的时间和空间，而且递归得更根本更彻底，在没有明确的堆栈的情况下，不能用迭代来代替。
单重递归的效率往往比多重递归高得多，一般可以用迭代计算代替，以线性时间运行，需要恒定的空间。而多重递归则可能需要指数级的时间和空间，而且递归得更根本更彻底，在没有明确的堆栈的情况下，不能用迭代来代替。
多重递归有时可以转换为单重递归（如果需要，再转换为迭代）。例如，虽然简单地计算斐波那契序列是一种多次迭代，因为算出每个值都需要两个前面的值，但可以通过传递两个连续的值作为参数，通过单重递归来计算。这被定义为共递归会更自然。从初始值开始建立，在每一步都跟踪两个连续的值。一个更复杂的例子是使用线程二叉树，它允许迭代树遍历，而不是多重递归。
多重递归有时可以转换为单重递归（如果需要，再转换为迭代）。例如，虽然简单地计算斐波那契序列是一种多次迭代，因为算出每个值都需要两个前面的值，但可以通过传递两个连续的值作为参数，通过单重递归来计算。这被定义为共递归会更自然。从初始值开始建立，在每一步都跟踪两个连续的值。一个更复杂的例子是使用线程二叉树，它允许迭代树遍历，而不是多重递归。
===间接递归===
===间接递归===
大多数递归的基本例子，以及这里介绍的大多数例子，都是直接递归，即一个函数调用自己。间接递归是指一个函数不是被它自己调用，而是被它调用的另一个函数（直接或间接）调用。例如，如果f调用f，那是直接递归，但如果f调用g，而g又调用f，那就是f的间接递归。三个或更多的函数链是可能的，例如，函数1调用函数2，函数2调用函数3，函数3再调用函数1。
大多数递归的基本例子，以及这里介绍的大多数例子，都是直接递归，即一个函数调用自己。间接递归是指一个函数不是被它自己调用，而是被它调用的另一个函数（直接或间接）调用。例如，如果f调用f，那是直接递归，但如果f调用g，而g又调用f，那就是f的间接递归。三个或更多的函数链是可能的，例如，函数1调用函数2，函数2调用函数3，函数3再调用函数1。
间接递归也叫'''<font color="#ff8000">互递归 mutual recursion</font>'''，这是一个比较对称的术语，不过这只是强调的不同，而不是概念的不同。也就是说，如果f调用g，然后g又调用f，而f又调用g，单从f的角度看，f是间接递归，而单从g的角度看，是间接递归，而从两者的角度看，f和g是互递归的。同理，三个或三个以上函数相互调用的函数集也可以称为互递归函数集。
间接递归也叫'''<font color="#ff8000">互递归 mutual recursion</font>'''，这是一个比较对称的术语，不过这只是强调的不同，而不是概念的不同。也就是说，如果f调用g，然后g又调用f，而f又调用g，单从f的角度看，f是间接递归，而单从g的角度看，是间接递归，而从两者的角度看，f和g是互递归的。同理，三个或三个以上函数相互调用的函数集也可以称为互递归函数集。
===匿名递归===
===匿名递归===
递归通常是通过显式调用一个函数的名字来实现的。但是，递归也可以通过根据当前上下文隐式调用函数来完成，这对于匿名函数特别有用，被称为'''<font color="#ff8000"> 匿名递归 anonymous recursion</font>'''。
递归通常是通过显式调用一个函数的名字来实现的。但是，递归也可以通过根据当前上下文隐式调用函数来完成，这对于匿名函数特别有用，被称为'''<font color="#ff8000"> 匿名递归 anonymous recursion</font>'''。
===结构递归与生成递归===
===结构递归与生成递归===
一些作者将递归分为 "结构性 "或 "生成性"。这种区别与递归程序从哪里获得它所处理的数据以及它如何处理这些数据有关：
一些作者将递归分为 "结构性 "或 "生成性"。这种区别与递归程序从哪里获得它所处理的数据以及它如何处理这些数据有关。
{{quote|text=[Functions that consume structured data] typically decompose their arguments into their immediate structural components and then process those components. If one of the immediate components belongs to the same class of data as the input, the function is recursive. For that reason, we refer to these functions as (STRUCTURALLY) RECURSIVE FUNCTIONS.|author=Felleisen, Findler, Flatt, and Krishnaurthi|source=''[[How to Design Programs]]'', 2001<ref name="Felleisen HtDP 2001">{{harvnb|Felleisen|Findler|Flatt|Krishnamurthi|2001|loc= [http://www.htdp.org/2003-09-26/Book/curriculum-Z-H-31.html art V "Generative Recursion]}}
{{quote|text=[Functions that consume structured data] typically decompose their arguments into their immediate structural components and then process those components. If one of the immediate components belongs to the same class of data as the input, the function is recursive. For that reason, we refer to these functions as (STRUCTURALLY) RECURSIVE FUNCTIONS.|author=Felleisen, Findler, Flatt, and Krishnaurthi|source=''[[How to Design Programs]]'', 2001<ref name="Felleisen HtDP 2001">{{harvnb|Felleisen|Findler|Flatt|Krishnamurthi|2001|loc= [http://www.htdp.org/2003-09-26/Book/curriculum-Z-H-31.html art V "Generative Recursion]}}
</ref>}}
</ref>}}
''消耗结构化数据的函数通常会将其参数分解为其直接的结构组件，然后对这些组件进行处理。如果其中一个直接组件与输入的数据属于同一类数据，那么这个函数就是递归的。出于这个原因，我们将这些函数称为结构递归函数。
——————Felleisen, Findler, Flatt, and Krishnaurthi, How to Design Programs, 2001''<ref name="Felleisen HtDP 2001">{{harvnb|Felleisen|Findler|Flatt|Krishnamurthi|2001|loc= [http://www.htdp.org/2003-09-26/Book/curriculum-Z-H-31.html art V "Generative Recursion]}}
</ref>}}
</ref>}}
因此，结构递归函数的定义特征是，每次递归调用的参数是原始输入的某一部分的内容。结构递归几乎包括所有的树形遍历，包括XML处理、二进制树的创建和搜索等。考虑到自然数的代数结构（即自然数要么是零，要么是自然数的继任者），阶乘等函数也可视为结构递归。
因此，结构递归函数的定义特征是，每次递归调用的参数是原始输入的某一部分的内容。结构递归几乎包括所有的树形遍历，包括XML处理、二进制树的创建和搜索等。考虑到自然数的代数结构（即自然数要么是零，要么是自然数的继任者），阶乘等函数也可视为结构递归。
生成递归是替代方法：
生成递归是替代方法：
''许多著名的递归算法都是从给定的数据中生成一个全新的数据，并对其进行递归。HtDP（How to Design Programs）把这种称为生成式递归。生成递归的例子包括：最大公约数、快速排序、二进制搜索、归并排序、牛顿法、分形和自适应集成。
——————Matthias Felleisen, Advanced Functional Programming, 2002'' <ref name="Felleisen 2002 108">{{Cite book
| last = Felleisen
| last = Felleisen
| first = Matthias
| first = Matthias
}}
}}
这种区别在证明函数的终止性时很重要。
这种区别在证明函数的终止性时很重要。
* 通过结构归纳，可以很容易地证明所有有限（归纳定义的）数据结构上的结构递归函数的终止：直观地看，每次递归调用都会接收较小的输入数据，直到达到一个基本情况。
* 通过结构归纳，可以很容易地证明所有有限（归纳定义的）数据结构上的结构递归函数的终止：直观地看，每次递归调用都会接收较小的输入数据，直到达到一个基本情况。