Updating an empty list within a recursive function

New to Julia
,
1

I implemented a recursive function within which I create an empty list. At the end of every recursion, I push the result (i.e. visited) onto the list but as soon as the recursion begins, I have an empty list. I’m able to print the output (i.e. visited) onto the terminal without any problems but I want the function to return the output of all the recursions as a list. Can you please help me with this?

Thanks

function RecDFS(genericgraph, visited, sink)

  """ Reads in a generic graph and a source-destination pair and prints an
      exhaustive list of paths using the Depth-first search (DFS) Technique  """

  ############################################################################
  # Credit: team17@stackoverflow.com

  nodes = LightGraphs.neighbors(genericgraph, visited[length(visited)]) # Returns neighbour nodes
  pathList = []

  for i in nodes

    if i == sink
      push!(visited, i)
      println(visited) # The accumulated paths are printed out iteratively
      push!(pathList, visited)
      pop!(visited)
    elseif !in(i, visited)
      push!(visited, i)
      RecDFS(genericgraph, visited, sink) # Recursion starts here
      pop!(visited)
    end

  end

return pathList
  
end
2

The general scheme you want to use here is something like this (untested):

# This function is your entry point
RecDFS(genericgraph, visited, sink) = RecDFS!([], genericgraph, visited, sink)
# This mutating function allows you to specify the current list you're working on
function RecDFS!(pathList, genericgraph, visited, sink)
  nodes = LightGraphs.neighbors(genericgraph, visited[length(visited)]) # Returns neighbour nodes
  for i in nodes
    if i == sink
      push!(visited, i)
      println(visited) # The accumulated paths are printed out iteratively
      push!(pathList, visited)
      pop!(visited)
    elseif !in(i, visited)
      push!(visited, i)
      RecDFS!(pathList, genericgraph, visited, sink) # Recurse with the current list
      pop!(visited)
    end
  end
5 Likes
3

I tested it and it worked perfect. Few mins earlier, I tried a similar solution where I just declare an empty list and pass it as an argument for the function (just like what RecDFS! does) and that worked too. Thanks for the solution @mbauman

1 Like