370
个编辑
更改
跳到导航
跳到搜索
第46行：
第46行： − − − − − − − − − − 第80行：
第70行： − − − − − −
→递归数据类型
==递归数据类型==
==递归数据类型==
许多计算机程序必须处理或生成大量的数据。递归是一种表示未知确切大小的数据的技术：程序员可以使用“自引用”技术来定义这些数据。'''<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>''' 这样的方法来表达程序语法。下面的实例语法，适用于表示简单的有乘法和加法的算术表达式：
这意味着一个表达式要么是一个数字，要么是两个表达式的乘积，要么是两个表达式的和。通过在第二行和第三行中递归引用表达式，该语法允许任意复杂的算术表达式，如 <code> (5 * ((3 * 6) + 8)) </code> ，在一个表达式中有多个乘积或和运算。
这意味着一个表达式要么是一个数字，要么是两个表达式的乘积，要么是两个表达式的和。通过在第二行和第三行中递归引用表达式，该语法允许任意复杂的算术表达式，如 <code> (5 * ((3 * 6) + 8)) </code> ，在一个表达式中有多个乘积或和运算。
===协归纳定义的数据和共递归===
===协归纳定义的数据和共递归===
协归纳数据定义规定了可以对一段数据进行怎样的操作；通常，自引用的协归纳定义可以用于定义无限大小的数据结构。
协归纳数据定义规定了可以对一段数据进行怎样的操作；通常，自引用的协归纳定义可以用于定义无限大小的数据结构。
用共归纳定义法来定义无限大小的字符串流，一个可能的例子是这样的：
用共归纳定义法来定义无限大小的字符串流，一个可能的例子是这样的：
字符串流是s这样的对象：
字符串流是s这样的对象：
头部<code>head</code>是字符串，且
头部<code>head</code>是字符串，且
尾部<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个质数的问题，就是能用一个核心递归程序来解决的问题。