Non-recursive (iterative) DFS with $O(n)$ size stack
You can keep only the topmost copy of a node on the stack:

dfs(source):
   s &lt;- empty stack
   visited &lt;- {}
   on_stack &lt;- map&lt;node,stack element&gt;
   s.push(source)
   on_stack.add(source,s.top())
   while s is not empty:
      current = s.pop()
      on_stack.remove(current)
      if visited.contains(current):
         continue
      # handle current
      visited.add(current)
      for v a neighbor of current:
         if on_stack.contains(v):
            stack_element &lt;- on_stack.get(v)
            unlink stack_element from s
         stack.push(v)
         on_stack.add(v,s.top())


If your stack is a linked list, the asymptotic runtime stays the same. I doubt however that it will be much faster in practice unless your graphs are very dense, because the constants involved are much bigger.