在数理逻辑和计算机科学中，递归函数或μ-递归函数是一类从自然数到自然数的函数。直觉上递归函数是"可计算的"。事实上在可计算性理论中已经证明了它确实是图灵机的可计算函数。递归函数与原始递归函数相关，而且递归函数的归纳定义（见下）建立在原始递归函数之上。但不是所有递归函数都是原始递归函数——其中最著名的是阿克曼函数。...

递归（英語：Recursion），又译为递回，在数学与计算机科学中，是指在函数的定义中使用函数自身的方法。递归一词还较常用于描述以自相似方法重复事物的过程。例如，当两面镜子相互之间近似平行时，镜中嵌套的图像是以无限递归的形式出现的。也可以理解为自我复制的过程。 在数学和计算机科学中，递归...

函数g返回要么常量1，要么函数f对n-1的n次应用。使用ISZERO谓词，和上面描述的布尔和代数定义，函数g可以用lambda演算来定义。 但是，g自身仍然不是递归的；为了使用g来建立递归函数，作为参数传递给g的f函数必须有特殊的性质。也就是说，作为参数传递的f函数必须展开为调用带有一个参数的函数g...

在可计算性理论中，原始递归函数（英語：primitive recursive functions）对计算的完全的形式化而言是形成重要构造板块的一类函数。它们使用递归和复合作为中心运算来定义，并且是递归函数的严格的子集，它们完全是可计算函数。通过补充允许偏函数和介入无界查找运算可以定义出递归函数的更广泛的类。...

絕大多數程式語言支援函式的自呼叫，在這些語言中函式可以通過呼叫自身來進行遞迴。計算理論可以證明遞迴的作用可以完全取代迴圈，因此有很多在函數程式語言（如Scheme）中用递归来取代循环的例子。 電腦科學家尼克勞斯·維爾特如此描述遞迴： 遞迴的強大之處在於它允許使用者用有限的語句描述無限的物件。因此，在電...

在计算机学裡，尾调用是指一个函数里的最后一个动作是返回一个函数的调用结果的情形，即最后一步新调用的返回值直接作為当前函数的返回结果。此时，该尾部调用位置被称为尾位置。尾调用中有一种重要而特殊的情形叫做尾递归。经过适当处理，尾递归形式的函数的运行效率可以被极大地优化。尾调用原则上都可以通过简化函数...

阿克曼函數是非原始递归函数的例子；它需要兩個自然數作為輸入值，輸出一個自然數。它的輸出值增長速度非常高。 1920年代後期，數學家大衛·希爾伯特的學生Gabriel Sudan和威廉·阿克曼，當時正研究計算的基礎。Sudan發明了一個遞歸卻非原始遞歸的苏丹函数。1928年，阿克曼又獨立想出了另一個遞歸卻非原始遞歸的函數。...

計算數也被稱為遞迴數、遞迴實數或可計算實數。 等效的定義可以用递归函数、图灵机及λ演算等演算法的形式表示法而得。可計算數形成實閉域，可以在許多數學應用上取代实数。 如果一個實數 a {\displaystyle a} 能被某個可計算函數 f : N → Z {\displaystyle f:\mathbb...

互递归是数学与计算机科学中一种递归，指两个数学或计算机对象如函数或数据类型互相定义。互递归在函數程式語言或某些问题域中非常常见，如递归下降分析器（英语：recursive descent parser），其中数据类型是自然地互相递归定义的。 采取互递归定义的最重要的基本数据类型是树。这可以用于定义森林（树的列表）:...

(1952) p. 279.）。 则五个原始递归算子加上无界但完全μ算子给出了 Kleene 所称的“一般”递归函数（就是由六个递归函数定义的全函数）。 (iii) 在偏递归函数的上下文中：假设关系 R 成立，当且仅当一个偏序递归函数收敛于零。并假设这个偏递归函数收敛（到某个东西不一定为零）只要 μ y...

递归可以有下列解释： 递归 - 一种函数的定义中使用函数自身的方法 递归语言 - 在数学、逻辑和计算机科学中的一种可判定语言 递归集合 - 一种可判定集合 递归缩写 - 一种在全称中引用它自己的缩写方式 递归 (计算机科学) 递归可枚举集合 递归可枚举语言 原始递归函数...

邱奇以及数学家斯蒂芬·科尔·克莱尼和逻辑学家J. Barkley Rosser（英语：J. Barkley Rosser）一起定义了一类函数， 这种函数的值可使用递归方法计算。 这三个理论在直觉上似乎是等价的--它们都定义了同一类函数。因此，计算机科学家和数学家们相信，可计算性的精确定义已经出现。邱奇-图灵论题的非正式表述说：如果某...

递归函数的相同定义可用克莱尼递归定理（英语：Kleene's recursion theorem）在可计算性理论中给出。这些结果并不是等价的定理，克拉斯特尔－塔斯基定理是个比那用于指称语义的更强的结果。然而，它却与丘奇－图灵论题的直观含义相同：一个递归函数可描述為特定泛函的最小不动点，将函数映射至函数。...

sinc函数（英語：sinc function）是一種函數，在不同的領域它有不同的定義。數學家們用符號 s i n c ( x ) {\displaystyle \mathrm {sinc} (x)\,} 表示這種函數。 sinc函数可以被定義为归一化的或者非归一化的，不過兩種函數都是正弦函数和单调的递减函数...

一个不需要预编译步骤的C++递归下降解析器生成器框架 parboiled (Java)（英语：parboiled (Java)） – 一个用于 Java 的递归下降 PEG 解析库 文法解析组合子 – 一个用于组合式解析的高阶函数，是一种对递归递归解析器设计进行因子化的方法 解析表达文法 – 另一种代表递归下降文法的形式 递归上升解析器（英语：Recursive...

{\displaystyle g} 和 h {\displaystyle h} 二者都有比 f {\displaystyle f} 少的参数，可以得出递归的使用这个过程将完成于只有一个变量的函数。 例如，让我们构造一个 f ( x , y ) = x ∨ y {\displaystyle f(x,y)=x\lor y} （逻辑或）的ANF：...

(\lambda x.f\ (x\ x))} 則允许匿名函数足夠逹成递归的作用，即递归函数。應用於帶有一個變量的函數，Y組合子通常不會終止。將 Y組合子應用於二或更多個變量的函數，會獲得更有趣的結果。第二個變量可當作計數器或索引。由此產生的函數行為，表現出如命令式語言中一個while或for迴圈。 這個組合子也是...

。这些函数也叫做偏递归函数。在可计算理论中，函数的定义域是函数被定义在其上的所有输入的集合。 定义在所有参数上的函数叫做全函数。如果可计算函数是全函数，它叫做全可计算函数或全递归函数。 有很多等价方式定义可计算函数的类。为了具体，本文余下部分将假定可计算函数已经被定义可以被图灵机计算的那些偏函数...

da演算的类型只是基本类型（或类型变量）和函数类型 σ → τ {\displaystyle \sigma \to \tau } 。系统T向简单类型lambda演算扩展了自然数类型和更高阶的原始递归函数；在这个系统中在可证明在皮亚诺算术中是递归函数的所有函数都是可定义的。系统F通过在所有类型上的全称...

递归定义的内容来证明。 大部分的递归定义都由三个部分构成：基本情况的定义，递归法则和递归结束的情况。如果定义的对象是无限的，那么可以省略第三个部分（递归结束的情况）。比如说，可以用递归定义的方式来定义如下的一个自然数集上的函数 f {\displaystyle f}...

分类算法的一种方法是通过实现手段。 递归 递归算法是一种重复调用（引用）自身的算法，直到某个条件（也称为终止条件）匹配，这是函数式编程常用的方法。迭代算法使用循环之类的重复构造，有时使用堆栈之类的附加数据结构来解决给定的问题。有些问题自然适合于这种或那种实现。例如，使用递归实现可以很好地理解河内的塔。每个递归...

A\times B} 是递归集合。集合 A {\displaystyle A} 是递归集合，当且仅当 A {\displaystyle A} 和 A {\displaystyle A} 的补集是递归可枚举集合。一个递归集合在全可计算函数下的原像（preimage）是递归集合。 递归可枚举集合 递归函数...

递归论或可计算性理论，是一个数理逻辑分支。它起源于可计算函数和图灵度的研究。它的领域增长为包括一般性的可计算性和可定义性的研究。在这些领域中，这门理论同证明论和能行描述集合论（effective descriptive set theory）有所重叠。 数理逻辑中的可计算性理论家经常研究相对可计算性...

Logik，1949 1958年《递归函数论》，科学出版社，13031·826；译自罗莎·培特（德语：Rózsa Péter）所著之Rekursive Funtionen，1951 1965年《数理逻辑导论》，上海科学技术出版社，13119·589 1965年《递归函数论》，上海科学技术出版社，13119·674...

停机測試悖论：计算机里面有个测试程序，这个测试程序的原则是，当有程序不递归调用自己（输出停机），测试程序就调用它（对应不停机）。如果程序递归调用自己（对应不停机），测试程序就不调用它（对应停机）。无法回答的问题是，测试程序递归调用自己嗎？ 柴廷常數 理发师悖论 哥德尔不完备定理 未解決的數學問題 pp...

数学中，後繼函數 或 後繼運算是使 S ( n ) = n + 1 {\displaystyle S(n)=n+1} 的原始递归函数S，其中n為自然数。例如， S(1)=2， S(2)=3。后继函數也称为zeration，因為它是第零个超運算： H 0 ( a ,   b ) = 1 + b {\displaystyle...

根据f(M)与y的关系执行 L = M 或 R = M，进入下一轮循环 在函数编程语言中，迭代可以用递归技巧来。 下述例子用Scheme语言写成。注意它是一个递归（迭代的特例），因为函数iter在解决问题时调用了自身。特别地，它使用了尾部递归，一种能被Scheme这样的编程语言完备支持的技巧，因此程序不会占用大量堆栈。...

编译器递归测试，是一種由计算机科学家高德纳提出，用來评价ALGOL 60编程语言实现的手段。该测试的目的是识别出能够正确实现“递归和非本地引用”的编译器。 目前只有少数的ALGOL 60解释器能够正确处理递归和非本地引用，所以我认为設計一段小程序去测试编译器的递归...

苏丹函数（Sudan function），是递归函数，但如同阿克曼函数，不能通過μ算子定義更廣泛的偏遞歸函數類，因而不是原始递归函数。苏丹函数是第一个具有此属性的函数。 它于1927年由大卫·希尔伯特的学生羅馬尼亞数学家加布里埃尔苏丹发现并发表。 F 0 ( x , y ) = x + y F n...

函数式编程的基础。 于20世纪50年代后期，John McCarthy在麻省理工学院，开发了早期的函数式语言LISP，运行在大型IBM主机（IBM700/7000系列（英语：IBM 700/7000 series））上。LISP的函数定义借鉴了邱奇的λ表示法，并扩展了标签构造来允许递归函数...

variables）是拥有局部作用域的变量。这样的变量只能由声明它的函数或块中访问。在仅有两层可见性的程序设计语言中，局部变量对应全局变量；另一方面，许多类ALGOL语言允许任意多层的嵌套函数，各自拥有私有变量、函数、常量和类型。 大多数程序设计语言中，局部变量是直接存储在调用堆栈上的自动变量。即递归函数...