在数学上，关于递归函数的定义如下：
对于某一函数f(x)，其定义域是集合A，那么若对于A集合中的某一个值X0，其函数值f(x0)由f(f(x0))决定，那么就称f(x)为递归函数。
在编程语言中，把直接或间接地调用自身的函数称为递归函数。函数的构建通常需要一个函数或者一个过程来完成。
在数理逻辑和计算机科学中，递归函数或μ-递归函数是一类从自然数到自然数的函数，它是在某种直觉意义上是"可计算的" 。事实上，在可计算性理论中证明了递归函数精确的是图灵机的可计算函数。递归函数有关于原始递归函数，并且它们的归纳定义(见下)建造在原始递归函数之上。但是，不是所有递归函数都是原始递归函数 — 最著名的这种函数是阿克曼函数。
其他等价的函数类是λ-递归函数和马尔可夫算法可计算的函数。
例子：
【pascal语言】
function do(x:integer);
begin
if x<=1 then exit(0)
else if x>1then exit(do(x-1)+10)
end;
【C++语言】
用递归法计算1+2+。。。N的值。
#include<iostream.h>
int fn(int i);
void main()
{
int N;
cout<<"
输入一个正整数:";
cin>>N;
cout<<"
1+2+...+"<<N<<"的结果是:"<<fn(N)<<"
";
}
//递归函数的定义
int fn(int i)
{
if(i==1)
return 1;
else
return i+fn(i-1);
}
