Nested loops via recursion

I encountered a problem where I needed to program a nested loop and wanted to share (code is in Julia).

Problem: We have a lattice with n ordered lattice sites, each of which are in state -1 or 1. There are thus distinct lattice states. My goal is to exhaustively enumerate each of these lattice states.

We can store the state of the lattice in an n-dimensional array of integers, lattice_state. For n=2, we can use a nested for loop to enumerate all lattice states. Each for loop represents a particular lattice site, or entry of lattice_state.

n = 2
lattice_state = zeros(Int, n)
for i = [-1, 1]
    lattice_state[1] = i
    for j = [-1, 1]
        lattice_state[2] = j
        println(lattice_state)
    end
end
 # =>
 # [-1,-1]
 # [-1,1]
 # [1,-1]
 # [1,1]

When n gets large, this looks ugly because we need to write n nested loops:

n = 4
lattice_state = zeros(Int, n)
for i = [-1, 1]
    lattice_state[1] = i
    for j = [-1, 1]
        lattice_state[2] = j
        for k = [-1, 1]
            lattice_state[3] = k
            for l = [-1, 1]
                lattice_state[4] = l
                println(lattice_state)
            end
        end
    end
end
 # =>
 # [-1,-1,-1,-1]
 # [-1,-1,-1,1]
 # [-1,-1,1,-1]
 # [-1,-1,1,1]
 # [-1,1,-1,-1]
 # [-1,1,-1,1]
 # [-1,1,1,-1]
 # [-1,1,1,1]
 # [1,-1,-1,-1]
 # [1,-1,-1,1]
 # [1,-1,1,-1]
 # [1,-1,1,1]
 # [1,1,-1,-1]
 # [1,1,-1,1]
 # [1,1,1,-1]
 # [1,1,1,1]

We can use a recursive algorithm instead to write a function for a general n:

n = 8
lattice_state = zeros(Int, n)
function nested_loop(loop_level::Int)
    """
    Recursive algorithm to perform nested loop:
    for i = [-1, 1]
        lattice_state[1] = i
        for j = [-1, 1]
            lattice_state[2] = j
            .... n times
        end
    end

    Prints all possible lattice_state arrays.
    Parameters:
        loop_level, Int: level of nested loop we are in.
        Nested loop `loop_level` modifies entry `loop_level` in `lattice_state`. 
    """
    # if we are the last loop,
    # print the array and return (do not go on)
    if (loop_level > n)
        println(lattice_state)
        return
    end
    # if we made it past this point, 
    # we need to continue going in the nested loop
    for i = [-1, 1]
        # modify entry loop_level
        lattice_state[loop_level] = i

        # with entry 1, 2, ..., loop_level fixed, 
        # call function again to go to next level in nested loop
        nested_loop(loop_level + 1)
    end
end

Now, I call the nested_loop function with loop_level=1 to start at the first loop in the nest. It will then print all configurations of the lattice of length n=8, represented by unique lattice_state arrays:

nested_loop(1)
comments powered by Disqus