Julia breaks recursion!

I do love recursion.

However Julia it seems does not. And you know that’s okay – recursion isn’t the panacea that some  people think it is. I mean I think it is an interesting problem solving methodology (I am writing a book on it)… but there are other ways of doing things. I recently wrote an algorithm to flood fill a portion of an image – that basically involves replacing the colour of  an interconnected region in an image with another colour. There were two algorithms: one recursive, and one iterative, however it is the recursive one that causes some issues. Here is the code in Julia:

# Floodfill using recursive algorithm
function floodfill(img, seedx, seedy, newC)

  function flood(x, y, oldC, newC)
      if img[x,y] != oldC       # the base case
          return
      end
      img[x,y] = newC
      flood(x+1, y, oldC, newC) # right
      flood(x-1, y, oldC, newC) # left
      flood(x, y+1, oldC, newC) # down
      flood(x, y-1, oldC, newC) # up
  end
 
  oldC = img[seedx,seedy]
  flood(seedx, seedy, oldI, newC)
 
  return img
end

Note that Julia allows nested functions, which makes it easier from the point of view of passing large structures like arrays, because you only have to pass them into the outer function, and the inner recursive function has access to them. I tested the algorithm on the following 10×10 sample image, with a starting point of (3,4), and a flood-fill intensity of 7.

testI = [0 0 0 0 0 0 0 0 0 0; 
         0 0 1 1 1 1 1 0 0 0;
         0 1 1 1 0 0 1 0 0 0;
         0 0 1 1 1 1 1 1 0 0;
         0 0 0 0 0 1 1 1 0 0;
         0 1 1 1 0 0 0 0 0 0;
         0 1 1 0 0 0 0 0 0 0;
         0 1 1 1 0 0 0 0 0 0;
         0 0 1 1 1 1 1 1 0 0;
         0 0 0 0 0 0 0 0 0 0]
 
testIf = floodfill(testI, 3, 4, 7)

Here is the output:

[0 0 0 0 0 0 0 0 0 0
 0 0 7 7 7 7 7 0 0 0
 0 7 7 7 0 0 7 0 0 0
 0 0 7 7 7 7 7 7 0 0
 0 0 0 0 0 7 7 7 0 0
 0 1 1 1 0 0 0 0 0 0
 0 1 1 0 0 0 0 0 0 0
 0 1 1 1 0 0 0 0 0 0
 0 0 1 1 1 1 1 1 0 0
 0 0 0 0 0 0 0 0 0 0]

No problem at all. Now I tested it on an image that is 1000×1000 image with a 282,000 pixel region to be filled. It doesn’t take long to break though. The function flood() is called a  total of 24835 times before the program fails, giving the following message: “ERROR: LoadError: StackOverflowError:”. There is obviously a limit to the stack size in Julia, but for the life of me I could not find any information pertaining to this, nor how to increase the size of the stack. So, similar to Python, large recursive processes should likely be avoided.

Running the iterative version of the flood fill runs without any problem, regardless of the size of the image.

 

 

 

Advertisements

3 thoughts on “Julia breaks recursion!

  1. Ángel De Vicente says:

    Hi,
    somehow stumbled on your post. As far as I know, Julia will use whatever stack size you have defined for your session. In my case I run your sample recursion code on a 1000×1000 matrix no problem after setting an unlimited stack size before starting Julia (in bash “ulimit -s unlimited”).
    Cheers,
    Ángel

    • spqr says:

      Hi,
      Yes, that would work – on some systems. On many systems there are hard limits to which the stack can be set, and ulimit -s unlimited would respond with a message of the form:
      “-bash: ulimit: stack size: cannot modify limit: Operation not permitted”.
      At the end of the day, a compiler shouldn’t need to rely on external modifications of stack space. Python has the same problem. Ultimately alternatives to recursion may be better from an algorithmic viewpoint anyway.
      cheers,
      Mike

  2. Ángel De Vicente says:

    Hi,
    but the issue is not with Julia, since any code relying on a bigger stack (recursion without tail call optimization, for example) will produce a stack overflow (be it C, Fortran, Python, whatever…)
    Cheers,
    Ángel

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s