Julia is bad at recursion

If you are thinking about using Julia to implement recursive algorithms, forget it. It just won’t work properly, well not unless you have some idea what the depth of recursion will be… but that’s hardly the point of recursion. So you could likely do Fibonacci(40) with few problems. Anything with indeterminate recursive depth, or a lot of internal variables though will suffer at the hands of Julia.

The hard limit a the stack size (kbytes) on a system can be found using ulimit, but its no panacea:

% ulimit -Hs
65520

Which is seemingly still a lot, at 65 megabytes (on OSX 11.1). The problem with Julia is weird, because Python has similar constraints, yet is able to run Slowsort(). Julia produces the following error when faced with sorting a mere 25 numbers:

ERROR: LoadError: StackOverflowError:
Stacktrace:
[1] recur(::String) at /recur.jl:2 (repeats 79984 times)
in expression starting at /recur.jl:5

This is different to Python, which also has issues with recursion, but there is it based on the value of the “recursion limit”, or depth of the recursion. In Python this can be fixed by setting new depth:

sys.setrecursionlimit(100000)

Julia on the other hand does not have an internal limit to the stack size, but uses the limits of the operating system. Now this doesn’t mean recursive depth. How many recursive calls will fit on the stack then depends upon both your system and the complexity of the function itself. Now let’s do an experiment. With the system stack set at max, we will run the following simple recursive function, with very little in the way of resource overhead.

function recur(var::String)
   recur("Ai")
end

recur("ai")

The outcome is still the same, a stack overflow. But the value 79984 is repeated. So what is going on here? To dig deeper, we calculate the depth of recursion before failure (DORBF). All we really do is count the number of times the function is called.

x = 0

function recur(var::String)
   global x = x + 1
   print(x," ")
   recur("A")
end

recur("a")

In this case the depth of recursion is 209,181, which is reasonably deep. If we apply the same principle to the Slowsort() function, we get a depth of 130,738.

The moral of the story is don’t use Julia for recursion, I mean it really was never designed for that.

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.