在python中将递归转换为迭代 [英] converting a recursion to iteration in python

问题描述

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

  ###使用递归
 import random 
来自datetime import datetime 
 
 start = str（datetime.now（）。time（））。split（'：'）
 def quicksort（A，first，last）： 
打印调用参数，A，第一个，最后一个
如果第一个> =最后一个：
返回
i，j =第一个，最后一个
 pivot = A [随机.randint（first，last）] 
 #pivot = A [last] 
而i< = j：
而A [i]< pivot：
 i + = 1 
 #printi：，i 
而A [j]> pivot：
 j- = 1 
 #printi，j，i，j 
 if i< = j：
 A [i]，A [j] = A [j]，A [i] 
i，j = i + 1，j-1 
 #printintermediate，A 
 #printloop i，j，i，j 
＃在这里使用递归
 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） 
 
打印A 
 stop = str（datetime.now（）。time（））。split（'：'）
 printtime taken，float（stop [2 ]） - 浮动（开始[2]）
  

解决方案

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

然而，快速排序不是（仅限于）tail recursive：它确实作为最后的东西进行递归，但它也递归它作为它做的第二件事。将这种算法转换为迭代算法的唯一通用方法是在堆栈上存储大量状态 - 实质上是重新实现函数调用的工作方式。这会使你的代码受到通常在幕后进行的内务管理的污染，并且通常会使事情变得相当慢（因为堆栈管理是通过函数调用来完成的，所以必须完成幕后工作无论如何，你正在重复它）。

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

特别是对于quicksort，递归版本是优选的，你很少会看到它在野外的迭代版本，除了演示如何使用堆栈。例如，请参阅的迭代和递归快速排序时间摘要

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

I wrote the below python script that sorts the elements of an array using divide-and-conquer (recursive calls). One of my friend suggested that recursion is slower than iteration. Is there a way to convert the below program to a 'for' loop and still leverage divide-and-conquer strategy. Will iteration beat recursion even if the list contains a lot of elements?

    ### 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])

解决方案

You can always change a tail recursive algorithm (that is, one where the recursive step is the very last statement in the function) into an iterative one. In Python, iteration is almost always faster than an equivalent tail recursion because Python (deliberately) lacks a feature called tail call optimization, because Guido van Rossum sees the debugging information lost in that optimization as being more important than the speed gained. Other languages have made the opposite tradeoff, so in some of those, the recursive version might be preferred.

However, quicksort is not (only) tail recursive: it does recurse as the very last thing it does, but it also recurses as the second last thing it does. The only general way to convert a this kind of algorithm into an iterative one is to store a lot of state on a stack - essentially, reimplementing how function calls work. This pollutes your code with "housekeeping" that is normally done behind-the-scenes, and usually make things considerably slower (since the stack management is done with, well, function calls, so the behind-the-scenes work has to be done anyway and you're duplicating it).

For some particular algorithms, there may be a way to convert cleanly from non-tail recursion to iteration, but often what you end up with will be a different algorithm with different performance characteristics, and so it doesn't end up being a comparison between iterative and recursive performance.

For quicksort in particular, the recursive version is preferable, and you will rarely if ever see an iterative version of it "in the wild" except to demonstrate how it is possible using a stack. For example, see this blog post about recursive and iterative quicksort - the iterative version uses a stack, and it gives this summary of results:

You can see that this analysis claims that the iterative version is slower for every element count, although the difference appears to get smaller in relative terms as the list gets larger. Also note that the (highly optimized) Python builtin list.sort outperforms both quicksort implementations by an order of magnitude - if you care particularly about the speed (rather than the learning experience of coding your own quicksort), use the builtin every time.

这篇关于在python中将递归转换为迭代的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！