The theory of recursion can be traced back to the use of primitive recursion. The understanding of addition and multiplication by ancient people and modern children is essentially the application of primitive recursion. But it was not until the17th century that the French scholar B. Basgal formally used the mathematical induction closely related to recursion. /kloc-in the 9th century, German mathematician R Dedekind and Italian mathematician G piano formally defined addition and multiplication by primitive recursion, thus developing the whole theory of natural numbers. T. Schollen proposed in 1923 and preliminarily proved that all functions in elementary number theory can be composed of primitive recursion, that is, they are primitive recursive functions. 193 1 year, when K. Godel proved his famous incompleteness theorem, he used primitive recursion as the main tool to arithmeticalize all the concepts of meta-mathematics. The importance of primitive recursive functions has attracted people's attention, and people begin to guess that primitive recursive functions may exhaust all computable functions. However, the appearance of non-primitive recursive computable function by German mathematician W. Ackerman denies this speculation, and also requires people to explore computable functions other than the original recursive function. 1934 inspired by J. Hellbrand, godel put forward the definition of general recursive function; S.C. Cligny of America proved in 1936 that the general recursive function defined in this way is the same as the λ definable function defined by A. Church, and gave several equivalent definitions. Such a general recursive function was later called Hellbrand-Godel-Cligny definition. In 1936, Church and A.M. Turing independently put forward an argument that all computable functions are general recursive functions, which closely combines the theory of recursive functions with the theory of feasibility, thus greatly expanding the application scope of recursive functions (see feasibility and general recursion). The progress of recursive function itself mainly lies in the generalization of definition domain, thus obtaining recursive word function, recursive linear function and recursive universal culvert.