Does "recursive" mean the same in "recursive functions" and in definition of Fibonacci function?

150 Views Asked by At

Why are recursive functions called "recursive"? Does "recursive" mean that we can define a family of functions inductively (from primitive recursive functions to composite recursive functions)?

Some functions can be defined recursively in terms of themselves individually. For example, Fibonacci function, and many functions which have been implemented in programming languages by divide and conquer. What is such a function called? Also "recursive" function?

Do the uses of "recursive" in the above two scenarios have related meanings at all?

1

There are 1 best solutions below

4
On

In the link you refer to $\mu$-recursive functions, also partial recursive functions. Indeed, these functions are defined from the base functions (successor function, projections functions, zero functions of each arity) by applying a finite sequence of compositions, primitive recursions and minimalizations. This is the class of computable functions by the Church thesis. This concept belongs to computability theory.

The Fibonacci function can be defined by recursion (calling itself several times to get a result). This concept belongs to programming.