更改

跳到导航 跳到搜索

递归 (查看源代码)

2020年12月12日 (六) 19:46的版本

添加2,185字节 、 2020年12月12日 (六) 19:46
→‎递归的类型
第236行： 第236行：  
多重递归有时可以转换为单重递归（如果需要，再转换为迭代）。例如，虽然简单地计算斐波那契序列是一种多次迭代，因为算出每个值都需要两个前面的值，但可以通过传递两个连续的值作为参数，通过单重递归来计算。这被定义为共递归会更自然。从初始值开始建立，在每一步都跟踪两个连续的值。一个更复杂的例子是使用线程二叉树，它允许迭代树遍历，而不是多重递归。
 
多重递归有时可以转换为单重递归（如果需要，再转换为迭代）。例如，虽然简单地计算斐波那契序列是一种多次迭代，因为算出每个值都需要两个前面的值，但可以通过传递两个连续的值作为参数，通过单重递归来计算。这被定义为共递归会更自然。从初始值开始建立，在每一步都跟踪两个连续的值。一个更复杂的例子是使用线程二叉树，它允许迭代树遍历，而不是多重递归。
   −
下面是计算斐波那契数列第n项得python代码，分别使用多重递归和单重递归实现。
+
下面是计算斐波那契数列第n项的python代码，分别使用多重递归和单重递归实现。
   −
  --[[用户:Qige96|Ricky]]代码实现并未经过大量测试，可能会有bug，如发现请在微信群@我
+
  --[[用户:Qige96|Ricky]]：代码实现并未经过大量测试，可能会有bug，如发现请在微信群@我
    
<syntaxhighlight lang="python">
 
<syntaxhighlight lang="python">
 +
"""
 +
Author: Ricky
 +
Email: rickyzhu@foxmail.com
 +
"""
 +
 
def fib_MR(n):
 
def fib_MR(n):
 
     "Multiple Recursion computing the n-th Fibonacci term"
 
     "Multiple Recursion computing the n-th Fibonacci term"
第249行： 第254行：  
         return 1
 
         return 1
 
     else:
 
     else:
−
         return fib_MR(n-1) + fib_MR(n-2)
+
         return fib_MR(n-1) + fib_MR(n-2) # 双重递归
    
def fib_SR(n):
 
def fib_SR(n):
第262行： 第267行：  
             return 1, 1
 
             return 1, 1
 
         else:
 
         else:
−
             An_1, An_2 = _fib_SR(n-1)
+
             An_1, An_2 = _fib_SR(n-1) # 单重递归
 
             return An_2 + An_1, An_1
 
             return An_2 + An_1, An_1
   第277行： 第282行：  
</syntaxhighlight>
 
</syntaxhighlight>
   −
===Indirect recursion===
+
===间接递归===
−
间接递归
+
 
 
{{main|Mutual recursion}}
 
{{main|Mutual recursion}}
   第291行： 第296行：  
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.
   −
间接递归也叫'''<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是互递归的。同理，三个或三个以上函数相互调用的函数集也可以称为互递归函数集。
 +
 
 +
===匿名递归===
   −
===Anonymous recursion===
  −
匿名递归
   
{{main|Anonymous recursion}}
 
{{main|Anonymous recursion}}
   第301行： 第306行：  
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.
 
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.
   −
递归通常是通过显式调用一个函数的名字来实现的。但是，递归也可以通过根据当前上下文隐式调用函数来完成，这对于匿名函数特别有用，被称为'''<font color="#ff8000"> 匿名递归anonymous recursion</font>'''。
+
递归通常是通过显式调用一个函数的名字来实现的。但是，递归也可以通过根据当前上下文隐式调用函数来完成，这对于匿名函数特别有用，被称为'''<font color="#ff8000"> 匿名递归 anonymous recursion</font>'''。
   −
===Structural versus generative recursion===
+
下面是计算斐波那契数列第10项的javascript代码，通过匿名递归实现。
−
结构递归与生成递归
+
 
 +
--[[用户:Qige96|Ricky]]：代码实现并未经过大量测试，可能会有bug，如发现请在微信群@我
 +
 
 +
<syntaxhighlight lang="javascript">
 +
/*
 +
* @author: Ricky
 +
* @email: rickyzhu@foxmail.com
 +
*/
 +
 
 +
(function (n) {
 +
  if (n <= 2) {
 +
    return n - 1;
 +
  } else {
 +
    return  arguments.callee(n - 1) + arguments.callee(n - 2);
 +
  }
 +
})(10); // 计算斐波那契数列第10项
 +
</syntaxhighlight>
 +
 
 +
===结构递归与生成递归===
 +
 
{{see also|Structural recursion}}
 
{{see also|Structural recursion}}
   第316行： 第340行：  
</ref>}}
 
</ref>}}
   −
{{quote|text= 消耗结构化数据的函数通常会将其参数分解为其直接的结构组件，然后对这些组件进行处理。如果其中一个直接组件与输入的数据属于同一类数据，那么这个函数就是递归的。出于这个原因，我们将这些函数称为结构递归函数。
+
{{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]}}
−
—  Felleisen，Findler，Flatt和Krishnaurthi，《如何设计程序》，2001年
+
</ref>}}
 +
 
 +
 
 +
-- [[用户: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.
第323行： 第350行：  
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.
   −
因此，结构递归函数的定义特征是，每次递归调用的参数是原始输入的某个字段的内容。结构递归几乎包括所有的树形遍历，包括XML处理、二进制树的创建和搜索等。考虑到自然数的代数结构（即自然数要么是零，要么是自然数的继任者），阶乘等函数也可视为结构递归。
+
因此，结构递归函数的定义特征是，每次递归调用的参数是原始输入的某一部分的内容。结构递归几乎包括所有的树形遍历，包括XML处理、二进制树的创建和搜索等。考虑到自然数的代数结构（即自然数要么是零，要么是自然数的继任者），阶乘等函数也可视为结构递归。
    
'''{{visible anchor|Generative recursion}}''' is the alternative:
 
'''{{visible anchor|Generative recursion}}''' is the alternative:
第344行： 第371行：  
}}
 
}}
 
</ref>
 
</ref>
 +
}}
    +
{{quote|text=许多著名的递归算法都是从给定的数据中生成一个全新的数据，并对其进行递归。HtDP（How to Design Programs）把这种称为生成式递归。生成递归的例子包括：最大公约数、快速排序、二进制搜索、归并排序、牛顿法、分形和自适应集成。|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>
 
}}
 
}}
   −
许多著名的递归算法都是从给定的数据中生成一个全新的数据，并对其进行递归。HtDP（How to Design Programs）把这种称为生成式递归。生成递归的例子包括：gcd、quicksort、二进制搜索、mergesort、牛顿法、分形和自适应集成。
+
-- [[用户:Qige96|Ricky]]：这里缺了一个quote模板。正确的显示应该是一段文摘引用：许多著名的递归算法都是从给定的数据中生成一个全新的数据，并对其进行递归。HtDP（How to Design Programs）把这种称为生成式递归。生成递归的例子包括：gcd、quicksort、二进制搜索、mergesort、牛顿法、分形和自适应集成。
   −
- Matthias Felleisen，《高级函数式编程》，2002年。
      
This distinction is important in [[Termination analysis#Termination proof|proving termination]] of a function.  
 
This distinction is important in [[Termination analysis#Termination proof|proving termination]] of a function.  
第356行： 第398行：     
这种区别在证明函数的终止性时很重要。
 
这种区别在证明函数的终止性时很重要。
 +
    
* 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.  
 
* 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.
 
* 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.  
 
* 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.
   −
就循环变体而言，结构性递归是指存在明显的循环变体，即大小或复杂度，它开始时是有限的，并在每个递归步骤中减少。
  −
  −
* 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.
     −
与此相反，生成递归是指没有这样明显的循环变体，终止取决于一个函数，如 "近似误差"，而这个函数不一定会降为零，因此，如果不作进一步的分析，就不能保证终止。
+
* 通过结构归纳，可以很容易地证明所有有限（归纳定义的）数据结构上的结构递归函数的终止：直观地看，每次递归调用都会接收较小的输入数据，直到达到一个基本情况。
 +
* 相比之下，生成递归函数不一定会向其递归调用提供较小的输入，因此对其终止的证明不一定那么简单，避免无限递归需要更加谨慎。这些生成式递归函数通常可以解释为共递归函数——每一步都会产生新的数据，比如牛顿方法中的逐次逼近——而终止这种核心递归需要数据最终满足某个条件，而这个条件不一定能保证被满足。
 +
* 就循环变体而言，结构性递归是指存在明显的循环变体，即大小或复杂度，它开始时是有限的，并在每个递归步骤中减少。
 +
* 与此相反，生成递归是指没有这样明显的循环变体，终止取决于一个函数，如 "近似误差"，而这个函数不一定会降为零，因此，如果不作进一步的分析，就不能保证终止。
    
==Recursive programs==
 
==Recursive programs==
Qige96
385

个编辑

取自“https://wiki.swarma.org/index.php/特殊:移动版差异/19980”

导航菜单