title: MapReduce with Recursion
body: <p>Consider the following problem:</p>
  
  <p>EDIT: Ignore if the algorithm below doesn't make much sense. I just put it there for the sake of it. The idea is that <code>doFunc</code> is somehow recursive.</p>
  
  <pre><code>doFunc(A):
      [a0, a1, a2, ...] &lt;- A
      If (someCondition([a0, a1, a2, ...]) == False)
          A &lt;- modified(A)
          r = doFunc(modified(A))
          A &lt;- convertR(r)
      B &lt;- someFunc1(A)
      C &lt;- someFunc2(B)
      r &lt;- lastFunc(D)
      return r
  </code></pre>
  
  <p>In this case, r is the result of the recursive function <code>doFunc</code> where someCondition on the list of <code>a0, a1, a2, ...</code> is <code>false</code>, the function recurses to get some kind of an optimal <code>A</code> for which the condition is <code>true</code>.</p>
  
  <p>Now consider that MapReduce could individually be applied to different parts of the program - say for example converting <code>A</code> to <code>a0, a1, a2, ...</code> and then to getting the <code>modifiedA</code> and then <code>someFuncI</code> are all possible using MapReduce, how does the recursion fit into this MapReduce implementation?</p>
  
  <p>Considering this, Hadoop Streaming is kind of out of the question given I don't understand how to implement it with Recursion. The only other possibility is doing some form of Python Hadoop Streaming Wrapper for example <code>dumbo</code> or <code>mrjob</code> to write the code ignoring that there is recursion which is obviously going to unfold when <code>doFunc</code> is called recursively. I am wondering that how that factors in with MapReduce and what the scalability is like.</p>
  
  <p>Questions: I have asked the questions in the text above but they might not be clear enough. So I'll have them laid in clear here.</p>
  
  <ol>
  <li>Does MapReduce behave well with Recursion?</li>
  <li>If so, does it scale well?</li>
  <li>Is there a way to implement Hadoop Streaming with functions involving recursion?</li>
  </ol>