递归，又译为递回，在数学与计算机科学中，是指在函数的定义中使用函数自身的方法。递归一词还较常用于描述以自相似方法重复事物的过程。例如，当两面镜子相互之间近似平行时，镜中嵌套的图像是以无限递归的形式出现的。也可以理解为自我复制的过程。
在数学和计算机科学中，当一类对象或方法可以由两个属性定义时，它们表现出递归行为:
例如，以下是某人祖先的递归定义:
斐波那契数列是递归的经典例子:
Fib(0)=1基线条件1；
Fib(1)=1基线条件2；
对所有整数n,n>1时：Fib(n)=(Fib(n-1)+Fib(n-2))。
许多数学公理基于递归规则。例如，皮亚诺公理对自然数的形式定义可以描述为:0是自然数，每个自然数都有一个后继数，它也是自然数。通过这种基线条件和递归规则，可以生成所有自然数的集合。
递归定义的数学对象包括函数、集合，尤其是分形。
递归还有多种开玩笑的“定义”。
递归是当程序的一个步骤涉及调用程序本身的过程。经历递归的过程被称为“递归”。
要理解递归，必须认识到程序和程序运行之间的区别。程序是基于一组规则的一组步骤。程序的运行实际上包括遵循规则和执行步骤。一个类比:一个程序就像一个书面的食谱；运行一个程序就像实际准备饭菜一样。
这提供了一种理解语言创造的方法——无限数量的语法句子——因为它立即预言句子可以是任意长度的:多萝西认为托托怀疑铁皮人说的....除了可以递归定义的句子之外，还有许多结构，因此一个句子可以通过许多方式将一个类别的实例嵌入另一个类别。多年来，一般来说，语言都被证明适合这种分析。
递归有时在计算机科学、程序设计、哲学或数学教科书中幽默地使用，通常是通过给出循环定义或自我引用，在循环定义或自我引用中，假定的递归步骤不会更接近基线条件，而是导致无限回归。这样的书在词汇表中包含一个笑话条目并不罕见，大致如下:
BrianKernighan和DennisRitchie的书《C编程语言》的一些版本的索引在第269页有所变化；索引条目递归引用自身(“递归86、139、141、182、202、269”)。这个笑话的最早版本出现在Kernighan和Plauger的“软件工具”中，也出现在Kernighan和Pike的“UNIX编程环境”中。它没有出现在第一版的《C编程语言》中。
递归首字母缩写也可以是递归幽默的例子。例如，PHP代表“PHPHypertextPreprocessor”，WINE代表“WINEIsNotanEmulator.”，GNU代表“GNU'snotUnix”。
例子:自然数
递归定义集合的典型例子由自然数给出:
0是自然数；
如果n是自然数，那么n+1也是自然数；
自然数集合是满足前两个属性的最小集合。
例子:真正可达命题的集合
另一个有趣的例子是公理系统中所有“真正可达”命题的集合。
这个集合被称为“真正可达命题”，因为在数学基础的非建设性方法中，真正命题的集合可能大于由公理和推理规则递归构造的集合。
有限细分规则是递归的几何形式，可用于创建类似分形的图像。细分规则从由有限多个标签标记的多边形集合开始，然后以仅依赖于原始多边形标签的方式将每个多边形细分为更小的标记多边形，这个过程可被迭代。创建康托集合的标准“中间三分之一”技术是细分规则，重心细分也是细分规则。
一个函数可以根据自身被部分地定义。一个常见的例子是斐波那契数列:F(n)=F(n1)+F(n2)。为了使这样的定义有用，它必须引入非递归定义的值，在这种情况下，F(0)=0，F(1)=1。
一个著名的递归函数是阿克曼函数，它不同于斐波那契数列，如果没有递归，它将无法被表达的。
如前几节所述，将标准的案例证明技术应用于递归定义的集合或函数，会产生结构归纳法，这是数学归纳法的一种强有力的推广，广泛用于数学逻辑和计算机科学中的推导证明。
动态规划是一种优化方法，它以递归的形式重述了多阶段或多步骤优化问题。动态规划的关键结果是贝尔曼方程(Bellmanequation)，它将优化问题早期(或较早步骤)的值写入到后期(或较晚步骤)的值中。
在集合论中，这是一个保证递归定义函数存在的定理。给定一个集合X,集合X中的一个元素a和一个函数f:X-->X，定理表明存在一个唯一的函数F：N-->X（N表示包括0的自然数集合），使得满足F(0)=a,F(n+1)=f(F(n))(对于任何自然数n)。
唯一性的证明
取两个函数F：N-->X和G：N-->X使得满足：
F(0)=a
G(0)=a
F(n+1)=f(F(n))
G(n+1)=f(G(n))
其中a是集合X中的一个元素。
数学归纳法可以证明对于所有自然数都有F(n)=G(n)：
基线条件：当n=0时，等式F(0)=a=G(0)成立；
递归步骤：假设当k∈N时，F(k)=G(K)成立,然后F(k+1)=f(F(k))=f(G(k))=G(k+1),因此F(k)=G(k)意味着F(k+1)=G(k+1)
通过归纳，F(n)=G(n)(其中n∈N)。
一种常见的简化方法是将一个问题分成相同类型的子问题。作为一种计算机编程技术，这被称为分治法，是许多重要算法设计的关键。分治法是一种自上而下解决问题的方法，通过解决越来越小的实例来解决问题。相反的方法是动态编程，这种方法是自下而上的方法，通过解决越来越大的实例来解决问题，直到达到所需的大小。
递归的一个经典例子是阶乘函数的定义，这里用C代码给出:
unsignedintfactorial(unsignedintn){if(n==0){return1;}else{returnn*factorial(n-1);}}
该函数在输入的较小版本（n-1）上递归调用自身，并将递归调用的结果乘以n，直到达到基线条件，类似于阶乘的数学定义。
当一个函数被定义为更简单、通常更小的自身时，计算机编程中的递归就是一个例子。然后通过组合从问题的简单版本中获得的解决方案来设计问题的解决方案。递归的一个示例应用是在编程语言的解析器中。递归的最大优点是通过有限的计算机程序可以定义、解析或产生无限组可能的句子、设计或其他数据。
递推关系是递归定义一个或多个序列的方程，可以“解决”某些特定类型的递推关系来获得非递归定义。