How can I implement insertion sort using recursion and which is more efficient?

Question

How could I implement this using recursion, and would it be more effcient?

My code:

def insertionSort(array):
    '''(list) - > list
    Returns a sorted list of integers by implementing
    the insertion sort which returns numbers in array from
    least to greatest
    '''
    for i in range(1, len(array)):

        if array[i-1] > array[i]: #Finds a number out of place
            temp = array[i]
            for a in range(0,i):
                if temp < array[a]:
                    array.insert(a,temp)
                    del array[i+1]
                    break
    return array

No it isn't more efficient to use recursion, it is usually much more costly, also have you attempted implementing recursion yourself? — jamylak, Mar 23 '13 at 05:45
@jamylak Doesnt Python optimize recursion, and that too by quite a bit ? I have seen some posts here on SO with time measurements that would suggest almost equivalent performance from both recursion and iteration. — asheeshr, Mar 23 '13 at 05:48
@AshRj Which posts are you talking about? Python recursion is notably slow — jamylak, Mar 23 '13 at 05:49
If I am not wrong my method sorts the list in quadratic time. I haven't yet tried to implement recursion, but wouldn't it be faster? — Jacob Worldly, Mar 23 '13 at 05:49
@JacobWorldly That would depend entirely on your algorithm and not recursion performance. — asheeshr, Mar 23 '13 at 05:50
@AshRj Using the code provided, and assuming an optimal recursive alternative to my code, wouldn't recursion still be faster since this calculates O(x^2) time? — Jacob Worldly, Mar 23 '13 at 05:57
@julio.alegria Just curious is all. Talking about recursion in general, is it a preferable solution to problems in python? I am new to python, and the reason I ask. — Jacob Worldly, Mar 23 '13 at 06:00
Related: [Does Python optimize tail recursion?](http://stackoverflow.com/questions/13591970/does-python-optimize-tail-recursion) (Answer: **no**) — Andrew Mao, Mar 23 '13 at 06:14

score 3 · Answer 1 · answered Mar 23 '13 at 06:32

A simple recursive version:

def insertionSort(array,i=1):
  if i >= len(array):
    return array
  if array[i-1] > array[i]: 
    temp = array[i]
    for a in range(0, i): 
      if temp < array[a]:
        array.insert(a,temp)
        del array[i+1]
        break
  return insertionSort(array, i+1)

Generally recursion is better for certain data structures such as trees and linked lists. Sometimes it is easier to think in terms of recursion to solve a problem. I don't remember a case where recursion actually used for efficiency.

Gene · Answer 2 · 2013-03-23T06:21:37.250

Any for loop for x in range(a,b): Body can be reimplemented with tail recursion:

def rfor(b, x = a):
  if a < b:
     Body
     rfor(b, x + 1)

This ought to give you enough to get the answer yourself. In standard Python this will definitely be slower than the loop and eat one stack frame per iteration. In other languages and implementations with good tail call optimization, they'll be equal in cost. Apparently Guido has said he's uninterested in tail call optimization.

How can I implement insertion sort using recursion and which is more efficient?

2 Answers2