在 python 中将递归转换为迭代

Question

我写了下面的 python 脚本，它使用分而治之（递归调用）对数组元素进行排序。我的一位朋友建议递归比迭代慢。有没有办法将下面的程序转换为 '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

是的，有一种方法可以转换它。是的，迭代几乎总是在执行时间上胜过递归。然而，递归通常更易于阅读和维护，节省程序员时间并减少错误发生率。

递归通常较慢，因为与维护计数器和一些状态变量相比，函数调用相对昂贵。当有很多元素时，这个差异实际上会变大。

您可能将此问题（迭代与递归）与计算复杂性问题混淆了。许多分而治之的算法将一个操作从 O(n) 减少到 O(log n)，并且其中许多算法便于递归编写。例如，快速排序是 O(n log n)，但更简单的冒泡排序是 O(n^2)。快速排序易于递归编写；冒泡排序更容易用迭代编写。然而，它们仍然不是等价的算法。

Answer 2

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

但是，快速排序不（仅）是尾递归的：它确实像它做的最后一件事一样递归，但它也递归作为它所做的倒数第二件事。将这种算法转换为迭代算法的唯一通用方法是在堆栈上存储大量状态——本质上，重新实现函数调用的工作方式。这会用通常 behind-the-scenes 完成的 "housekeeping" 污染您的代码，并且通常会使事情变得相当慢（因为堆栈管理是通过函数调用完成的，所以 behind-the-scenes 工作必须无论如何都要完成，你正在复制它）。

对于某些特定的算法，可能有一种方法可以将 non-tail 递归完全转换为迭代，但通常您最终得到的将是 不同的算法 具有不同的性能特征，因此它最终不会成为迭代和递归性能之间的比较。

特别是对于快速排序，递归版本更可取，您很少会看到它的迭代版本 "in the wild" 除了演示如何使用堆栈。例如，请参阅 this blog post about recursive and iterative quicksort - 迭代版本使用堆栈，并给出以下结果摘要：

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

在 python 中将递归转换为迭代

Converting a recursion to iteration in python

python

iteration

recursion

quicksort