Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Can all iterative algorithms be expressed recursively?

If not, is there a good counter example that shows an iterative algorithm for which there exists no recursive counterpart?

If it is the case that all iterative algorithms can be expressed recursively, are there cases in which this is more difficult to do?

Also, what role does the programming language play in all this? I can imagine that Scheme programmers have a different take on iteration (= tail-recursion) and stack usage than Java-only programmers.

like image 468
eljenso Avatar asked Jan 19 '10 13:01

eljenso


1 Answers

There's a simple ad hoc proof for this. Since you can build a Turing complete language using strictly iterative structures and a Turing complete language using only recursive structures, then the two are therefore equivalent.

like image 119
plinth Avatar answered Sep 28 '22 02:09

plinth