Why Python is horrible for recursion

If you are going to choose one language to write recursive algorithms in, then avoid Python. Why? It is just too restrictive. There are a number of reasons for this. Firstly Python is intrinsically lethargic, i.e. it will take a long time to run algorithms. Next, the Python interpreter doesn’t perform any sort of recursion optimization. Due to this, the recursion limit is often quite low. On most systems it is set at 1000. This means when a recursive function has to recurse many times, an error will be generated by the system.

RecursionError: maximum recursion depth exceeded in comparison

This is done to avoid a stack overflow, and so that infinite recursions are avoided. Nice. But not very useful. We can of course override this using the function setrecursionlimit(), which takes one parameter, the value of the new recursion limit. But honestly, it is likely best to use another language altogether.

import sys
sys.setrecursionlimit(10**6)

To illustrate the inability of Python to cope with recursion, we will implement a recursive Slowsort algorithm in Python, and C. This algorithm was chosen, not because of its great abilities, but rather because of the fact that it is inefficient, and will spur the use of recursive resources. Below is the algorithm written in Python.

def slowsort(A, i, j):
    if i >= j:
        return
    m = int((i+j) / 2)
    slowsort(A, i, m)
    slowsort(A, m+1, j)
    if A[j] < A[m]:
        A[j], A[m] = A[m], A[j]
    slowsort(A, i, j-1)

The code is then run with the following code, which reads from a file, and sorts the numbers:

with open('num25.txt') as file:
    lines = [int(i) for i in file]
a = 0
b = len(lines)-1
slowsort(lines,a,b)

To sort a mere 25 numbers with this algorithm takes 655 seconds in Python. The same algorithm written in C it takes 0 seconds (probably nanoseconds). In many respects if you are programming in Python, there is very little likelihood you will really need recursion anyway.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.