2,443
个编辑
更改
跳到导航
跳到搜索
第57行：
第57行： − Many [[computer program]]s must process or generate an arbitrarily large quantity of [[data]]. Recursion is a technique for representing data whose exact size is unknown to the [[programmer]]: the programmer can specify this data with a [[Self reference|self-referential]] definition. There are two types of self-referential definitions: inductive and [[Coinduction|coinductive]] definitions. − − {{further|Algebraic data type}} − − Many computer programs must process or generate an arbitrarily large quantity of data. Recursion is a technique for representing data whose exact size is unknown to the programmer: the programmer can specify this data with a self-referential definition. There are two types of self-referential definitions: inductive and coinductive definitions. 第68行：
第63行： − {{main|Recursive data type}} − − An inductively defined recursive data definition is one that specifies how to construct instances of the data. For example, [[linked list]]s can be defined inductively (here, using [[Haskell (programming language)|Haskell]] syntax): − An inductively defined recursive data definition is one that specifies how to construct instances of the data. For example, linked lists can be defined inductively (here, using Haskell syntax): 第78行：
第69行： − The code above specifies a list of strings to be either empty, or a structure that contains a string and a list of strings. The self-reference in the definition permits the construction of lists of any (finite) number of strings. − The code above specifies a list of strings to be either empty, or a structure that contains a string and a list of strings. The self-reference in the definition permits the construction of lists of any (finite) number of strings. − − Another example of inductive [[definition]] is the [[natural numbers]] (or positive [[integers]]): − − Another example of inductive definition is the natural numbers (or positive integers): − <pre>A natural number is either 1 or n+1, where n is a natural number.</pre> − − − Similarly recursive [[definition]]s are often used to model the structure of [[expression (programming)|expressions]] and [[statement (programming)|statements]] in programming languages. Language designers often express grammars in a syntax such as [[Backus–Naur form]]; here is such a grammar, for a simple language of arithmetic expressions with multiplication and addition: − − Similarly recursive definitions are often used to model the structure of expressions and statements in programming languages. Language designers often express grammars in a syntax such as Backus–Naur form; here is such a grammar, for a simple language of arithmetic expressions with multiplication and addition: 第109行：
第88行： − − This says that an expression is either a number, a product of two expressions, or a sum of two expressions. By recursively referring to expressions in the second and third lines, the grammar permits arbitrarily complex arithmetic expressions such as <code>(5 * ((3 * 6) + 8))</code>, with more than one product or sum operation in a single expression. − − This says that an expression is either a number, a product of two expressions, or a sum of two expressions. By recursively referring to expressions in the second and third lines, the grammar permits arbitrarily complex arithmetic expressions such as <code>(5 * ((3 * 6) + 8))</code>, with more than one product or sum operation in a single expression. 第118行：
第93行： − − {{main|Coinduction|Corecursion}} − A coinductive data definition is one that specifies the operations that may be performed on a piece of data; typically, self-referential coinductive definitions are used for data structures of infinite size. − − A coinductive data definition is one that specifies the operations that may be performed on a piece of data; typically, self-referential coinductive definitions are used for data structures of infinite size. − A coinductive definition of infinite [[stream (computer science)|streams]] of strings, given informally, might look like this: − − A coinductive definition of infinite streams of strings, given informally, might look like this: − A stream of strings is an object s such that: − head(s) is a string, and − tail(s) is a stream of strings. 第141行：
第105行： − This is very similar to an inductive definition of lists of strings; the difference is that this definition specifies how to access the contents of the data structure—namely, via the [[accessor]] functions <code>head</code> and <code>tail</code>—and what those contents may be, whereas the inductive definition specifies how to create the structure and what it may be created from. − − Corecursion is related to coinduction, and can be used to compute particular instances of (possibly) infinite objects. As a programming technique, it is used most often in the context of [[lazy evaluation|lazy]] programming languages, and can be preferable to recursion when the desired size or precision of a program's output is unknown. In such cases the program requires both a definition for an infinitely large (or infinitely precise) result, and a mechanism for taking a finite portion of that result. The problem of computing the first n [[prime numbers]] is one that can be solved with a corecursive program (e.g. [[Fold (higher-order function)#Examples|here]]). − − Corecursion is related to coinduction, and can be used to compute particular instances of (possibly) infinite objects. As a programming technique, it is used most often in the context of lazy programming languages, and can be preferable to recursion when the desired size or precision of a program's output is unknown. In such cases the program requires both a definition for an infinitely large (or infinitely precise) result, and a mechanism for taking a finite portion of that result. The problem of computing the first n prime numbers is one that can be solved with a corecursive program (e.g. here).
→递归数据类型
==递归数据类型==
==递归数据类型==
许多计算机程序必须处理或生成大量的数据。递归是一种表示未知确切大小的数据的技术：程序员可以使用“自引用”技术来定义这些数据。'''<font color="#ff8000"> 自引用self-referential</font>'''定义有两种类型: 归纳（inductive）定义和协归纳（coinductive）定义。
许多计算机程序必须处理或生成大量的数据。递归是一种表示未知确切大小的数据的技术：程序员可以使用“自引用”技术来定义这些数据。'''<font color="#ff8000"> 自引用self-referential</font>'''定义有两种类型: 归纳（inductive）定义和协归纳（coinductive）定义。
===归纳定义的数据===
===归纳定义的数据===
归纳定义是指定如何构造数据实例的定义。例如，字符串列表可以被归纳定义为（这里使用Haskell语法）：
归纳定义是指定如何构造数据实例的定义。例如，字符串列表可以被归纳定义为（这里使用Haskell语法）：
<syntaxhighlight lang="haskell">data ListOfStrings = EmptyList | Cons String ListOfStrings</syntaxhighlight>
<syntaxhighlight lang="haskell">data ListOfStrings = EmptyList | Cons String ListOfStrings</syntaxhighlight>
上面的代码指定了一个字符串列表，要么是空的，要么是包含一个字符串和一个字符串列表的结构。定义中的自引用允许构建任意（有限）数量的字符串列表。
上面的代码指定了一个字符串列表，要么是空的，要么是包含一个字符串和一个字符串列表的结构。定义中的自引用允许构建任意（有限）数量的字符串列表。
归纳定义的另一个例子是'''<font color="#ff8000">自然数 natural numbers</font>'''（或正整数）：
归纳定义的另一个例子是'''<font color="#ff8000">自然数 natural numbers</font>'''（或正整数）：
<pre>一个自然数是1或 n + 1，其中 n 是一个自然数。</pre>
<pre>一个自然数是1或 n + 1，其中 n 是一个自然数。</pre>
类似的递归定义也经常被用来对编程语言中表达式和语句的结构建模。语言设计者经常用'''<font color="#ff8000"> BNF： Backus–Naur form</font>''' 这样的方法来表达程序语法。下面的实例语法，适用于表示简单的有乘法和加法的算术表达式：
类似的递归定义也经常被用来对编程语言中表达式和语句的结构建模。语言设计者经常用'''<font color="#ff8000"> BNF： Backus–Naur form</font>''' 这样的方法来表达程序语法。下面的实例语法，适用于表示简单的有乘法和加法的算术表达式：
| (<expr> + <expr>)
| (<expr> + <expr>)
</syntaxhighlight>
</syntaxhighlight>
这意味着一个表达式要么是一个数字，要么是两个表达式的乘积，要么是两个表达式的和。通过在第二行和第三行中递归引用表达式，该语法允许任意复杂的算术表达式，如 <code> (5 * ((3 * 6) + 8)) </code> ，在一个表达式中有多个乘积或和运算。
这意味着一个表达式要么是一个数字，要么是两个表达式的乘积，要么是两个表达式的和。通过在第二行和第三行中递归引用表达式，该语法允许任意复杂的算术表达式，如 <code> (5 * ((3 * 6) + 8)) </code> ，在一个表达式中有多个乘积或和运算。
===协归纳定义的数据和共递归===
===协归纳定义的数据和共递归===
协归纳数据定义规定了可以对一段数据进行怎样的操作；通常，自引用的协归纳定义可以用于定义无限大小的数据结构。
协归纳数据定义规定了可以对一段数据进行怎样的操作；通常，自引用的协归纳定义可以用于定义无限大小的数据结构。
用共归纳定义法来定义无限大小的字符串流，一个可能的例子是这样的：
用共归纳定义法来定义无限大小的字符串流，一个可能的例子是这样的：
字符串流是s这样的对象：
字符串流是s这样的对象：
尾部<code>tail</code>是字符串流。
尾部<code>tail</code>是字符串流。
这与字符串列表的归纳定义非常相似；不同的是，这个定义指定了如何访问数据结构的内容，即通过访问函数的头<code>head</code>和尾<code>tail</code>以及这些内容可能是什么，而归纳定义则指定了如何创建结构以及它可能是由什么创建的。
这与字符串列表的归纳定义非常相似；不同的是，这个定义指定了如何访问数据结构的内容，即通过访问函数的头<code>head</code>和尾<code>tail</code>以及这些内容可能是什么，而归纳定义则指定了如何创建结构以及它可能是由什么创建的。
共递归与协归纳相关，可以用来计算无限规模的对象。作为一种编程技术，它最常被用于 '''<font color="#f668800">惰性编程语言 lazy programming language</font>'''中，当程序输出的大小或精度未知时，使用共递归会比递归更合适。在这种情况下，程序既需要一个无限大（或无限精确）结果的定义，又需要一个取该结果有限部分的机制。计算出前n个质数的问题，就是能用一个核心递归程序来解决的问题。
共递归与协归纳相关，可以用来计算无限规模的对象。作为一种编程技术，它最常被用于 '''<font color="#f668800">惰性编程语言 lazy programming language</font>'''中，当程序输出的大小或精度未知时，使用共递归会比递归更合适。在这种情况下，程序既需要一个无限大（或无限精确）结果的定义，又需要一个取该结果有限部分的机制。计算出前n个质数的问题，就是能用一个核心递归程序来解决的问题。