title: How to implement a recursive DFS in Clojure (without using a vector / stack)
body: <p>How would I code the equivalent of the following python in clojure, but strictly using recursion for the stack management (e.g. not using a loop/recur with a vector acting as the frontier)? <br/> I realize it's fairly simple with a vector maintaining your paths and just peeking / popping, but I'm doing this as a thought exercise.</p>
  
  <p><strong>Python Version</strong></p>
  
  <hr>
  
  <pre><code>def dfs(start,successors,goal,visited=set()): 
      if start not in visited:
          visited.add(start)
          for s in successors.get(start):
              if goal(s): 
                  return s
              else:
                  res = dfs(s,successors)
                  if res: return res #bail early when found
      return False
  </code></pre>
  
  <p><strong>Clojure Version</strong></p>
  
  <hr>
  
  <pre><code>(defn dfs [start goal? successors visited]
    (if (goal? start) 
         start
        (when (not (contains? visited start))
               (mapcat #(dfs % goal?  successors (conj visited start)) 
                        (successors start)))))
  </code></pre>
  
  <p>Since iteration is controlled by a call to map in the Clojure version, you can't really bail early the way you can in Python e.g. <code>if goal(s): return s</code>. <br/> Since you are collecting the recursive calls inside of a list with map, you are forced to evaluate every possible node even after the target is found.  Only then after all nodes have been explored do you get the result.
  <hr>
  Now, I know I can do something like this (I know this isn't pretty... just trying to provide a quick example, feel free to suggest improvements!) but I'm primarily interested in seeing if there is a way to avoid explicitly using a stack, and letting the call stack do the work like in the python version.</p>
  
  <pre><code>(defn dfs-non-rec [frontier goal? successors visited]
    (loop [f frontier g? goal? s successors v visited]
          (let [node (peek f)]
               (cond ; case 1
                     (goal? node) 
                      node
                     ;case 2
                     (not (contains? v node))
                     (recur (vec (concat (pop f) (successors node))) g? s (conj v node))
                     ;case 3
                     :else 
                     (recur (pop f) g? s (conj v node)))))) 
  </code></pre>
  
  <p>How should I approach this?</p>
  
  <p><strong>EDIT</strong> 
  <hr>
  There was some confusion on my part as to whether some of the provided answers were in fact depth-first.  The confusion stemmed from an assumption I made about the input, which I should have provided in this post originally.  I had assumed the input as an adjacency list, which represents a <em>graph</em>, rather than a <em>tree</em> </p>
  
  <pre><code>(def graph  {"a"  ["b","c","d"],
               "b"  ["a","e","f"],
               "c"  ["x","y"],
               "d"  [],
               "e"  [],
               "f"  [],
               "x"  ["c"],
               "y"  ["e"]})
  </code></pre>
  
  <p>then when converted to a seq, the order followed is in-fact depth-first <em>for that resulting tree</em> created by calling seq on the graph, however the order implied by the adjacency list is not followed, because the graph structure is lost in the conversion. </p>
  
  <p>So if you are looking for the node <code>x</code> starting at the <code>a</code>, I would expect the traversal order to be <code>adcyex</code>, rather than <code>abcdbaefcxy</code></p>