递归函数论是30年代发展起来的，是数理逻辑的一个分支，广泛应用于计算机科学的可计算性、计算复杂性和程序理论等方面。

一、递归函数和可计算性

　　可以说递归函数和可计算性是同一概念。
　　（1）可计算性

　　（2）可计算性与递归函数

　　（3）几个可计算的与不可计算的函数