递归功能被转换成非递归函数

Question

可能重复：
Can every recursion be converted into iteration?

可以随时或箱子一个递归函数被转换成非递归功能或一组非递归函数？

你能指点我的例子哪些工作，不工作？

感谢

Answer 1

这总是可能的，因为您可以自己模拟调用堆栈。但是，这并不容易。

简单案例是尾递归：这些甚至不需要堆栈。例如，这家伙被轻易地转化成for循环：

def countdown(n): 
    if n >= 0: 
     print n 
     countdown(n-1) 

即使功能不是严格尾递归，有时你可以仍然逃脱不具有栈。例如，经典因子函数：

def factorial(n): 
    if n <= 1: 
     return 1 
    else: 
     return n * factorial(n-1) 

当存在多个递归调用时，它变得更加困难。举个例子，快速排序：

def quicksort(array): 
    if len(array) <= 1: 
     return array 
    else: 
     pivot = array[0] 
     left = quicksort([x for x in array[1:] if x < pivot]) 
     right = quicksort([x for x in array[1:] if x >= pivot]) 
     return left + [pivot] + right 

虽然这是绝对有可能做到这一点没有递归，你就必须自己建立一个栈，并构建while循环，迭代，直到堆栈为空。

Answer 2

是的，它总是可以递归函数转换成非递归之一。

你可以用一个简单的思想实验证明了这一点：您可以实施模拟一个图灵完备的寄存器机堆栈（一个简单的微处理器的基本等价）一个简单的非递归解释。这是一个非递归的代码，可以运行任何递归函数。

请注意，在递归的所有非平凡情况下（即比简单的尾部递归更复杂，可以将其转换为循环），您将需要以某种方式捕获包含在嵌套堆栈帧中的信息。通常，这可以通过使用堆内存来模拟可变大小的堆栈来完成，但也可以使用其他技术（例如延续或队列）。

Answer 3

是的每个递归函数都可以转换为迭代函数。

Answer 4

所有的递归函数都可以转换为迭代函数，但并非如此简单。

它只是简单的在尾递归的情况。这是当只有一个递归调用发生时，它发生在最后。这可以简单地转换为do-while语句。

对于其他情况并非如此简单。虽然所有递归都可以转化为迭代，但是您需要在更复杂的示例中模拟自己的堆栈。

Answer 5

总是可以使用stack将递归转换为迭代。您不必使用某些参数进行递归调用，而是将参数集推入堆栈。在每次迭代中，顶部参数集被弹出并处理。