It is said that computability theory is also called recursion theory. Why is it called like that? Why recursion has this much importance?
Importance of recursion in computability theory
computability;terminology;history
In the 1920's and 1930's people were trying to figure out what it means to effectively compute a function (remember, there were no general purpose computing machines around, and computing was something done by people).Several definitions of computable were proposed, of which three are best known:The $\lambda$-calculusRecursive functionsTuring machinesThese turned out to define the same class of number-theoretic functions. Because recursive functions are older than Turing machines, and the even older $\lambda$-calculus was not immediately accepted as an adequate notion of computability, the adjective recursive was used widely (recursive functions, recursive sets, recursively enumerable sets, etc.)Later on, there was an effort, popularized by Robert Soare, to change recursive to computable. Thus we nowadays speak of computable functions and computably enumerable sets. But many older textbooks, and many people, still prefer the recursive terminology.So much for the history. We can also ask whether recursion is important for computation from a purely mathematical point of view. The answer is a very definite yes!. Recursion lies at the basis of general-purpose programming languages (even while loops are just a form of recursion because while p do c is the same as if p then (c; while p do c)), and many fundamental data stuctures, such as lists and trees, are recursive. Recursion is simply unavoidable in computer science, and in computability theory specifically.