python - 在Python中将递归转换为迭代

Question

我编写了下面的 python 脚本，它使用分而治之(递归调用)对数组的元素进行排序。我的一位 friend 建议递归比迭代慢。有没有办法将下面的程序转换为“for”循环，并且仍然利用分而治之的策略。即使列表包含很多元素，迭代也会击败递归吗？

    ### Using recursion
import random
from datetime import datetime

start = str(datetime.now().time()).split(':')
def quicksort(A,first,last):
    print "calling parameters",A,first,last
    if first >= last:
        return
    i , j = first, last
    pivot = A[random.randint(first,last)]
    #pivot = A[last]
    while i <= j:
        while A[i] < pivot:
            i+=1
            #print "i:",i
        while A[j] > pivot:
            j-=1
        #print "i,j",i,j
        if i <= j:
            A[i],A[j] = A[j],A[i]
            i,j = i+1, j-1
        #print "intermediate",A
        #print "loop i,j",i,j
    # Using Recursion here    
    quicksort(A,first,j)
    quicksort(A,i,last)

A = [2,8,7,1,3,5,6,4]
#A = [1,1,1,1,1,1,1,1]
quicksort(A,0,len(A)-1)

print A
stop = str(datetime.now().time()).split(':')
print "time taken",float(stop[2]) - float(start[2])

Answer 1

您始终可以将尾递归算法(即递归步骤是函数中最后一条语句的算法)更改为迭代算法。在 Python 中，迭代几乎总是比等效的尾递归更快，因为 Python(故意)缺乏称为尾调用优化的功能，因为 Guido van Rossum 认为优化中丢失的调试信息比获得的速度更重要。其他语言做了相反的权衡，因此在其中一些语言中，递归版本可能是首选。

但是，快速排序并不是(唯一)尾递归:它会递归作为它所做的最后一件事，但它也会递归作为它所做的第二件事。将此类算法转换为迭代算法的唯一通用方法是将大量状态存储在堆栈上 - 本质上是重新实现函数调用的工作方式。这会通过通常在幕后完成的“内务处理”污染您的代码，并且通常会使速度变得相当慢(因为堆栈管理是通过函数调用完成的，因此必须完成幕后工作无论如何，你正在复制它)。

对于某些特定的算法，可能有一种方法可以干净地从非尾递归转换为迭代，但通常您最终得到的将是具有不同性能特征的不同算法，所以它最终并不是迭代和递归性能之间的比较。

特别是对于快速排序，递归版本更可取，并且除了演示如何使用堆栈之外，您很少会在“野外”看到它的迭代版本。例如，参见this blog post about recursive and iterative quicksort - 迭代版本使用堆栈，它给出了结果摘要:

您可以看到，此分析声称迭代版本对于每个元素计数都较慢，尽管随着列表变大，相对而言差异似乎会变小。另请注意，(高度优化的)Python 内置 list.sort 的性能优于两种快速排序实现一个数量级 - 如果您特别关心速度(而不是编写自己的快速排序的学习体验)，每次都使用内置函数。