Do we need recursion in programming language to solve any problem?

Question

My question is simple: If we want to be able to solve every problem, that we can solve using recursions, do we need programming language to allow us use recursions?

Assuming we are allowed to use: conditional evaluation of blocks (if/else), cycles(for,while), dynamic allocation of memory.

I know, that we won't be able to implement everything the way we want. However, I'm asking whether we are able to solve everything, just by using different implementation - or by modification of algorithm to be non-recursive.

Answer 1

You do not need recursion, and as you suggest, and as confirmed by Dave Clarke's answer, you only need conditionals, loops and memory allocation and assignment.

You can use it to simulate recursion. Or more simply you can use it to implement arbitrary Turing machines. Just do it for a universal TM, so you get to implement only one :)

You can actually almost also do it without loops, but not quite. You need at least one loop if you expect to have infinite computations, which is implied by Turing power.

However, it could be an implicit loop that loops back to the beginning of the program, unless you execute a termination statement.

You can remark that control of a Turing Machine has exactly that: a single loop applied to a case statement, looking up a transition table.

If you wonder how abitrary many loops can be encoded into a single loop, is is very similar to dovetailing techniques use to explore space according to several indices. Think of indexing all pairs of natural numbers, with or without upperbounds, with a single integer.

Added after the question was modified:

If you consider "every problem, that we can solve using recursions", rather than "any problem", you do not change the question, unless you are a lot more precise (and restrictive) about what else is available, and what use of recursion you allow.

But an unrestricted recursion will give you at least one unlimited loop, which is usually enough to get Turing Power, if you allow unlimited memory allocation.

Note that there are limited uses of recursion that keep you below Turing Power, in precise settings. Look for example at primitive recursive functions.

_{I understand from your later comment that you made that change, so as to limit the request for solvability to what was already solvable, thus excluding such problems as the halting problem. If that is the intent, it is of course better stated. But, I guess, everyone had instinctively understood it that way, and the change was disconcerting (at least for me).}

Answer 2

In short, to answer your questions:

(1) You can convert any recursive algorithm into its non-recursive form.

(2) As stated by the others, you have all the features you need.

Computational Power (Turing-completeness)

You probably know that you cannot solve any problem, for instance, the halting problem is undecidable. And so are many other problems, such as deciding whether an arbitrary formula in first order logic is provable. Thus, with today's knowledge on computability, even the most advanced computer/programming system imaginable won't be able to process every query even if all the data is available.

When assessing the computational power of languages, computer scientists often use the notion of Turing-completeness: If you can describe (and run) any Turing machine in your programming language, then it is Turing complete and can solve any problem which can be solved by a Turing machine.

To get a feel for Turing machines, I strongly encourage you to use a Simulator and try to solve some simple problems.

In particular, have a look at the syntax of the sample program in the Simulator, which should give you an idea of your minimal language.

Expressive Power and Minimality

When it comes to language design, expressive power is more important to me than the ability to solve any computable problem. Many useful domain-specific languages are not Turing-complete, but address specific problems very well.

However, equally powerful computational models such as the Lambda Calculus (functional programming) or the Pi Calculus (concurrent programming) show that you can have a very small set of elegant, composable language elements to construct larger systems, to be able to reason about their composition while having the computational power of Turing machines at the same time. Beautiful.

So if it is minimality you are looking for, take a closer look at the Lambda Calculus. Other noteworthy well designed minimal languages are:

• LISP
• Prolog
• Smalltalk and in particular Self

Feel free to add more languages to your personal list (and please let me know ;)

Answer 3

If you have all the features you mention, you don't need recursion.

Using dynamic memory you can implement a stack. This can be used to save "partial computations" and the while loop can loop through them, thereby mimicking recursion.

But just because you can do it, doesn't mean it's a good idea.

Answer 4

To complete others' answers, I think you might want to check the difference between a recursive process, and a recursive procedure. A recursive procedure doesn't necessarily execute a recursive process. When Babou writes that you can do everything without loops, he is probably secretly thinking about recursive procedures yielding iterative processes.