So what confuses me is that let's consider a function f. According to a definition from a text book it asserts that f is called recursive, if there is a Turing machine that computes it (for all input strings output of the machine should be equal to output of the function given the same input).

But in general, we say that a function is recursive if it calls itself or maybe firstly another function and then that other function calls our initial function again and again until some initial condition.

So these two definitions are seems to be different. Should I choose the meaning of recursion based on context or am I missing something ? Thanks in advance


2 Answers 2


A function is recursive if it can be defined using certain constructs, one of which is recursive calls.

A function is computable if it can be implemented by a Turing machine.

Theorem: A function is computable if, and only if, it is recursive.

Because of the above theorem people are sometimes a bit imprecise about using the correct words and definitions, and they conflate recursive and computable functions. They should not. It confuses students.


When we say a function is recursive in the computational models class, we mean that its computable.

A function that calls itself is also called recursive, but usually you wont see those in computational models - and if you do, then its explicitly said that it calls itself.

I think you should not worry about having two definitions for the same name as they come in different contexts.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.