This question already has an answer here:

Is it possible to solve every problem (solvable with turing machine) with only recursion ? If yes, which principles or theories assure this ? Thanks

marked as duplicate by Raphael Feb 26 at 12:37

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • Hi, im my life i solved some problems using recursion and i wanna know if exist some theorems that proves if is it possible to solve every problem (solvable with turing machine) with only recursion – Qwerto Feb 26 at 10:29
  • Please specify what operations 'recursion' consists of and what other operations are allowed. For instance, many problems will be unable to be solved without some form of I/O (this can be implicit in your model, but this has to be specified). An example of what 'only recursion' can mean is 'no other control structures'. – Discrete lizard Feb 26 at 10:50
  • What would "only recursion" mean? What are you forbidding? What operations are allowed? Please edit the question to clarify it -- don't leave clarifications in the comments, but edit the question so it is clear for someone who encounters it for the first time. We want questions to stand on their own so people don't have to read the comments. – D.W. Feb 26 at 18:05
up vote 0 down vote accepted

A set $A$ is computable (like in Turing machines) iff its characteristic function $$\chi_A(x) = \begin{cases}1, & x \in A\\ 0, & x \notin A\end{cases}$$ is recursive. The class of recursive functions (sometimes referred to as $\mu$-recursive functions) is the smallest class that contains all constant functions, successor function, projection, and is closed under substitution, primitive recursion and minimization.

So yes, every computable function is recursive w.r.t. to the definition above.

  • Why the recursion is so versatile (speaking in practice) so as every problem can be converted in a recursion problem ? – Qwerto Feb 26 at 11:49
  • 2
    Although this has been accepted, it's not clear to me that it actually answers the question. The question, to me, seems to be about recursion in the sense of programming languages (functions calling themselves), not in the sense of recursion theory. Indeed, in terms of computability, the words "recursive" and "computable [by a Turing machine]" are taken as synonymous, but there's no meaningful recursion in Turing machines. – David Richerby Feb 26 at 12:38
  • You say true things, but there is no reasoning whatsoever. You say "so yes", but where does the "so" come from? – Raphael Feb 26 at 12:38
  • 1
    @Raphael Isn't the duplicate question actually going the other way? (Being able to replace all recursions with iteration doesn't necessarily imply that you can replace all iteration with recursion, which is what this question is asking.) – David Richerby Feb 26 at 12:42
  • I am not quite sure in which direction you want to go with that question @Qwerto. In theory, the story goes like "look at some program, it can be encoded in some number and then be simulated by encoding each step the program does". In terms of programming languages the steps are quite the same. It is not too hard to eliminate the while-loop from e.g. C by doing some simulation of each iteration with recursion. – PHPNick Feb 26 at 12:45

Can you define what it means to solve a problem "only" with recursion?

Would your definition allow an algorithm like this:

int foo(int n) {
    if (n==1) return 1;
    while(someCondition) {
        do something
        foo(n-1);
    }
}

If your definition would wllow this, then it would be easy to transform every algorithm in such a recursive form (you could do all your calculations in the outermost function call and do nothing in the recursive calls).

  • They probably mean something like lambda calculus. – Raphael Feb 26 at 12:38
  • 1
    Surely, you mean "if(someCondition) {...}"? At the moment, your example contains both iteration (while) and recursion. – David Richerby Feb 26 at 13:02

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