converting a recursion to iteration in python
Question: 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])
    


Answer: 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](http://codexpi.com/quicksort-python-
iterative-recursive-implementations/) \- the iterative version uses a stack,
and it gives this summary of results:

[![Summary of iterative&recursive quicksort times for various
n](//i.stack.imgur.com/4VCwX.png)](//i.stack.imgur.com/4VCwX.png)

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.

