递归函数被转换为非递归函数

Question

可能重复:
每次递归都可以转换为迭代吗？

可以总是或在哪种情况下将递归函数转换为非递归函数或非递归函数集？

你能指出一些有用的例子吗？

谢谢

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循环,迭代直到堆栈为空.