How to implement a recursive DFS in Clojure (without using a vector / stack)

Question

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)?
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.

Python Version

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

Clojure Version

(defn dfs [start goal? successors visited]
  (if (goal? start) 
       start
      (when (not (contains? visited start))
             (mapcat #(dfs % goal?  successors (conj visited start)) 
                      (successors start)))))

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. if goal(s): return s.
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.

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.

(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))))))

How should I approach this?

EDIT

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 graph, rather than a tree

(def graph  {"a"  ["b","c","d"],
             "b"  ["a","e","f"],
             "c"  ["x","y"],
             "d"  [],
             "e"  [],
             "f"  [],
             "x"  ["c"],
             "y"  ["e"]})

then when converted to a seq, the order followed is in-fact depth-first for that resulting tree 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.

So if you are looking for the node x starting at the a, I would expect the traversal order to be adcyex, rather than abcdbaefcxy

leetwinski leetwinski · Accepted Answer · 2017-12-13T10:25:21

first of all you don't really need to check tree for loops, since clojure's data structures don't have circular references (unless you don't use mutable state with atoms referencing to another atoms, which is an obvious code smell). The simple way of traversal could look like this (this way is referenced by lots of lisp (and overall programming) books):

user> (defn dfs [goal? data]
        (if (goal? data)
          data
          (loop [data data]
            (when-let [[x & xs] (seq data)]
              (cond (goal? x) x
                    (coll? x) (recur (concat x xs))
                    :else (recur xs))))))

user> (dfs #{10} [1 [3 5 [7 9] [10] 11 12]])
10

user> (dfs #{100} [1 [3 5 [7 9] [10] 11 12]])
nil

in addition there are more concise (and thus idiomatic i guess) ways to do this in clojure. The simplest one is to use tree-seq:

user> (defn dfs [goal? tree]
        (first (filter goal? (tree-seq coll? seq tree))))
#'user/dfs

user> (dfs #{10} [1 [3 5 [7 9] [10] 11 12]])
10

user> (dfs #{100} [1 [3 5 [7 9] [10] 11 12]])
nil

user> (dfs (every-pred number? even?) [1 [3 5 [7 9] [10] 11 12]])
10

tree-seq is lazy, so it only traverses tree until you find the needed value.

another way is to use clojure's zippers:

user> (require '[clojure.zip :as z])
nil

user> (defn dfs [goal? tree]
        (loop [curr (z/zipper coll? seq identity tree)]
          (cond (z/end? curr) nil
                (goal? (z/node curr)) (z/node curr)
                :else (recur (z/next curr)))))
#'user/dfs

user> (dfs #{10} [1 [3 5 [7 9] [10] 11 12]])
10

user> (dfs #{100} [1 [3 5 [7 9] [10] 11 12]])
nil

user> (dfs (every-pred number? even?) [1 [3 5 [7 9] [10] 11 12]])
10

How to implement a recursive DFS in Clojure (without using a vector / stack)

2 Answers