每个递归过程都可以转换为迭代过程吗？ [英] Can every recursive process be transformed into an iterative process?

问题描述

我正在读这本书，计算机程序的结构和解释，其中讲述了递归过程和递归过程之间的区别，以及迭代过程和迭代过程之间的区别。因此，递归过程仍然可以生成迭代过程。

I was reading the book, Structure and Interpretation of Computer Programs, where in it tells about the distinction between a recursive procedure and recursive process, and similarly between iterative procedure and iterative process. So, a recursive procedure could still generate an iterative process.

我的问题是：给定一个生成递归过程的过程，你总是可以编写另一个实现相同过程的过程吗？结果，但生成一个迭代过程？

My question is: given a procedure which generates a recursive process, can you always write another procedure that achieves the same result but generates an iterative process?

我试图解决的具体问题是编写一个程序，它执行二进制搜索树的有序遍历，但生成一个迭代过程。我知道如何使用堆栈来解决此问题的迭代过程。但是，这仍然会产生一个递归过程（如果我错了，请纠正我）。

The specific problem that I was trying to solve was to write a procedure which does an in-order traversal of a binary search tree but generates an iterative process. I know how you can use a stack to get an iterative procedure for this problem. However, that still generates a recursive process (correct me if I am wrong here).

谢谢，

Abhinav。

Thanks,
Abhinav.

推荐答案

使用线性迭代过程（例如树递归，无法转换为尾递归）无法解决某些任务。您必须使用平台内置的堆栈，或者在语言中自行重新创建堆栈（通常是效率低得多且更加丑陋的解决方案）。
因此，如果将'recursion'定义为'使用堆栈来存储相同代码的不同调用'，那么是的，有时绝对需要递归。

Some tasks are truly impossible to solve with linear iterative processes (e.g. tree recursion, which is impossible to convert to tail recursion). You either have to use the stack built into your platform, or re-create it yourself within the language (usually a much less efficient and uglier solution). So if you define 'recursion' as 'using a stack to store different invocations of the same code', then yes, recursion sometimes is absolutely required.

如果你将'recursion'定义为'我的语言中的函数（最终）调用自身'，那么你可以通过自己重新实现递归来实现无需显式递归，如上所述。这仅在您的语言不提供递归过程，或者没有足够的堆栈空间或具有类似限制时才有用。 （例如，早期的Fortran没有递归过程。当然，他们也没有动态数据结构，你需要模拟它们！就个人而言，我从未遇到过实现伪递归的实际例子。正确的解决方案。）

If you define 'recursion' as 'a function in my language (eventually) calling itself', then you can get by without explicit recursion by re-implementing recursiveness yourself, as describes above. This is only useful if your language doesn't provide recursive procedures, or not enough stack space, or has similar limitations. (For instance, early Fortran's didn't have recursive procedures. Of course, they also didn't have the dynamic data structures that you would need to simulate them! Personally, I have never come across an actual example where implementing pseudo-recursion was the right solution.)

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