所有迭代算法都可以递归表达吗？ [英] 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?

此外，编程语言在这一切中扮演什么角色？我可以想象，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.

这篇关于所有迭代算法都可以递归表达吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！