5
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • $\begingroup$ Closely related question, maybe even a duplicate. $\endgroup$ – Raphael♦ Apr 15 '15 at 13:05
  • $\begingroup$ @Raphael Yea, closely related, but not a duplicate. However, as I now see. The answer for my question is, to check turing completeness, and then I need to search for criteria. $\endgroup$ – kravemir Apr 15 '15 at 13:14
  • $\begingroup$ @Raphael I do not understand your understanding of "any problem". To me the meaning is the same as "every problem" in this context. I had not seen your comment, and was at loss to interpret the edit by Miro (as seen in my answer). But I am not a native speaker either (who is, given the number of English dialects? :) $\endgroup$ – babou Apr 15 '15 at 13:36
  • 1
    $\begingroup$ @Raphael It seems to me that the closely related question was a pretty bad one. There is an infinity of different criteria to ensure Turing power. Indeed we know that very different programming languages, with completely different features, all have Turing power. Actually, in early times, people would design programming languages corresponding to formal mathematical models, See Lisp, Snobol, APL, Prolog, Algol, Setl. And they did not go as far as they could have. See also Turing complete weirdos such as Intercal, Brainfuck and other esoteric programming languages.. $\endgroup$ – babou Apr 15 '15 at 14:07
  • 1
    $\begingroup$ @Raphael Boring, I think not? Check: I am fascinated by the way the OP accepted the only wrong answer, which got more votes as a result. Then user swick remarked it was wrong, since one loop is needed. The author of the answer swept it under the rug, as being achieved by a specific assignment ... This kind of assignment does have a name in programming: goto, and it can indeed be used to create loops. But explaining in an accepted answer that (1) loop is not needed, and (2) because it can be replaced by a goto, seems to be adding insult to injury. Did Miro notice answers incompatibilities? $\endgroup$ – babou Apr 15 '15 at 21:42
4
$\begingroup$

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).

|cite|improve this answer
$\endgroup$
7
$\begingroup$

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 ;)

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Well, it's more than an answer. I feel like at "automation and grammars" classes, but you're right. I just needed to check for turing-completeness. $\endgroup$ – kravemir Apr 15 '15 at 12:49
  • $\begingroup$ What do you mean by not even needing loops? You do need loops or recursion to be Turing complete. Or does "writing memory" mean something weird, like changing the code of the program while it's executing? $\endgroup$ – svick Apr 15 '15 at 17:08
  • $\begingroup$ svick: You are of course right. Indeed, what I meant is that you could change the machine state (the instruction pointer, or rather the 'follow up state') by writing to a particular memory address. But yeah, that's really weird :) $\endgroup$ – ftl Apr 15 '15 at 18:20
  • $\begingroup$ Miro: Sorry, I couldn't restrain myself, I find language design exciting and I got carried away. Thanks for accepting my answer :) $\endgroup$ – ftl Apr 15 '15 at 18:30
  • $\begingroup$ Just one thing I had overlooked. We need loops. However, it doesn't have to be for, while. It could be just loop made using goto. So, your (2) statement is not correct :) $\endgroup$ – kravemir Apr 16 '15 at 6:26
3
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ "But just because you can do it, doesn't mean it's a good idea." - This is what is it all about... people can use recursion, so together with virtual methods they often make chaotic software(just for simple problems), that is often hard to analyze and reason about,... making software "bottom-up / no recursions" requires developers to write clear code, that is easily understandable, because you don't have to study tons of functions and classes that use each other, like a spaghetti code - hard to make parallel, and distribute computation $\endgroup$ – kravemir Apr 15 '15 at 12:45
  • 2
    $\begingroup$ Write a function that adds up the numbers stored in the leaves of a binary tree with and without recursion. See the difference recursion can make. $\endgroup$ – Dave Clarke Apr 15 '15 at 12:57
  • $\begingroup$ Non-recursive is easy too. Make stack, push root node. While stack is not empty: pop&store top, if top has children, add children to stack, else add number to sum... Few lines. $\endgroup$ – kravemir Apr 15 '15 at 13:06
  • 2
    $\begingroup$ Miro: I encourage you to read Why Functional Programming Matters by John Hughes. $\endgroup$ – ftl Apr 15 '15 at 18:37
  • 1
    $\begingroup$ I hope people don't write software as described in comment #3. To process recursive structures one should have a strong tendency towards using recursive algorithms. Otherwise its like using a hammer to insert a screw: It might work, but its still the wrong tool for the job. $\endgroup$ – Mike B. Apr 16 '15 at 13:18
-2
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Downvoters, care to explain? $\endgroup$ – Yugo Amaryl Oct 18 '17 at 18:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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