概述

定义

条件

计算

概述

对于某一函数f（x），其定义域是集合A，那么若对于A集合中的某一个值X0，其函数值f（x0）由f（f（x0））决定，那么就称f（x）为递进函数，又名递归函数，是计算机程序中比较常见的一种算法。

定义

在数学上，关于递归函数的定义如下：对于某一函数f(x)，其定义域是集合A，那么若对于A集合中的某一个值X0，其函数值f(x0)由f(f(x0))决定，那么就称f(x)为递归函数。

在编程语言中，把直接或间接地调用自身的函数称为递归函数。函数的构建通常需要一个函数或者一个过程来完成。

在数理逻辑和计算机科学中，递归函数或μ-递归函数是一类从自然数到自然数的函数，它是在某种直觉意义上是"可计算的" 。事实上，在可计算性理论中证明了递归函数精确的是图灵机的可计算函数。递归函数有关于原始递归函数，并且它们的归纳定义(见下)建造在原始递归函数之上。但是，不是所有递归函数都是原始递归函数 — 最著名的这种函数是阿克曼函数。

其他等价的函数类是λ-递归函数和马尔可夫算法可计算的函数。

条件

一个含直接或间接调用本函数语句的函数被称之为递归函数，它必须满足以下两个条件：

1） 在每一次调用自己时，必须是（在某种意义上）更接近于解；

2） 必须有一个终止处理或计算的准则。

例如：

梵塔的递归函数

void hanoi （int n, char x, char y, char z）

{

if （n==1）

move（x, 1, z）；

else {

hanoi（n-1, x, z, y）；

move（x, n, z）；

hanoi（n-1, y, x, z）；

}

}

计算

数论函数的一种，其定义域与值域都是自然数集，只是由于构作函数方法的不同而有别于其他的函数。处处有定义的函数叫做全函数，未必处处有定义的函数叫做部分函数。最简单又最基本的函数有三个：零函数O（x）=0（其值恒为0）；射影函数；后继函数S（x）=x+1。它们合称初始函数。要想由旧函数作出新函数，必须使用各种算子。

代入（又名复合或叠置）是最简单又最重要的造新函数的算子，其一般形状是：由一个m元函数？与m个n元函数 g1,g2,…，gm 造成新函数 ? （g1（x1,x2,…，xn），g2（x1,x2,…，xn），…，gm（x1,x2，…，xn）），亦可记为？（g1，g2,…，gm）（x1，x2,…，xn）。另一个造新函数的算子是原始递归式。