How to eliminate for/if/while from algorithms when it's possible

Is there any way to find out how to replace for/if for elementary recursive algorithms? I know that primitive recursive functions cannot basically eliminate "for", but for elementary recursive functions, there must be a way to convert the program into ones that do not have for/if/while and so on (which is elementary recursive).

• If you assume that you are given a program (a TM) and you are asking whether there is an equivalent program without for/if, then it is clearly undecidable (e.g. since it's a nontrivial semantic property). If you are referring to a promise problem, where you are given an elementary recursive function, my guess is that it would remain uncomputable. Commented Apr 28, 2013 at 7:31
• @Shaull I know that Entscheidungsproblem is unsolvable, but this only means there does not exist a single program that shows whether two function results in the same result... This case is only restricted those that are known to have elementary recursive algorithm/function. (Complexity class: elementary)
– Pros
Commented Apr 28, 2013 at 9:46
• actually I was thinking about this undecidable promise problem, which motivates me to believe that your problem may also be undecidable. But as I said - it's only a guess. Commented Apr 28, 2013 at 14:23
• Could you be more precise as to what is left, rather than what you remove. It is a rather unusual way to define a problem. Else give precise reference to what you had to start with. I mean that for me, for and while are very similar. So is repeat. Do you keep repeat? Commented Aug 10, 2015 at 15:44
• What is meant by "elementary recursive"? Primitive recursive? Deciding weather a program is writable in a primitive recursive fashion is undecidable (proof there are functions from natural numbers to natural numbers which are not primitive recursive and there are those that are, apply rice's theorem). This applies to any complexity class btw. However if you are asking weather you can replace for/if statements with recursion in general then the answer is yes, always, because both are turing complete.
– Jake
Commented Aug 10, 2015 at 17:17