CODEWITHSUNDEEP
pythonrecursioniterationquicksort
ForeverLearner
ForeverLearner

Reputation: 2103

Converting a recursion to iteration in python

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

Upvotes: 1

Views: 5844

Answers (2)

lvc
lvc

Reputation: 35069

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:

Summary of iterative&recursive quicksort times for various n

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.

Upvotes: 4

Prune
Prune

Reputation: 77837

Yes, there is a way to convert it. Yes, iteration almost always beats recursion in execution time. However, recursion is often easier to read and maintain, saving programmer time and reducing the incidence of errors.

Recursion is generally slower because a function call is relatively expensive compared to maintaining a counter and a few status variables. This difference actually gets larger when there are a lot of elements.

You may have confused this issue (iteration vs recursion) with the issue of computational complexity. Many divide-and-conquer algorithms reduce one operation from O(n) to O(log n), and many of these algorithms are convenient to write recursively. For instance, the quick sort is O(n log n), but the simpler bubble sort is O(n^2). Quick sort is easy to write recursively; bubble sort is easier to write with iteration. However, they are still not equivalent algorithms.

Upvotes: 0

Related Questions