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

另外，编程语言在这一切中扮演什么角色?我可以想象，与纯 Java 程序员相比，Scheme 程序员对迭代(=尾递归)和堆栈使用有不同的看法.

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 Turing complete language using only recursive structures, then the two are therefore equivalent.

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