title: Depth first search algorithm in python
body: <p>(This question is followed up in more detail here: <a href="https://stackoverflow.com/questions/33156834/python-search-algorithm-from-implied-graphs">python-search-algorithm-from-implied-graphs</a>)  </p>
  
  <p>Suppose I have a function that takes an input ($x_i$) and then goes through a loop and yields a series of outputs ($x_{i, j}$). Then each output can be an input again to the same function yielding further outputs ($x_{i, j, k}$). And I'm trying to find a set of steps via this function to a particular end state. </p>
  
  <p>This is a general problem, and my question is what is a good code structure within python to handle this.</p>
  
  <p>Here's some meta code as an example (though it might be more complicated in practice):</p>
  
  <pre><code>def f(x):
    for i in range(n):
      if some_condition:
        yield g(x,i) 
    yield false
  </code></pre>
  
  <p>Then for some $x_0$ and some $y$, we're looking for a sequence $x_0,x_1,\ldots,x_k$, such that $x_k=y$, and $x_{j+1}=g(x_j,i_j)$ for $j\in{0,\ldots,k-1}$.</p>
  
  <p>To do this with a depth first search where you would calculate $f(f(\ldots f(x) \ldots))$ first until it yields the targeted result or a false. Then back up one step and yield the second result from $f$ and repeat (a rough description, but you get the idea: a depth first search, basically). </p>
  
  <p>It seems to me that the yield keyword is going to be inefficient to handle this. You've also got to handle the stack (I think this is the right terminology) of $(x, f(x), f(f(x)),\ldots)$ in a way that allows you to back track when you hit a dead end. </p>
  
  <p>This general problem is something I come across now and then, and I kind of solve it <em>ad hoc</em>, but I wondered if there was a good general structure for solving this, which naturally and efficiently handles the stack and exploring the tree of possible solutions in python. </p>
  
  <p>I hope this question is sufficiently clear. I welcome any thoughts, comments, clarifications or answers. </p>