所有迭代算法都可以递归表达吗？

本文介绍了所有迭代算法都可以递归表达吗？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

如果没有，是否有一个好的计数器示例显示迭代算法，其中不存在递归对应物？

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?

此外，编程语言在这一切中扮演什么角色？我可以想象，Scheme程序员对Java迭代（=尾递归）和堆栈使用的看法不同于仅Java程序员。

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.

推荐答案

这是一个简单的临时证明。既然你可以使用严格的迭代结构来构建图灵完整语言，并且只使用递归结构来构建完整语言，那么这两者就是等价的。

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