尾调用
在计算机学，尾调用是指一个函数里的最后一个动作是返回一个函数的调用结果的情形，即最后一步新调用的返回值直接作為当前函数的返回结果。 特征与简单示例 尾调用可能位于一个函数语法上最后的位置： function foo(data) { a(data); return b(data); } 在这里，a(data)、b(data) 都是函数调用，但是 b(data) 是函式返回前的最后运行的东西，所以也是所谓的尾位置。然后，并非所有的尾调用都必…
标签：#递归
共 18 篇文章
可重入
若一個程序或子程序可以「在任意時刻被中斷然後作業系統調度執行另一段程式碼，這段程式碼又使用了該副程式不會出錯」，則稱其為可重入（reentrant 或 re-entrant）的。即當該副程式正在運作時，執行线程可以再次進入並執行它，仍然可得到符合設計時所預期的結果。與多執行緒併發執行的线程安全不同，可重入強調對單一執行緒執行時重新進入同一個子程序仍然是安全的。 可重入概念是在單執行緒作業系統的時代提出的。一個子程序的重入，可能由於自身原…
原始递归函数
在可计算性理论中，原始递归函数（）对计算的完全的形式化而言是形成重要构造板块的一类函数。它们使用递归和复合作为中心运算来定义，并且是递归函数的严格的子集，它们完全是可计算函数。通过补充允许偏函数和介入无界查找运算可以定义出递归函数的更广泛的类。 通常在数论中研究的很多函数，近似于实数值函数，比如加法、除法、阶乘、指数，找到第 n 个素数等等是原始递归的（Brainerd and Landweber, 1974）。实际上，很难设计不是原始…
递归
是递归的一种视觉形式。图中女性手持的物体中有一幅她本人手持同一物体的小图片，进而小图片中还有更小的一幅她手持同一物体的图片，依此类推。]] 递归（），又译为-{zh-cn:递回; zh-tw:遞歸; zh-hk:遞迴;}-，在数学与计算机科学中，是指在函数的定义中使用函数自身的方法。递归一词还较常用于描述以自相似方法重复事物的过程。例如，当两面镜子相互之间近似平行时，镜中嵌套的图像是以无限递归的形式出现的。也可以理解为自我复制的过程。 …
递归 (计算机科学)
遞迴（）在電腦科學中是指一種通過重複將問題分解為同類的子問題而解決問題的方法。 遞迴式方法可以被用於解決很多的電腦科學問題，因此它是電腦科學中十分重要的一個概念。 絕大多數程式語言支援函式的自呼叫，在這些語言中函式可以通過呼叫自身來進行遞迴。計算理論可以證明遞迴的作用可以完全取代迴圈，因此有很多在函數程式語言（如Scheme）中用递归来取代循环的例子。 電腦科學家尼克勞斯·維爾特如此描述遞迴： 遞迴程式 java public void…
不动点组合子
不动点组合子（，或不动点算子）是计算其他函数的一个不动点的高阶函数。 函数 f 的不动點是將函數應用在輸入值 x 時，會傳回與輸入值相同的值，使得 f(x) = x。例如，0 和 1 是函数 f(x) = x2 的不动点，因为 02 = 0 而 12 = 1。鉴于一阶函数（在简单值比如整数上的函数）的不动点是个一阶值，高阶函数 f 的不动点是另一个函数 g 使得 f(g) = g。那么，不动点算子 fix 的定義是 : x = f\ x…
With (SQL)
在SQL数据库中，处理组织架构、家族树、文件系统等层次模型数据的主要手段有两种：递归公用表表达式（Recursive CTE）与 CONNECT BY子语句。 层级查询（Hierarchical Query）是一种处理层次模型数据的SQL查询，本质上是更通用的“递归不动点查询（Recursive Fixpoint Queries）”的特殊形式，主要用于计算数据的传递闭包（Transitive Closures）。 自标准发布以来，层级查…
互递归
互递归（mutual recursion），是数学与计算机科学中一种递归，指两个数学或计算机对象如函数或数据类型互相定义。互递归在函數程式語言或某些问题域中非常常见，如，其中数据类型是自然地互相递归定义的。 例子 数据类型 采取互递归定义的最重要的基本数据类型是树。这可以用于定义森林（树的列表）: f: [t[1], ..., t[k]] t: v f 森林f由一棵树的列表组成，同时一棵树t由一对：值v与森林f (子树)构成。这种定义是…
Fold (高阶函数)
在函数式编程中，折叠（fold），也称为归约（reduce）、积累（accumulate）、聚集（aggregate）、压缩（compress）或注入（inject），指称一组高阶函数，它们分析递归数据结构并通过使用给定组合运算，将递归的处理它的构成部件、建造一个返回值的结果重组起来。典型的，要向折叠提供一个组合函数，一个数据结构的顶端，和可能的在特定条件下使用的某些缺省值。折叠接着以系统性方式使用这个函数，进行组合这个数据结构的层级中…
递归缩写
递归缩写或递归首字缩写是一种缩写，此类缩写会递归地包含在其全称中。这个词最先在1986年在纸质出版物中出现。 计算机相关实例 在计算机领域黑客社区中一个较早的传统（特别是在麻省理工大学）就是使用幽默地引用自身或其他缩写的缩写。最早的实例可能是在1977年或1978年间出现的TINT（"TINT Is Not "，TINT不是文字编辑器和修正器），它是一个MagicSix的编辑器。这又启发了麻省理工大学的两个Lisp机器编辑器的命名，一个…
超限归纳法
超限归纳法（）是数学归纳法向（大）良序集合比如基數或序数的集合的扩展。 超限归纳 假设只要对于所有的\beta，P(\beta)为真，则P(\alpha)也为真。那么超限归纳告诉我们P对于所有序数为真。 就是说，如果P(\alpha)为真只要P(\beta)对于所有\beta为真，则P(\alpha)对于所有\alpha为真。或者更实用的说：若要证明所有序数\alpha都符合性质P，你可以假定它对于所有更小的\beta已经是成立的。 通…
树的遍历
在计算机科学裡，树的遍历（也称为-{zh-hant:樹的遍歷;zh-hans:树的走访;}-或树的搜索）是一种圖的遍歷，指的是按照某种规则，不重复地访问某种樹的所有节点的过程。具体的访问操作可能是检查节点的值、更新节点的值等。不同的遍历方式，其访问节点的顺序是不一样的。以下虽然描述的是二叉树的遍历算法，但它们也适用于其他树形结构。 遍历的种类 与那些基本上都有标准遍历方式（通常是按线性顺序）的线性数据结构（如链表、一维数组）所不同的是，…
德罗斯特效应
德罗斯特效应（Droste effect），是一种递归的模式，指一张图片部分与整张图片相同，一張有德罗斯特效应的圖片，在其中會有一小部份是和整张图片類似。而這小部份的圖片中，又會有一小部份是和整张图片類似，以此類推。理論上此效應可以一直重覆下去，但實際上此效應會受到圖片分辨率的限制，而且類似的图片大小會以等比數列的方式遞減。德罗斯特效应是一個的可視化例子，也是自指系統的幾何示例，自指系統又是碎形理論的基石。 源起 德罗斯特效应的名稱是由…
递归定义
递归定义是数理逻辑和计算机科学用到的一种定义方式，使用被定义对象的自身来为其下定义（简单说就是自我复制的定义）。递归定义与归纳定义类似，但也有不同之处。递归定义中使用被定义对象自身来定义，而归纳定义是使用被定义对象的已经定义的部分来定义尚未定义的部分。不过，使用递归定义的函数或集合，它们的性质可以用数学归纳法，通过递归定义的内容来证明。 定义方式 大部分的递归定义都由三个部分构成：基本情况的定义，递归法则和递归结束的情况。如果定义的对象…
非直谓性
一个数学定义是非直谓性的，如果它依赖于一个事物的集合，至少其中之一是它自身所定义的事物。换句话说，定义是自引用的。 罗素悖论是著名的非直谓性构造：“不包含自身作为成员的所有集合的集合”。悖论是这种集合是否包含自身——如果包含则根据它的定义它应当不是，而如果不是则根据它的定义它应当是。 但是，著名的数学家拉姆齐争论说，非直谓性定义是绝对需要的。例如，「屋子里最高的人」是非直谓性的，因为它依赖于某個包含其本身的集合，也就是在屋子中所有人的集…
递归语言
在数学、逻辑和计算机科学中，递归语言或遞迴語言是也叫做可判定语言或图灵可判定语言的形式语言类型。所有递归语言的类经常被称为 R。这种语言类型在乔姆斯基层级中没有定义。 定义 递归语言有两种等价的主要定义: 递归语言是在形式语言的字母表上的所有可能的字的集合的递归子集。 设 S ⊆ Σ 是一个语言，M 是一台图灵机， 若对于任何字符串 ω ∈ Σ，有 ω ∈ S 当且仅当 M 接受 ω ω ∉ S 当且仅当 M 拒绝 ω 则称 M 判定语…
共递归
共递归在计算机科学重视一类操作，与递归在范畴论上对偶。因而递归是分析地工作，把数据分解为更小的数据直至达到基本情况。共递归是合成地工作，从基本情况构造出数据。共递归的数据是自己一点一点构造出来的。一个类似但不同的概念是生成式递归（generative recursion）。 共递归常与惰性求值配合，产生一个潜在无穷结构的有限子集。 例子 Corecursion can be understood by contrast with rec…
左遞歸
在電腦科學裡面，左遞歸是一種遞歸的特殊狀況。 在上下文無關文法內裡的說法，若一個非终结符號（non-terminal）r有任何直接的文法規則或者透過多個文法規則，推導出的句型（sentential form）其中最左邊的符號 又會出現r，則我們說這個非终结符號r是左遞歸的。 使用類似的方式我們可以定義出某文法本身是左遞歸的。 定義 "一個文法是左遞歸的，若我們可以找出其中存在某非终结符號A，最終會推導出來的句型(sentential f…