Fortran recursion segmentation faults

Question

Hey all -

I have to design and implement a Fortran routine to determine the size of clusters on a square lattice, and it seemed extremely convenient to code the subroutine recursively. However, whenever my lattice size grows beyond a certain value (around 200/side), the subroutine consistently segfaults. Here's my cluster-detection routine:

RECURSIVE SUBROUTINE growCluster(lattice, adj, idx, area)
    INTEGER, INTENT(INOUT)  :: lattice(:), area 
    INTEGER, INTENT(IN)     :: adj(:,:), idx

    lattice(idx) = -1
    area = area + 1

    IF (lattice(adj(1,idx)).GT.0) &
        CALL growCluster(lattice,adj,adj(1,idx),area)

    IF (lattice(adj(2,idx)).GT.0) &
        CALL growCluster(lattice,adj,adj(2,idx),area)

    IF (lattice(adj(3,idx)).GT.0) &
        CALL growCluster(lattice,adj,adj(3,idx),area)

    IF (lattice(adj(4,idx)).GT.0) &
        CALL growCluster(lattice,adj,adj(4,idx),area)
END SUBROUTINE growCluster

where adj(1,n) represents the north neighbor of site n, adj(2,n) represents the west and so on. What would cause the erratic segfault behavior? Is the cluster just "too huge" for large lattice sizes?

Answer 1

1) Have you tried compiling and then running with subscript-range checking turned on? Just to make sure that the large size isn't revealing a bug in which the code steps past the array bounds into illegal memory. It's an easy check.

2) Re the possibility that your program is running out of memory: try increasing the per-process stack size limit. How to do this depends on the operating system -- search here, or google, or tell us your operating system.

Answer 2

I think you're running into a stack overflow. If your lattice is over 200 units per side, that's 40,000 units, which means you're recursing 40,000 times. Depending on your stack size and your stack frame size, you could easily be running out of stack space.

You'll have to convert your algorithm into one that uses less stack space in order to handle larger lattices. Wikipedia provides a few implementations (in pseudocode) on how to do a flood fill without blowing your stack.