一些计算机编程语言允许一个模块或函数来调用自身。这种技术被称为递归。在递归函数α直接调用自己或调用函数β，反过来调用原函数α。该函数α被称为递归函数。
特性
递归函数可以无限执行就类似一个循环。为了避免递归函数的无穷运行，一个递归函数必须具备有两个属性 -
-
基本准则 − 必须有至少一个基本的标准或条件，例如，当满足此条件时函数停止递归调用自身。
-
由浅入深 − 递归调用应该在那个递归调用作出每次涉及靠近基标准这样的方式前进。
实现
许多编程语言通过堆栈的方式实现递归。一般来说，当一个函数（调用者）调用另一个函数（被调用者）或本身作为被调用， 调用者传送函数执行控制权被调用。
这意味着，调用方函数具有暂停其执行并在稍后继续时从被调用函数的执行控制返回。在这里，调用函数需要从执行的角度入手正是它把自己搁置。它也需要完全相同的数据值执行。为此，活动记录（或堆栈帧）可以创建调用函数。
此活动记录保留局部变量的信息，形式参数，返回地址并传递给调用函数的所有信息。
递归分析
有人可能会认为，作为同样的任务可以反复地来完成，为什么使用递归？第一个原因是递归使得程序更具可读性，并因为今天的提升 CPU 系统中，递归比迭代更加高效。
时间复杂度
如果是迭代，我们采取迭代次数来计算的时间复杂度。同样，在递归的情况下，假设一切都不变，我们试着找出递归调用的次数。 调用一个函数是 Ο(1), 因此（n）数量是递归调用作出递归函数的时间 Ο(n)。
空间复杂度
空间复杂度是算作所需要的执行模块的额外空间量。如遇迭代，编译器几乎不要求任何额外的空间。 编译器不断更新并反复使用的变量值。 但如遇到递归，系统需要的递归调用作出每次存储激活记录。因此可以认为，空间递归函数的复杂性可能比用迭代的函数去更高。